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

퀵 정렬 (루비) 2편

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

많은 도움 되셨나요?

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

댓글을 달아 주세요.

  1. 안녕하세요 코드 공부하는 학생입니다. 2019.08.12 14:25 Reply Address Modify/Delete Reply

    자료구조를 공부하다가 벤치마크 툴에 대해서 알게 되었는데요
    블로그 하실 위에서 루비로 테스트 하신 툴이 무엇인가요?
    몇 초 걸린지 나온 값이 어떻게 나온건가요?

Today 29    Yday 25    Tot 73,537
Juwan Park
Juwan Park's blog is powered by Daum and TISTORY.
Contemporary Blue for TISTORY.
Designed by Juwan Park. Creative Commons License
▲ TOP