원소의 순서대로 n 번째 자릿수 에 맞게 버킷(큐)에 넣고, 버킷에서 차례대로 빼면 정렬이 된다.
가장 큰 수의 자릿수 개수만큼 수행한다.
설명을 글로 쓰고 나니 쉬운 내용을 돌아가는 것 같아서 예시로 설명한다.
ex) 69, 10, 30, 2, 16, 8, 31, 22
기수 = 10, 최대 자릿수 = 2
1> 1의 자리
0 / 10, 30
1 / 31
2 / 2, 22
3 /
4 /
5 /
6 / 16
7 /
8 / 8
9 / 69
=> 10, 30, 31, 2, 22, 16, 8, 69
2> 10의 자리
0 / 2, 8
1 / 10, 16
2 / 22
3 / 30, 31
4 /
5 /
6 / 69
7 /
8 /
9 /
=> 2, 8, 10, 16, 22, 30, 31, 69
Pseudocode >>
radixSort(a[], n)
for(k <- 1 ; k <= n ; k <- k+1) do {
for(i <- 0 ; i < n ; i <- i+1) do {
k 번째 자릿수 값에 따라서 버킷에 저장
enqueue(Q[k], a[i])
}
p <- -1
for(i <- 0 ; i <= 9 ; i <= i+1) do {
while(Q[i] != NULL ) do {
p <- p+1
a[p] <- dequeue(Q[i])
}
}
}
end radixSort()
소스 >>
# 기수 정렬 구현
# 2009-03-18, Jung-taek Lim(Heart)
require 'circular_queue'
def swap_array_elem(array, idx1, idx2)
temp = array[idx1]
array[idx1] = array[idx2]
array[idx2] = temp
end
def make_example_array
array = [69, 10, 30, 2, 16, 8, 31, 22]
end
def print_array(array)
puts array.map {|x| x.to_s + " "}.to_s
end
def radix_sort(arr, radix)
radix_queue = []
(0..9).each { |i| radix_queue[i] = CircularQueue.new(arr.length + 1) }
# 원소 중 계산할 자릿수가 아직 남았는지 확인
quotient_sum = 1
# 나눌 수
mod_value = 10
while( quotient_sum > 0 )
quotient_sum = 0
arr.each do |element|
quotient, remainder = element.divmod(mod_value)
quotient_sum += quotient
positional_number = remainder / (mod_value / 10)
radix_queue[positional_number].enqueue(element)
end
p = 0
(0..9).each do |i|
until radix_queue[i].is_empty
arr[p] = radix_queue[i].dequeue
p += 1
end
end
mod_value *= 10
end
end
array = make_example_array
radix_sort array, 10
print_array array
|
결과 >>
2 8 10 16 22 30 31 69
'Dev.Programming > DS/Algorithm' 카테고리의 다른 글
| 트리 정렬 - in Ruby (0) | 2009/03/18 |
|---|---|
| 힙 정렬 - in Ruby (0) | 2009/03/18 |
| 기수 정렬 - in Ruby (0) | 2009/03/18 |
| 병합 정렬 - in Ruby (0) | 2009/03/18 |
| 셸 정렬 - in Ruby (0) | 2009/03/18 |
| 삽입 정렬 - in Ruby (0) | 2009/03/18 |
