알아두면 유용한 정렬 알고리즘

Selection Sort(선택 정렬)

Selection Sort는 첫 번째부터 끝까지 훑어서 가장 작은게 1번째, 2번째부터 끝까지 훑어서 가장 작은게 2번째 이런식으로 (n-1)번을 반복하는 방식으로 시간 복잡도는 O(n(n-1)/2)다.
파생형으로 Double Selection Sort(이중 선택 정렬)도 있다. 이 방법을 사용하면 반복 횟수가 반으로 줄어든다.

Insertion Sort(삽입 정렬)

Insertion Sort는 n번째 원소를 1번째부터 n-1번째까지 비교해 끼워넣고 그 뒤의 원소들을 한 칸씩 뒤로 밀어내는 방식으로 시간복잡도는 O(n^2)이다.
평균적으로 O(n^2) 정렬 중에는 빠른 편이지만 데이터가 한쪽에 치우쳤을 경우 비교 횟수와 이동이 크게 차이난다.
하지만 이미 정렬 되어 있는 리스트에 자료를 하나씩 삽입/제거 하는 경우에 매우 유용하며 이는 탐색을 제외한 오버헤드가 매우 적기때문이다.

Quick Sort(퀵 정렬)

Quick Sort는 분할 정복(Divide and conquer)이라는 방법을 통해 리스트를 정렬하는 기법으로 데이터들 중 피봇이라는 기준 데이터를 선정하고 나머지 데이터들과 비교하며 데이터를 정렬한다.
퀵 정렬의 시간복잡도는 n개의 데이터를 정렬할 때 최악의 경우에는 O(n^2)번의 비교를 수행하고, 평균적으로 O(nlogn)번의 비교를 수행하는데 이는 피봇의 선정 기준이나 데이터의 정렬 상태에 따라 비교 횟수가 상이해지기 때문이다.
피봇 위치에 따라 비교 횟수가 늘어날 수 있으며 최악의 경우에는 피봇이 모든 데이터들과 비교를 하게되는 경우(데이터가 이미 정렬되어있거나 역순으로 정렬되어있는것과같은 특수한 상황)가 될 수 있다.
하지만 피봇 선정은 난수분할이나 중위법 같은 것들을 통해 알고리즘을 설계하는 것이 가능하고 실질적인 데이터가 정렬되어 오진 않기 때문에 일반적인 상황에서 최악의 경우는 배제할 수 있다고 한다.
또한 퀵 정렬 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있기때문에(메모리 참조가 지역화되어 있기때문에 CPU 캐시의 히트율이 높아지기 때문이라고 함) 일반적인 상황에서는 다른 O(nlogn) 알고리즘에 비해 훨씬 빠르게 동작한다고 한다.
퀵 정렬은 원본 데이터에 영향도가 있는 불안정 정렬(동일한 값을 가진 데이터들의 순서가 정렬 후에는 바뀔 수 있음)에 속한다.

Merge Sort(합병 정렬)

Merge Sort는 분할 정복 알고리즘의 일종으로 리스트를 반으로 나누면서 리스트의 길이가 1 이된 후 다시 반씩 비교를 하며 하나의 정렬된 리스트로 합병하는 방식이다.
다시 리스트로 합병해야할 공간이 필요하므로 원본 데이터 크기만한 메모리가 추가적으로 필요하다는 점이 있다.
합병 정렬의 시간복잡도는 반씩 분할하며 다시 반씩 합쳐지는 과정에서 logn번의 비교 연산이 이루어지고 여기에 데이터 요소 개수 n개를 곱한 O(nlogn)으로 최악, 최고, 평균 모두 동일하다.
합병 정렬의 성능은 퀵정렬에 전반적으로 뒤지긴하지만 최악의 경우에도 O(nlogn)이라는 점에서 차이가 있으며 원본 데이터에 영향도가 크지 않는 안정 정렬이라는 점이 장점이다.