병합 정렬 (루비)

루비에서 병합 정렬 알고리즘을 구현한 예제입니다.

우선 병합 정렬의 개념에 대해 먼저 설명드리자면, 정렬을 수행한 데이터를 반씩 쪼갠 다음 정렬 과정에서 다시 붙여나가는 정렬 방식입니다.

예를 들어, 배열 [4, 1, 2, 3]이 있다고 합시다. 그러면...

1. 이 배열을 정렬하기 위해 반으로 쪼개 [4, 1] [2, 3]으로 만듭니다.
2. 그리고 [4, 1]을 다시 쪼개 [4] [1]로 만들면,
3. [4]는 원소가 하나이므로 더는 쪼갤 수 없고 [1]도 마찬가지로 더는 쪼갤 수 없습니다. 그러므로 이 둘의 값을 비교하여 정렬합니다. 1이 4보다 작으므로 당연히 1이 앞에 옵니다. 정렬되면서 4와 1로 쪼개진 게 다시 [1, 4]로 합쳐졌습니다.
4. 위 1번에서 쪼갠 나머지 반쪽인 [2, 3]도 위 2번~3번과 같은 방법으로 처리합니다. 그러면 당연히 [2, 3]이 되겠지요.
5. 이제 [1, 4]와 [2, 3]을 맨 앞의 값을 비교하면서 다시 합칩니다. 먼저 1<2이므로 1을 집어넣고, 4>2이므로 2를 집어넣습니다. 그리고 4>3이므로 3을 집어넣고 마지막 남은 4까지 집어넣으면 [1, 2, 3, 4] 이렇게 정렬됩니다.

이게 뭔 소린지 모르겠다는 분들이 계실까봐 움짤을 첨부하자면...

이런 식으로 돌아가는 정렬 알고리즘이라고 보시면 됩니다.

이 알고리즘을 루비로 구현하면 다음과 같이 됩니다.

def merge_sort(a)
  return a if a.length <= 1
  # 배열의 원소 개수가 0이거나 1이면 그냥 그대로 돌려줌

  half = a.length / 2    # 배열 개수의 절반 (소수점 버림)
  # half 변수 값을 기준으로 좌우로 나누고 재귀호출
  l = merge_sort(a[0..(half - 1)])           # 왼쪽을 추출
  r = merge_sort(a[half..(a.length - 1)])    # 오른쪽 추출
  mer = Array.new       # 결과를 저장하기 위한 빈 배열
  while l.length > 0 && r.length > 0 do
    # 왼쪽과 오른쪽에 모두 남아있는 원소가 있으면
    if l[0] > r[0]      # 왼쪽이 크면
      mer << r[0]       # 오른쪽 0번 원소를 집어넣고
      r.delete_at(0)    # 그 원소는 삭제
    else                # 그 외에는
      mer << l[0]       # 왼쪽 0번 원소를 집어넣고
      l.delete_at(0)    # 그 원소는 삭제
    end
  end
  # 마지막 남은 원소들도 모두 넣음
  mer += l if l.length > 0
  mer += r if r.length > 0
  return mer    # 최종 결과값을 돌려줌
end

그리고 다음과 같이 실제로 실행해 보면,

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

다음과 같습니다.

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

제대로 돌아갑니다.

이 알고리즘은 배열의 원소 개수가 2ⁿ개가 아니더라도 정상적으로 작동합니다. 루비에서는 그냥 나눗셈을 하더라도 정수÷정수는 소수점 이하가 그대로 버려지기에 저렇게 코딩해도 문제는 없습니다.

여기서 주의할 점이라면 왼쪽과 오른쪽의 키 값이 중복일 경우 왼쪽을 넣도록 해야 한다는 점입니다. 병합 정렬의 장점 중 하나가 정렬의 안정성인데, 키 값이 같은 원소에 대해 오른쪽 값을 우선하게 되면 정렬 전과 순서가 뒤바뀌어 불안정 정렬이 되는 상황이 발생할 수도 있기 때문입니다. 그렇기 때문에 키 값이 같은 원소에 대해서는 왼쪽 값을 우선해야 합니다.

많은 도움 되셨나요?

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