[자료구조] 1201 (1)

12. 정렬

1. 정렬이란?
2. 선택 정렬
3. 삽입 정렬
4. 버블 정렬
5. 셸 정렬
6. 합병 정렬
7. 퀵 정렬
8. 히프 정렬
9. 기수 정렬
10. 정렬 알고리즘의 비교

 

---

12.9 기수 정렬 (Radix Sort)

: 레코드를 비교하지 않고 정렬을 수행한다.

• 시간 복잡도: O(dn) --> n*log(n)을 능가하는 빠른 정렬 방법!
  - d: 자릿수

 

한자릿수 기수정렬

두자릿수 기수정렬

: 낮은 자릿수 먼저 분류한 다음, 순서대로 읽어서 다시 높은 자릿수를 분류한다.

--> 뒷자리가 정렬되었기 때문에, 앞자리 정렬로 전체 정렬이 가능하다.

• 버킷(추가 공간): 큐로 구현한다.

 

기수정렬 프로그램

• factor: 몇 번째 자릿수를 추출할지 결정한다.

 

---

12.10 정렬 알고리즘의 비교

정렬 알고리즘들의 복잡도 비교

 

---

 

 

 

 

 

출처: 이화여자대학교 이숙영교수님 자료구조