퀵 정렬 (루비) 2편

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

많은 도움 되셨나요?

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