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

퀵 정렬 (루비) 1편

★프로그래밍/Ruby :: 2016. 8. 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 27    Yday 25    Tot 73,535
Juwan Park
Juwan Park's blog is powered by Daum and TISTORY.
Contemporary Blue for TISTORY.
Designed by Juwan Park. Creative Commons License
▲ TOP