정렬

개요

정렬 (sort)는 데이터를 특정 규칙에 따라 재배열하는 것을 말한다. 1, 5, 11 처럼 작은 수부터 나열한 것을 오름차순, 반대를 내림 차순이라 한다. 정렬에 필요한 시간은 주로 비교 횟수와 교환 횟수에 의해 정해진다. 이 횟수는 수열 데이터가 어떻게 나열되어 있는지와 기기에 따라 다르다. 그러나 이 횟수는 방식에 따라서 엄청난 차이가 존재하기에 개선된 알고리즘의 정렬을 사용해야 한다.

종류

[math]O(n^2)[/math]

1. Bubble sort
2. Shaker sort
3. Selection sort
4. Insertion sort

[math]O(n^{1.2})[/math]

1. Shell sort (간격을 어떻게 상정하느냐에 따라 시간 복잡도가 매우 달라진다.)

[math]O(n\log_2{n})[/math]

1. Heap sort
2. Quick sort (최약의 경우 [math]n^2[/math])
3. Merge sort