정렬 알고리즘

$ O(n^2) $

버블 정렬 (Bubble Sort)

1. 1번째와 2번째 원소를 비교하여 정렬한다.
2. 2번째와 3번째 원소를 비교하여 정렬한다.
3. n-1번째와 n번째를 비교하여 정렬한다.
4. 1-3을 반복하되 n-2번째와 n-1번째까지만 비교한다.
5. 모든 원소가 정렬될 때까지 반복한다.

구현이 쉽고 직관적이지만 거의 모든 상황에서 최악의 성능을 보여준다.

선택 정렬 (Selection Sort)

1. 배열에서 가장 작은 값과 1번째 원소의 자리를 바꾼다.
2. 1번째 원소를 제외한 배열에서 가장 작은 값과 2번째 원소의 자리를 바꾼다.
3. 모든 원소가 정렬될 때까지 반복한다.

정렬 상태에 상관없이 $ \frac{n(n-1)}{2} $ 에 비례하는 시간이 걸린다.

삽입 정렬 (Insertion Sort)

1. 2번째 원소를 1번째 원소와 비교하여 적당한 자리에 삽입한다.
2. 3번째 원소를 1, 2번째 원소와 비교하여 적당한 자리에 삽입한다.
3. 모든 원소가 정렬될 때까지 반복한다.

이미 정렬이 되어있는 자료구조에 자료를 삽입/제거하거나 배열이 작을 경우에 효율적이다.

$ O(nlogn) $

병합 정렬

병합 정렬은 다음과 같은 단계로 이루어 진다.

1. 배열의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.

2. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
3. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 다시 병합 정렬을 재귀적으로 적용한다.
4. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
   1. 2개의 배열의 값들을 처음부터 하나씩 비교하여 2개의 배열의 값 중에서 더 작은 값을 새로운 배열로 옮긴다.
   2. 둘 중 하나가 끝날 때까지 이 과정을 되풀이한다.
   3. 둘 중 하나의 배열이 먼저 끝나게 되면 나머지 배열의 값을 전부 새로운 배열로 복사한다.
   4. 새로운 배열을 원래의 배열로 옮긴다.

데이터와 동일한 크기의 메모리가 필요하고, 동일 값에 대해서 기존의 정렬 순서가 유지되는 Stable한 정렬이다.

힙 정렬 (Heap Sort)

1. 원소들을 전부 힙에 삽입한다.
2. 힙의 루트를 출력하고 힙에서 제거한다.
3. 힙이 빌 때까지 2를 반복한다.

이론상 $ O(nlogn) $의 성능을 내지만 최악의 경우 $ O(n^2) $ 성능을 내는 퀵정렬보다 성능이 떨어진다.

• 퀵 정렬은 원소들끼리 근접한 메모리 영역에 있는 배열을 사용하기 때문에 캐시 친화적이다.
• 힙 정렬을 포인터 연산을 많이 사용하기 때문에 포인터 연산에 걸리는 오버헤드가 있다.

퀵 정렬 (Quick Sort)

1. Pivot을 맨 왼쪽 값으로 설정한다.
2. 2개의 포인터가 이동해서 왼쪽 포인터의 값이 pivot보다 크다면 서로 스왑하는 형태로 진행된다. left 포인터가 이동하면서 pivot의 값이 왼쪽 값보다 작을 때, 왼쪽과 오른쪽의 스왑이 진행된다.
3. 스왑 이후에는 right 포인터가 함께 이동 한다.
4. left 포인터가 끝에 도달하게 되면 pivot 미만인 값은 왼쪽으로, pivot 이상인 값은 오른쪽에 위치하게 된다.
5. right 포인터의 위치로 피벗 아이템이 이동한다

$ O(n) $

계수 정렬 (Counting Sort)

1. 배열을 돌면서 데이터의 개수를 데이터의 값에 대응하는 위치에 저장한다. (1이 2개 있으면 a[1] = 2)

2. 1에서 만든 배열 a를 순서대로 돌면서 데이터의 위치를 찾아낸다.

크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘으로 데이터의 최대값만큼의 크기를 갖는 배열이 필요하다.

기수 정렬 (Radix Sort)

1. x진법의 데이터에 대하여 0번부터 x-1번까지의 bucket을 만들어 놓는다.
2. 배열을 순회하며 각 데이터의 가장 낮은 자리수에 해당하는 bucket의 값을 하나 올린다.
3. bucket을 순회하며 bucket의 누적합 배열을 준비한다.
4. 배열을 역으로 순회하며 3에서 만든 배열의 값을 각 데이터의 index로 한다. 그리고 bucket의 값을 하나 줄인다.
5. 가장 큰 자릿수의 정렬이 완료될 때까지 1-4를 반복한다.

기수 정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 시간복잡도가 자릿수 k에 비례하고 데이터의 특성에 따라 기수 정렬이 불가능한 경우도 있어 사용할 수 있는 범위가 제한적이다.