들어가며
지난 시간에는 기본적인 정렬 알고리즘에 대해 알아봤는데요. 이번 시간에는 그보다 효율적인 정렬 알고리즘에 대해 알아보겠습니다.
병합 정렬(Merge sort)
분할 정복 알고리즘의 대표적인 예로, 리스트를 반으로 나누어 정렬한 뒤 다시 병합하는 방식으로 동작합니다.
병합 정렬의 동작 과정은 다음과 같습니다.
- 원소 개수가 1 또는 0이 될 때까지 리스트를 절반으로 나눕니다.
- 각 부분 리스트를 정렬합니다.
- 정렬된 두 부분 리스트를 병합합니다.
시간복잡도
O(n log n)
공간복잡도
O(n)
특징
- 분할 정복 알고리즘
- 안정 정렬
- 추가적인 메모리 공간 필요
- 병렬 처리에 적합
- 대규모 데이터 처리에 효과적
힙 정렬(Heapsort)
힙 자료구조를 활용하여 정렬을 수행하는 알고리즘입니다.
동작 과정은 다음과 같습니다.
- 주어진 입력 배열을 최대 힙으로 구성합니다.
- 최대 힙의 루트 노드(가장 큰 값)를 마지막 노드와 스왑합니다.
- 힙의 크기를 1 줄이고, 다시 최대 힙을 구성합니다.
- 2, 3번 과정을 반복하여 전체 배열이 정렬될 때까지 진행합니다.
시간복잡도
O(n log n)
공간복잡도
O(1)
특징
- 힙 구조 사용
- 불안정 정렬
- 제자리 정렬
- 대규모 데이터 처리에 효과적
선택 정렬과 거의 같은 알고리즘이지만, 유일한 차이점은 가장 큰 원소를 알아낼 때 전체 배열을 순회하는지 힙을 사용하는지입니다.
퀵 정렬(Quicksort)
분할 정복 알고리즘의 대표적인 예로, 정렬 알고리즘 중에서도 가장 효율적이고 널리 사용되는 알고리즘 중 하나입니다.
동작 과정은 다음과 같습니다.
- 정렬할 리스트에서 임의의 원소를 선택하여 피벗(pivot)으로 지정합니다.
- 리스트를 둘로 분할합니다. 피벗보다 작은 값들은 왼쪽, 큰 값들은 오른쪽에 위치하도록 합니다.
- 분할된 왼쪽과 오른쪽 부분 리스트에 대해 재귀적으로 1, 2번 과정을 반복합니다.
- 더 이상 분할할 수 없을 때까지 반복하여 정렬을 완성합니다.
1, 2번 과정을 partition 단계라고 하며, 이를 어떻게 설정하느냐에 따라 성능 차이가 날 수 있습니다.
시간복잡도
평균적으로 O(n log n)
최악의 경우 O(n²). 피벗을 최솟값이나 최댓값으로 계속해서 잡게 되는 경우
공간복잡도
O(1)
특징
- 분할 정복 알고리즘
- 불안정 정렬
- 제자리 정렬
- 평균적인 상황에서 최고의 성능
- 피벗을 극단적으로 계속 잡게 되는 경우 최악의 성능
- partition 단계를 어떻게 설정하느냐에 따라 성능 차이가 날 수 있음
- 대규모 데이터 처리에 효과적
정렬 비교 사이트
아래 사이트에서 정렬 알고리즘이 어떻게 수행되는지를 확인할 수 있습니다.
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
마치며
이번 시간에는 효율적인 정렬 알고리즘에 대해 알아봤는데요.
이들은 구현이 비교적 복잡하지만, 시간복잡도가 O(n log n)으로 대규모 데이터 처리에 특히 효과적입니다.
퀵 정렬이 가장 많이 쓰이지만, partition 단계를 어떻게 설정하느냐에 따라 성능이 차이가 날 수 있습니다.
지적이나 다른 의견은 언제나 환영합니다 :D
감사합니다.
See also
JavaScript의 sort는 어떤 정렬 알고리즘을 사용할까?
References
https://en.wikipedia.org/wiki/Merge_sort
'Algorithm > Sort' 카테고리의 다른 글
| 정렬 알고리즘 알아보기 (1) - 기본 정렬 알고리즘 (0) | 2024.06.21 |
|---|