💡 기수 정렬 (Radix Sort)
👉 낮은 자리 수부터 정렬하는 방식 (1의 자리, 10의 자리, 100의 자리 등)
👉 각 원소 간의 비교 연산을 하지 않아 빠른 대신, 기수 테이블 (Queue) 을 위한 메모리가 필요하다.
👉 알고리즘 복잡도 : O(dn) (d : 최대 자리수)
💡 기수 정렬 과정
- 배열의 원소들의 1의 자리수를 먼저 비교해서 Queue로 구현한 기수 테이블에 자리수별로 Queue에 넣어준다.
- 0번부터 9번까지 dequeue 시켜줘서 꺼내준다.
- 10의 자리수를 기준으로 똑같이 inqueue 한 후 0번부터 9번까지 dequeue 시켜줘서 정렬한다.
💡 계수 정렬 (Counting Sort)
👉 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식이다.
👉 카운팅을 위한 카운팅 테이블 (Array) 메모리가 필요하다.
👉 알고리즘 복잡도 : O(n + k) (k : 정렬 대상 데이터 중 최대값)
💡 계수 정렬 과정
- Array 로 구현한 카운팅 테이블에 각 원소들을 돌면서 개수를 세어준다.
- Array 0번부터 돌면서 배열에 저장해서 정렬해준다.
💡 셸 정렬 (Shell Sort)
👉 삽입 정렬의 약점을 보완한 정렬 방식이다.
👉 삽입 정렬의 약점
- 오름차순 정렬 기준, 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 비교하며 모두 교환해야 한다.
👉 이전의 모든 데이터와 비교하지 않고 일정 간격을 두고 비교한다.
👉 알고리즘 복잡도 : O(n²)
간격 설정에 따라 Worst Case는 삽입 정렬과 동일하다.
일반적인 산포 데이터 기준으로는 삽입 정렬에 비해 빠르다.
💡 셸 정렬 과정
- 0번부터 Gap을 두고 비교하여 삽입 정렬해준다. (Gap = 배열 길이 / 2)
- 한번 정렬할 때마다 Gap을 2로 나눠 좁은 간격으로 비교해서 삽입 정렬해준다.
💡 정렬 알고리즘 복잡도 Summary
| 정렬 방법 | 시간 복잡도 (O(n)) | 보조 메모리 | 안정성 |
|---|---|---|---|
| 버블 정렬 | n² | 1 | o |
| 삽입 정렬 | n² | 1 | o |
| 선택 정렬 | n² | 1 | x |
| 합병 정렬 | nlogn | n | o |
| 힙 정렬 | nlogn | 1 | x |
| 퀵 정렬 | n² | nlogn | x |
| 트리 정렬 | n² | n | x |
| 기수 정렬 | dn | n+k | o |
| 계수 정렬 | n+k | n+k | o |
| 셸 정렬 | n² | 1 | x |
- d : 정렬 대상 데이터 최대 자리수
- k : 정렬 대상 데이터 중 최대값
- 보조 메모리가 1인 정렬들은 제자리 정렬 (in-place 정렬) 이 가능한 정렬이다.
- 코딩 테스트에서 in-place로 문제를 풀라고 하거나, 일부 컨스턴스 메모리를 제외한 메모리를 추가로 사용하지 말라고 하면 n, nlogn, n+k 가 필요한 정렬을 피해서 풀어야한다.
- 안정한 정렬은 정렬 후 값의 자리가 바뀌지 않는 경우이다.
BE