정렬 문서 원본 보기

[[분류: 정렬]]

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

== 종류 ==
=== <math>O(n^2)</math> ===
#[[Bubble Sort]]
#[[Shaker Sort]]
#[[Selection Sort]]
#[[Insertion Sort]]
=== <math>O(n^{1.2})</math> ===
#[[Shell Sort]] (간격을 어떻게 상정하느냐에 따라 시간 복잡도가 매우 달라진다.)

===  <math>O(n\log_2{n})</math>===
#[[Heap Sort]]
#[[Quick Sort]] (최약의 경우 <math>n^2</math>)
#[[Merge Sort]]