퀵 정렬 (루비) 2편

루비로 퀵 정렬하기 1편에 이어서 포스팅합니다.

원래는 사용자 함수 형태로 정의했지만, 이 포스트에서는 배열 클래스 안에 사용자정의 메소드 형태로 정의하는 방법입니다.

다음 코드를 봅시다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Array   def quick_sort     return self if self.length <= 1     # 배열의 원소 개수가 0이거나 1이면 그냥 그대로 돌려줌     begin       pivot = (self.max + self.min) / 2       # 기준값을 최댓값과 최솟값의 중간으로 잡음     rescue       pivot = self[rand(self.length)]       # 예외 처리 발생시는 랜덤으로 함     end     less = Array.new       # 기준값보다 작은 원소들     equal = Array.new      # 기준값과 같은 원소들     greater = Array.new    # 기준값보다 큰 원소들     self.each do |x|       less    << x if x < pivot       equal   << x if x == pivot       greater << x if x > pivot     end     # 기준값보다 작은 원소들과 큰 원소들 재귀호출     return less.quick_sort + equal + greater.quick_sort   end       def quick_sort!     self.replace(self.quick_sort)   end end

살짝 바뀌었습니다. 한 번 실험해 보겠습니다.

?

29 30

arr = [7, 1, 4, 6, 10, 2, 14, 16, 13, 11, 15, 9, 12, 5, 8, 3] puts sprintf("%s", arr.quick_sort)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

의도하는 대로 돌아갑니다.

이번에는 이 알고리즘을 벤치마킹 돌려보겠습니다. 비교 대상은 교환식 퀵 정렬과 병합 정렬입니다.

                           user     system      total        real
quick_sort             0.203000   0.000000   0.203000 (  0.209756)
ex_quick_sort          2.184000   1.607000   3.791000 (  3.899742)
merge_sort             0.609000   0.015000   0.624000 (  0.621248)

5만개의 원소가 있는 배열을 100번 정렬했을 때의 벤치마킹입니다. 교환식 퀵 정렬은 원소가 많아지니 의외로 느립니다. 반면 병합식 퀵 정렬은 원소가 매우 많아짐에도 최상의 효율이 유지됩니다.

많은 도움 되셨나요?

유용한 정보로 활용하시기를 바랍니다.