[정렬] 기수 정렬 | 계수 정렬 | 셸 정렬

목차

1. 기수 정렬

2. 계수 정렬

3. 셸 정렬

 

---

 

1. 기수 정렬 (Radix Sort)

  - 낮은 자리 수부터 정렬하는 방식  * 123 > 3(일의 자리)

  - 각 원소 간의 비교 연산을 하지 않아 빠른 대신, 기수 테이블을 위한 메모리 필요

  - 알고리즘 복잡도 : O(dn) *d : 최대 자릿수

 

 

2. 계수 정렬 (Counting Sort)

  - 숫자 끼리 비교하지 않고 카운트를 세서 정렬하는 방식

  - 카운팅을 위한 메모리 필요

  - 알고리즘 복잡도 : O(n + k)  *k : 정렬 대상 데이터 중 최대값

 

 

3. 셸 정렬 (Shell Sort)

  - 삽입 정렬의 약점을 보완한 정렬 방식

  - 삽입 정렬의 약점 : 오름차순 정렬 기준, 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 비교하며

                                  모두 교환 해야함

  - 이전의 모든 데이터와 비교하지 않고 일정 간격을 두어 비교

  - 알고리즘 복잡도 : O(n^2)