이 포스트는 루비로 퀵 정렬 알고리즘을 구현한 포스트입니다.
필자의 티스토리 블로그에도 퀵 정렬 알고리즘을 구현한 포스트가 있지만 여기서는 조금 개량한 코드를 서술합니다.
def quick_sort(a, desc = false , randompivot = true) return a if a.length <= 1 # only 2 or more begin pivot = (a.max + a.min) / 2 rescue pivot = a[randompivot ? rand(a.length) : a.length / 2] end less = Array.new # less than pivot equal = Array.new # equal to pivot greater = Array.new # greater than pivot a.each do |x| less << x if x < pivot equal << x if x == pivot greater << x if x > pivot end # recursion if desc return quick_sort(greater, true, randompivot) + equal + quick_sort(less, true, randompivot) else return quick_sort(less, false, randompivot) + equal + quick_sort(greater, false, randompivot) end end
파이썬으로 퀵 정렬 알고리즘 구현하기 포스트에서 구현한 알고리즘과 구조가 같습니다.
2번 줄에서 배열 크기를 검사합니다. 배열 크기가 1 이하일 경우 그냥 그 배열을 돌려주고 2 이상일 경우 다음 코드로 갑니다. 배열을 쪼개면서 재귀하는 특성상 배열 크기가 1 이하일 때 재귀를 멈춰야 하므로 필수로 넣어야 하는 부분입니다.
3번 줄부터 7번 줄까지가 기준값 잡는 코드입니다. 4번 줄은 배열의 최댓값과 최솟값의 중간값으로 기준값을 잡는 코드입니다. 만약 수치배열이 아닐 경우 오류가 일어나므로 이 때는 예외처리로 6번 줄로 넘어갑니다. 6번 줄에서는 기준값을 랜덤으로 잡거나 배열의 중간 값으로 잡습니다.
8번 줄부터 10번 줄까지는 기준값보다 작은 값, 기준값과 같은 값, 기준값보다 큰 값이 각각 들어갈 배열을 선언합니다.
11번 줄부터 15번 줄까지가 배열의 크기만큼 반복하는 반복문입니다. 각 배열의 원소를 하나씩 추출해서 그 값을 기준값과 비교한 다음 맞는 배열에 대입합니다.
17번 줄부터 21번 줄까지는 기준값보다 작은 값 배열과 큰 값 배열에 대해 재귀호출하면서 작은 값, 같은 값, 큰 값 배열을 합친 배열을 돌려줍니다. 만약 내림차순 옵션을 true로 주었다면 큰 값 – 같은 값 – 작은 값 순서대로 합치고 그 외에는 당연히 작은 값 – 같은 값 – 큰 값 순서대로 합칩니다.
이제 이 함수를 실험해 봅시다.
arr = [7, 1, 4, 6, 10, 2, 14, 16, 13, 11, 15, 9, 12, 5, 8, 3]
puts sprintf(" Unsorted: %s", arr)
puts sprintf(" Ascending: %s", quick_sort(arr) )
puts sprintf("Descending: %s", quick_sort(arr, true) )
정렬되지 않은 배열을 세팅한 다음 정렬 함수를 오름차순과 내림차순으로 실행해 보면,
Unsorted: [7, 1, 4, 6, 10, 2, 14, 16, 13, 11, 15, 9, 12, 5, 8, 3] Ascending: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] Descending: [16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
정렬된 배열이 출력됩니다.
이와 같이 루비에서도 퀵 정렬 알고리즘을 구현해 볼 수 있습니다.