@ 퀵 정렬 - in Ruby
현재 보고 있는 책에 연습문제로 나와서 한 번 풀어 보았다.
퀵 정렬에서 partition() 이 pivot 을 결정할 때 최악의 경우를 피하도록 개선하시오
참고로 퀵 정렬에서 최악의 경우는 partition() 을 호출할 때 피벗을 중심으로 계속 1:n-1 개의 집합으로 나뉘는 것이다.
전체의 median 을 구해서 pivot 을 구하면 되겠네... 라고 생각했는데 정렬이 선행되기 때문에 불가능하고...
최악의 경우만 피하면 되므로 맨 앞의 값 중 3개만 뽑아서 median 을 pivot 으로 잡는다.
그러면 최악의 경우까지는 피할 수 있다.(그래도 간신히 최악을 피할 수도 있음...;;)
def get_sample_median_index(array, begin_idx, end_idx)
# 3개가 되지 않으면(2개, 1개) 맨 처음 인덱스를 리턴
return begin_idx if end_idx - begin_idx < 2
idx_arr = []
(0..2).each { |i| idx_arr[i] = begin_idx + i }
value_arr = []
(0..2).each { |i| value_arr[i] = array[begin_idx + i] }
# 셀렉션 소트로 값을 기준으로 정렬하되 인덱스 정보도 같이 정렬해야 한다
(0..1).each do |i|
min_idx = i
(i+1..2).each do |j|
min_idx = j if value_arr[min_idx] > value_arr[j]
end
if min_idx != i
value_arr[i], value_arr[min_idx] = value_arr[min_idx], value_arr[i]
idx_arr[i], idx_arr[min_idx] = idx_arr[min_idx], idx_arr[i]
end
end
return idx_arr[1]
end
위의 메소드를 pivot 결정할 때 사용한다.
'Dev.Programming > DS/Algorithm' 카테고리의 다른 글
| 기수교환 정렬(Radix Exchange Sort) (0) | 2009/08/07 |
|---|---|
| 버블 정렬 개선 - 이미 정렬되어 있는 경우 최소한의 비교로 정렬을 종료하기 (2) | 2009/05/11 |
| 퀵 정렬 개선 - median 을 이용한 pivot 결정하기 (0) | 2009/05/11 |
| 분리 집합 (0) | 2009/05/11 |
| 수식 트리 in Ruby (4) | 2009/05/11 |
| Backtracking : N-Queen Problem (2) | 2009/05/07 |
