📝 퀵 정렬이란?
하나의 pivot(축, 기준점)을 정해서 pivot보다 작은 값은 왼쪽에 큰값은 오른쪽에 위치시키면서 정렬하는 방법이다.
🎯 퀵 정렬의 특징
- 분할 정복 기법 사용한다.
- 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
- 분할된 두 개의 작은 배열에 대해 재귀적으로 과정을 반복한다.
- Big O => Best Case: O(NlogN) / Worst Case: O(n^2)
✔ O(N^2)이 나오는 경우는 매우 희박하기 때문에 보통 O(NlogN)으로 취급한다.
📈 퀵 정렬의 장점
- 속도가 매우 빠른 정렬 알고리즘이다.
- 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환한다.
- in place 알고리즘이기 때문에 메모리가 절약한다.
📉 퀵 정렬의 단점
- Unstable 정렬이다.
- 최악의 경우 시간 복잡도는 O(N^2)이다.
✔ O(N^2) 경우는 거의 정렬되거나 이미 정렬된 데이터를 정렬할 때 이다.
📝 합병 정렬이란?
하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 정렬하는 방법이다.
🎯 합병 정렬의 특징
- 일반적인 방법으로 구현했을 때 이 정렬은 안정정렬 에 속하며, 분할 정복 알고리즘의 하나 이다.
- 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다.
- O(nlogn)의 시간복잡도를 보장한다.
합병 정렬의 단계
1. 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
2. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
3. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.
📈 합병 정렬의 장점
- 안정적인 정렬 방법이다.
- 데이터가 무엇이든 정렬되는 시간은 동일하다
- 연결 리스트로 구성하면 제자리 정렬(in-place sorting)로 구현할 수 있다.
- 크기가 큰 레코드를 정렬할 경우 연결리스트를 사용하면 다른 정렬 방법보다 효율적이다.
📉 합병 정렬의 단점
- 레코드를 배열로 구성하면 임시 배열이 필요하다.
- 레코드들의 크기가 큰 경우 이동 횟수가 많으므로 시간적으로 낭비된다.
📝 힙 정렬이란?
완전 이진트리에서 파생된 힙의 특성을 사용하여 정렬하는 알고리즘으로 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성한다.
🎯 힙 정렬의 특징
- 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다.
- 힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때이다.
- O(nlogn)의 시간복잡도를 보장한다.
힙 정렬의 과정
- n개의 노드에 대한 완전 이진 트리를 구성한다. 순서는 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다.
- 최대 힙을 구성한다.
- 루트노드를 가장 끝의 노드와 교환한다.
- 2번과 3번을 반복한다.
📈 힙 정렬의 장점
- 추가적인 배열이 필요하지 않아 메모리가 절약된다.
📉 힙 정렬의 단점
- 데이터의 순서를 보장하지 못하는 불안정(unstable)정렬이다.
참고자료
도라에몽 암기빵