기수정렬 (Radix Sort)

• 낮은 자리 수부터 정렬하는 방식
• 각 원소간의 비교 연산을 하지 않아 빠른 대신, 기수테이블을 위한 메모리 필요
• 시간 복잡도: $O(dn)$
• d: 최대자릿수
• Queue를 활용해 구현

계수정렬 (Counting Sort)

• 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식
• 카운팅을 위한 메모리 필요
• 시간 복잡도: $O(n+k)$
• k: 정렬대상 데이터 중 최대값

셸정렬 (Shell Sort)

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

삽입 정렬의 약점

오름차순 정렬 기준, 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 비교하며 모두 교환 필요

• 이전의 모든 데이터와 비교하지 않고 일정간격을 두어 비교
• 간격은 보통 배열길이의 절반부터 시작
• 시간복잡도: $O(n^2)$