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

퀵 정렬 (루비) 1편

★프로그래밍/Ruby :: 2016.08.25 22:35

루비로 퀵 정렬 알고리즘을 구현한 예제입니다.

여기서는 기존의 교환식 퀵 정렬 대신 병합식 퀵 정렬로 구현하였습니다. 이는 퀵 정렬에 병합 정렬 알고리즘을 접목시킨 것으로, 교환식 퀵 정렬의 단점이었던 불안정성(정렬 키 값이 같은 데이터끼리 순서가 정렬 후 서로 바뀔 수 있는 성질)을 해소하였습니다.

코드는 다음과 같습니다.

def quick_sort(a, randompivot = true)
  return a if a.length <= 1
  # 배열의 원소 개수가 0이거나 1이면 그냥 그대로 돌려줌
  pivot = a[randompivot ? rand(a.length) : 0]
  # 기준값을 랜덤으로 혹은 첫 번째 원소로 잡음
  less = Array.new       # 기준값보다 작은 원소들
  equal = Array.new      # 기준값과 같은 원소들
  greater = Array.new    # 기준값보다 큰 원소들
  a.each do |x|
    less    << x if x < pivot
    equal   << x if x == pivot
    greater << x if x > pivot
  end
  # 기준값보다 작은 원소들과 큰 원소들 재귀호출
  return quick_sort(less, randompivot) + equal + quick_sort(greater, randompivot)
end

3개의 소배열을 만든 후 원래 배열에서 처음부터 하나씩 훑어 기준값보다 작은 값, 같은 값, 큰 값으로 분류하여 소배열에 순서대로 하나씩 추가하고 그 소배열을 작은 - 같은 - 중간 순서로 병합합니다. 물론 여기서 작은 값 소배열과 큰 값 소배열을 인자로 재귀호출하여 정렬시킵니다.

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

실험해 보면,

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

제대로 돌아감을 확인할 수 있습니다.

만약 숫자만 정렬한다면, 코드를 다음과 같이 바꿀 수도 있습니다.

def quick_sort(a)
  return a if a.length <= 1
  # 배열의 원소 개수가 0이거나 1이면 그냥 그대로 돌려줌
  pivot = (a.max + a.min) / 2
  # 기준값을 최댓값과 최솟값의 중간으로 잡음
  less = Array.new       # 기준값보다 작은 원소들
  equal = Array.new      # 기준값과 같은 원소들
  greater = Array.new    # 기준값보다 큰 원소들
  a.each do |x|
    less    << x if x < pivot
    equal   << x if x == pivot
    greater << x if x > pivot
  end
  # 기준값보다 작은 원소들과 큰 원소들 재귀호출
  return quick_sort(less) + equal + quick_sort(greater)
end

병합식은 교환식과는 달리 기준값이 원래 배열 안에 없어도 됩니다. 교환식에서는 기준값이 원래 배열에 없으면 안 되지만 병합식에서는 이 경우 단지 기준값과 같은 값을 저장하는 소배열이 비게 될 뿐 정상적으로 동작합니다. (교환식에서도 원래 배열에 없는 기준값으로도 정렬 가능한 알고리즘을 구현할 수 있어 정정합니다.) 퀵 정렬의 문제점 중 하나가 예를 들어 배열이 [7, 1, 5, 3] 이런 식일 때 기준값을 7로 잡고 그 다음은 기준값을 1로 잡는 식으로 기준값을 최댓값이나 최솟값으로만 잡아서 재귀호출 깊이가 그만큼 깊어지고 효율이 크게 떨어지는 매우 안 좋은 경우가 있는데 이 방법으로 하면 기준값을 언제나 최댓값과 최솟값의 중간으로 취하기 때문에 이런 극단적인 경우가 일어나지 않습니다.

이렇게 루비의 배열 원소 삽입/삭제 메소드를 이용하여 병합식 퀵 정렬을 손쉽게 구현할 수 있습니다.

많은 도움 되셨나요?

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

Today 0    Yday 48    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