Juwan Park :: 병합 정렬 (루비)

병합 정렬 (루비)

★프로그래밍/Ruby :: 2016.08.25 12:36

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

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

예를 들어, 배열 [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]

제대로 돌아갑니다.

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

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

많은 도움 되셨나요?

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

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