링크는 위키피디아인데, pivot 을 부분집합의 맨 왼쪽으로 잡고 partitioning 을 한다.
하지만 책에는 pivot 을 부분집합의 중앙으로 잡는 방식으로 설명하고 있다.
그래서 아래 구현도 책을 따라간다.
Algorithm >>
quicksort(a[], begin, end)
if(m < n) then {
p <- partition(a, begin, end)
quicksort(a[], begin, p-1)
quicksort(a[], p+1, end)
}
end quicksort()
partition(a[], begin, end)
pivot <- (begin + end) / 2
L <- begin
R <- end
while(L < R) do {
while(a[L] < a[pivot] and L < R) do L++
while(a[R] >= a[pivot] and L < R) do R++
if(L < R) then swap a[L] and a[R]
}
swap a[pivot] and a[R]
return L
end partition()
소스 >>
# 퀵 정렬 구현
# 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 quick_sort(array, begin_idx, end_idx)
if(begin_idx < end_idx)
pivot_idx = partition(array, begin_idx, end_idx)
quick_sort(array, begin_idx, pivot_idx - 1)
quick_sort(array, pivot_idx + 1, end_idx)
end
end
def partition(array, begin_idx, end_idx)
pivot = (begin_idx + end_idx) / 2
left = begin_idx
right = end_idx
while(left < right)
left += 1 while( array[left] < array[pivot] && left < right )
right -= 1 while( array[right] >= array[pivot] && left < right )
swap_array_elem(array, left, right) if(left < right)
end
# left == right
swap_array_elem(array, pivot, right)
return right
end
array = make_example_array
quick_sort(array, 0, array.length - 1)
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/17 |
| 선택 정렬 & 버블 정렬 in Ruby (2) | 2009/03/17 |
| 그래프 탐색(깊이 우선 탐색, 너비 우선 탐색) - in Ruby (0) | 2009/03/16 |
| 인접 리스트로 구현한 Graph - in Ruby (2) | 2009/03/16 |
