셸 정렬은 일정한 간격으로 떨어져 있는 자료들끼리 부분집합을 구성하고 이들을 삽입 정렬로 정렬한 다음, 간격을 계속 반으로 줄여 간격이 0 이 될 때까지 부분집합을 정렬하는 과정을 반복한다. 이 때, 첫 간격은 원소 개수의 1/2 로 잡는다.
한 단계만 예로 들자면, 69 10 30 2 16 8 31 22 의 경우 첫 간격은 8 / 2 = 4 가 되고 {69, 16} / {10, 8} / {30, 31} / {2, 22} 가 부분집합의 쌍이 된다. 이를 각각 정렬하면 16 8 30 2 69 10 31 22 가 되고, 다음 간격은 4 / 2 = 2 가 된다. 이를 반복하는 것이다.
셸 정렬은 삽입 정렬의 아래와 같은 성질을 이용하고 보완한 일반화라고 할 수 있다.
- 삽입 정렬은 입력되는 초기리스트가 "거의 정렬"되어 있을 경우 효율적이다.
- 삽입 정렬은 한 번에 한 요소의 위치만 결정되기 때문에 비효율적이다.
셸 정렬은 마지막 간격이 1이 될 때 전체에 대해 삽입 정렬을 수행하게 되는데, 이미 삽입 정렬의 성질에 적합하게 정리되어 있기 때문에 효율적인 정렬이 된다.
Pseudocode >>
shellSort(a[], n)
interval <- n
while(interval >= 1) do {
interval <- interval / 2
for(i <- 0 ; i < interval ; i <- i + 1) do {
intervalSort(a[], i, n, interval)
}
}
end shellSort()
intervalSort(a[], begin, end, interval)
for(i <- begin+interval ; i < end ; i <- i+interval) do {
item <- a[i]
for(j <- i - interval ; j >= begin && item < a[j] ; j <- j-interval) do {
a[j+interval] <- a[j]
}
a[j+interval] <- item
}
end intervalSort()
소스 >>
# 셸 정렬 구현
# 2009-03-17, Jung-taek Lim(Heart)
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 shell_sort(array)
interval = array.length
while(interval >= 1)
interval /= 2
(0...interval).each do |i|
interval_sort(array, i, interval)
end
end
end
def interval_sort(array, begin_idx, interval)
(begin_idx + interval).step(array.length - 1, interval) do |i|
item = array[i]
j = i - interval
while(j >= begin_idx && item < array[j])
array[j + interval] = array[j]
j = j - interval
end
array[j + interval] = item
end
end
array = make_example_array
shell_sort array
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/17 |
| 선택 정렬 & 버블 정렬 in Ruby (2) | 2009/03/17 |
