Juwan Park :: 퀵 정렬 (루비) 2편

퀵 정렬 (루비) 2편

★프로그래밍/Ruby :: 2016.08.26 16:04

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

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

다음 코드를 봅시다.

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

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

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번 정렬했을 때의 벤치마킹입니다. 교환식 퀵 정렬은 원소가 많아지니 의외로 느립니다. 반면 병합식 퀵 정렬은 원소가 매우 많아짐에도 최상의 효율이 유지됩니다.

많은 도움 되셨나요?

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

Today 48    Yday 46    Tot 56,858
Juwan Park
Juwan Park's blog is powered by Daum and TISTORY.
Contemporary Blue for TISTORY.
Designed by Juwan Park. Creative Commons License
▲ TOP