정렬 알고리즘엔 많은 기법이 존재한다.
시간복잡도가 O(n²)인 선택정렬과 삽입정렬 그리고 O(n log n)인 퀵정렬에 대해서 알아보자.

O(n²)

선택정렬

선택 정렬을 실행했을 때 나오는 그림.

버블 정렬이 비교하고 바로 바꿔 넣는 걸 반복한다면 이쪽은 일단 1번째부터 끝까지 훑어서 가장 작은 게 1번째, 2번째부터 끝까지 훑어서 가장 작은 게 2번째……해서 (n-1)번 반복한다. 어찌 보면 인간이 사용하는 정렬 방식을 가장 많이 닮았다. 어떻게 정렬이 되어 있든 일관성 있게 $\frac{n(n-1)}{2}$ 에 비례하는 시간이 걸린다는 게 특징. 또한, 버블 정렬보다 두 배 정도 빠르다

파생형으로 이중 선택 정렬(Double Selection Sort)도 있다. 이쪽은 끝까지 훑어서 최솟값과 최댓값을 동시에 찾아낸 뒤 최솟값은 1번째와 바꾸고 최댓값은 끝과 바꾼 다음 훑는 범위를 양쪽으로 한 칸씩 줄여서 반복하는 방식이다. 즉 선택 정렬에 칵테일 정렬 방식을 도입한 것. 이 방법을 쓰면 반복 횟수가 반으로 줄어든다.

삽입정렬

삽입 정렬을 알기 쉽게 만든 그림. 선택 정렬과 함께 인간에게 뭔가를 정렬하라고 하면 무의식적으로 사용하는 대표적인 알고리즘이다.

k번째 원소를 1부터 k-1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식으로, 평균적으론 $O(n^2)$ 중 빠른 편이나 자료구조에 따라선 뒤로 밀어내는데 걸리는 시간이 크며, 앞의 예시처럼 작은 게 뒤쪽에 몰려있으면(내림차순의 경우 큰 게 뒤쪽에 몰려있으면) 그야말로 헬게이트다.
다만 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다. 괜히 '삽입'이란 이름이 붙은 것이 아니다.

그밖에도 배열이 작을 경우에 역시 상당히 효율적이다. 일반적으로 빠르다고 알려진 알고리즘들도 배열이 작을 경우에는 대부분 삽입 정렬에 밀린다. 따라서 고성능 알고리즘들 중에서는 배열의 사이즈가 클때는 $O (n\log n)$ 알고리즘을 쓰다가 정렬해야 할 부분이 작을때 는 삽입 정렬로 전환하는 것들도 있다.

또 굳이 장점을 뽑자면 구현이 매우 쉽다는 것. 그 예로 C/C++에서 기본적인 삽입 정렬을 구현하는데는 서너줄의 코드면 충분하다.

파생형으로 이진 삽입 정렬(Binary insertionSort)이 있다. 이진 탐색을 활용해 새로운 원소가 위치할 곳을 미리 찾아서 정렬하는 방식이다. 원소크기를 비교하는 조건 부분을 $(\log n)$수준으로 낮춰 조금은 더 빠르게 수행할 수 있다는 점 정도.

O(n log n)

퀵 정렬

퀵 정렬의 적절한 예시.

찰스 앤터니 리처드 호어가 1959년에 개발한 알고리즘이다. 퀵이라는 이름에서 알 수 있듯이 평균적인 상황에서 최고의 성능을 나타낸다. 컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나이다. C, C++, PHP등의 언어에서 제공하는 정렬 함수에서 퀵 정렬 혹은 퀵 정렬의 변형 알고리즘을 사용한다. 방식은 적절한 원소 하나를 기준(피벗, pivot)으로 삼아 그보다 작은 것을 앞으로 빼내고 그 뒤에 피벗을 옮겨 피벗보다 작은 것, 큰 것으로 나눈뒤 나누어진 각각에서 다시 피벗을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬한다. 이렇게 피벗을 잡고 이보다 작은 원소들을 왼쪽으로, 보다 큰 원소들을 오른쪽으로 나누는걸 partition step이라 한다. 퀵 정렬에도 이 partition step을 어떻게 하느냐에 따라 바리에이션이 매우 많으며, 성능 차이도 날 수 있다.

퀵 정렬의 가장 간단한 분할 알고리즘인 로무토 파티션을 도식화 해보면 그림과 같다. 피벗은 맨 오른쪽 값을 기준으로 하며, 이를 기준으로 2개의 포인터가 이동해서 오른쪽 포인터의 값이 피벗보다 작다면 서로 스왑하는 형태로 진행된다. 오른쪽 right 포인터가 이동하면서 피벗의 값이 오른쪽 값보다 더 클때, 왼쪽과 오른쪽의 스왑이 진행된다. 스왑 이후에는 왼쪽 left 포인터가 함께 이동 한다. 여기서 피벗의 값은 4이므로, 오른쪽 포인터가 끝에 도달하게 되면 4 미만인 값은 왼쪽으로, 4 이상인 값은 오른쪽에 위치하게 된다. 그리고 왼쪽 포인터의 위치로 피벗 아이템이 이동한다. 즉 그림에서 최종 결과인 8)을 보면, 4를 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽으로 분할되어 있고, 피벗이 그 중앙으로 이동하는 모습을 확인할 수 있다. 이렇게 계속 분할하면서 정복을 진행하여 코드 기준으로 left < right를 만족하지 않을 때까지, 즉 서로 위치가 역전할 때까지 계속 재귀로 반복되면서 정렬이 완료된다.

하지만 앞서 위에서도 말했듯이 최악의 경우에는 시간복잡도가 $O(n^2)$가 되는데, 피벗을 최솟값이나 최댓값으로 계속해서 잡게 되는 경우에 그렇다. 대표적인 예로는 피벗을 항상 배열의 첫 번째 원소를 잡도록 구현했을때 이미 정렬된 배열을 정렬할 경우. 다음 그림과 같이 전혀 분할이 진행되지 않고 하나씩 정렬되는 모습을 확인할 수 있다. 힙정렬이나 병합정렬은 이런 경우가 없지만, 데이터가 극단적이면 대충 구현된 퀵정렬은 안 쓰느니만 못한 최악의 결과를 초래한다.

이를 방지하기 위하여 여러 기법들이 개발 되었는데, 대표적인 것이 피벗을 랜덤으로 잡는 것(Random Quick sort). 또는, 무조건 배열의 위치상 중간에 있는걸 피벗으로 잡거나 배열 중에 3개나 9개의 원소를 골라서 이들의 중앙값을 피벗으로 고르는 것이다. 이 방법을 사용하더라도 최악의 경우가 나올 수는 있지만 그 경우가 극히 드물게 된다. 다만 배열이 단순하게 비교 가능한 숫자가 아니라면 중앙값 피벗 방법이 비효율적일 수도 있다. 예를 들어서 비교하는데 연산이 아주 많이 들어가는 객체 또는 데이터 베이스. 이럴땐 그냥 무작위 또는 중간에 있는 원소를 피벗으로 잡는게 낫다.

피벗을 랜덤으로 정한다고 해도 정렬 시간이 $O(n^2)$로 나쁜 경우가 나올 수 있다. 그래서 이런 나쁜 케이스들을 완전히 없애고 싶다면 순수 퀵 소트 보다는 특수한 상황이 나왔을때 다른 빠른 정렬 알고리즘을 섞어서 쓰는 하이브리드 퀵 소트가 좋다. 그래서 재귀 깊이가 어느 제한 이상으로 깊어질 경우 힙 정렬 알고리즘을 사용하여 항상 $O (n\log n)$을 보장해주는 방법도 많이 쓰인다. (인트로 정렬)

크드 리스트 역시 퀵정렬이 가능하다. 첫번째 노드 A를 피벗으로 놓고 나머지 노드들 중 피벗보다 작은 것들은 L1, 큰 것들은 L2로 연결한다. L1과 L2를 퀵정렬한 뒤 L1->A->L2 순으로 연결하면 정렬 완료. 힙소트나 머지소트 역시 가능.

파이썬은 퀵정렬을 하지 않는다. 파이썬은 안정(stable) 정렬을 하는데, 퀵정렬은 불안정 정렬이다. 예를 들어 한글의 키값이 2, 영문의 키값이 1이라 두면 a, ㄱ , ㄷ, ㄹ, b를 퀵정렬해서 b, a, ㄹ, ㄱ, ㄷ 같은 게 나올 수도 있다. $O(n)$의 추가 메모리를 이용하면 안정한 퀵정렬을 만들 수 있다.

현존하는 컴퓨터 아키텍처상에서 비교 연산자를 이용하여 구현된 정렬 알고리즘 중 가장 고성능인 알고리즘이 바로 이 퀵정렬이다. 단 데이터에 접근하는 시간이 오래 걸리는 외부 기억장소(하드디스크 등)에서 직접 정렬을 수행할 경우에는 병합 정렬이 더 빠른 것으로 알려져 있다. 요즘에는 디스크에서 데이터를 블럭 단위로 읽어서 각각을 퀵정렬한 뒤 정렬된 두 블럭을 병합정렬하는 식으로 알고리즘을 설계한다.

참고
https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98