마찬가지로 현재 보고 있는 책의 연습문제이다.
버블 소트의 동작을 생각해 보면, 인근의 값을 비교하여 교환을 수행한다.
이미 정렬되어 있는 경우를 생각해보자.
a, b, c, d, e, f 가 정렬되어 있다면, a < b < c < d < e < f 이다.
다시 말하면... 첫 스텝 때 교환이 수행되지 않는다면, 배열은 이미 정렬되어 있다는 것이다.
몇 번째 스텝이라 해도 마찬가지이다.
스텝을 하나 적용했을 때, 나머지 부분이 이미 정렬되어 있다면 다음 스텝에서는 교환이 수행되지 않을 것이다.
그렇다면 차후 스텝은 의미가 없다.
이를 적용한 소스는 다음과 같다.
array 를 [1,2,6,3,4,5] 로 변경하면 '.' 은 총 9번(5번 + 4번) 출력되고 정렬이 완료된다.
이미 정렬되어 있는 경우, 필요 없는 비교를 수행하지 않고 함수를 종료할 수 있도록 BubbleSort 를 수정하세요
버블 소트의 동작을 생각해 보면, 인근의 값을 비교하여 교환을 수행한다.
이미 정렬되어 있는 경우를 생각해보자.
a, b, c, d, e, f 가 정렬되어 있다면, a < b < c < d < e < f 이다.
다시 말하면... 첫 스텝 때 교환이 수행되지 않는다면, 배열은 이미 정렬되어 있다는 것이다.
몇 번째 스텝이라 해도 마찬가지이다.
스텝을 하나 적용했을 때, 나머지 부분이 이미 정렬되어 있다면 다음 스텝에서는 교환이 수행되지 않을 것이다.
그렇다면 차후 스텝은 의미가 없다.
이를 적용한 소스는 다음과 같다.
def print_array(array)위와 같이 완전히 정렬된 6개의 원소를 가진 배열을 정렬하면 '.' 은 총 5번만 출력된다.
puts array.map {|x| x.to_s + " "}.to_s
end
def bubble_sort(array)
array_len = array.length
(0..array_len - 1).each do |i|
flag = nil
(0..array_len - (i+2)).each do |j|
puts "."
if array[j] > array[j+1]
array[j], array[j+1] = array[j+1], array[j]
flag = true
end
end
return if !flag
end
end
array_sorted = [1,2,3,4,5,6]
bubble_sort(array_sorted)
print_array(array_sorted)
array 를 [1,2,6,3,4,5] 로 변경하면 '.' 은 총 9번(5번 + 4번) 출력되고 정렬이 완료된다.
'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 |
