Ch 06. 정렬 알고리즘 (2)

6.7 기수 정렬

개념

• 비교 정렬 X
• 자릿수별로 정렬
• 어느 비교정렬 알고리즘보다 빠르다
• 안정한 정렬
  • 입력 순으로 정렬
• LSD, MSD

과정

구현

• Pseudo code
  입력: n 개의 r진수의 k자리 숫자
  출력: 정렬된 숫자

RadixSort(L: list of unsorted items):
     largest := max(L)
     exponent := floor(log10(largest))
     bucket := empty list
     index := 0
     for i to exponent+1 do:
     	bucket := empty list
     	for j to length(L) do:
     		number := L[j]
        	digit := i+1
        	while(digit--) do:
          		temp := number % 10
          		number := floor(number-temp/10)
        	digit := temp
        	if bucket[digit] exists then
          		bucket[digit] := bucket[digit]
        	if bucket[digit] is undefined then
         		bucket[digit] := empty list
        	add L[j] to bucket[digit]
      	reset index to 0
      	for digit to length(bucket) do:
        	if bucket[digit] exists then
          		for j to length(bucket[digit])
            		L[index++] := bucket[digit][j]
  	return L
  	end-function

시간복잡도

$O(k(n+r))$
단, k 또는 r이 n보다 매우 작을 경우 $O(n)$

---

6.8 외부정렬

개념

• 입력 크기가 매우 커서 보조 기억 장치에 입력을 저장할 수밖에 없는 상태에서 수행되는 정렬
• 주기억장치에 수용 가능할 만큼의 데이터를 불러와서 정렬 후 다시 디스크에 저장
• 정렬된 블록으로 분할 -> 블록 2개씩 선택하여 합병 수행

과정

128GB 입력과 1GB의 주기억 장치 대한 ExternalSort의 수행 과정


1GB의 정렬된 블록 128개가 별도의 HDD에 저장된다.
2GB의 정렬된 블록 64개가 출력 HDD에 만들어진다.
4GB의 정렬된 블록 32개가 출력 HDD에 만들어진다.
8GB의 정렬된 블록 16개 출력 HDD에 만들어진다.
⋯
64GB의 정렬된 블록 2개가 출력 HDD에 만들어진다.
128GB의 정렬된 블록 1개가 출력 HDD에 만들어진다.

출력 HDD 리턴

시간복잡도

$O(log(N/M))$

• 기준 자체가 다르므로, 외부정렬과 내부정렬의 시간복잡도는 비교 불가능하다.