Ruby로 병합 정렬 살펴보기

이것은 Ruby로 다양한 정렬 알고리즘을 구현하는 방법을 살펴보는 시리즈의 3부입니다. 1부에서는 버블 정렬을 살펴보고 2부에서는 선택 정렬을 살펴보았습니다.

이 시리즈의 이전 게시물에서 논의한 것처럼 데이터 정렬 방법을 이해하는 것은 소프트웨어 엔지니어의 툴킷에서 없어서는 안될 부분입니다. 운 좋게도 Ruby와 같은 대부분의 고급 언어에는 배열을 정렬하는 데 효율적인 메서드가 이미 내장되어 있습니다. 예를 들어 .sort를 호출하면 배열에서 후드 아래에서 퀵 정렬을 사용하고 있습니다. 이 포스트에서 우리는 퀵 정렬과 유사한 알고리즘인 병합 정렬을 배울 것입니다. 이 두 알고리즘 모두 "분할 및 정복 접근"을 사용합니다. 병합 정렬은 1945년 John von Neumann에 의해 발명되었습니다. Von Neumann은 Manhattan Project, "mini-max" 정리, Monte Carlo 방법 등을 연구한 것으로도 알려진 유명한 컴퓨터 과학자이자 물리학자입니다.

높은 수준에서 병합 정렬 알고리즘은 하나의 요소만 남을 때까지 배열을 두 개의 하위 배열로 반복해서 분할합니다(재귀 사용). 거기에서 요소는 다시 "병합"되어 최종 정렬된 배열을 형성합니다. 버블 정렬 및 기타 유사한 알고리즘과 달리 병합 정렬은 시각화 없이는 이해하기 어렵습니다. 다음 다이어그램은 병합 정렬의 작동 방식을 보여주는 Wikipedia의 단계별 그림입니다. 그러나 무슨 일이 일어나고 있는지 여전히 약간 모호하더라도 걱정하지 마십시오. 다음에 코드를 살펴보겠습니다.

우리가 이전에 논의한 알고리즘(즉, 버블 및 선택)과 달리 기본적으로 실제 작업에는 비현실적이지만 병합 정렬은 Big-O 표기법 측면에서 훨씬 더 잘 수행됩니다. Big-O 표기법에 익숙하지 않은 경우 다른 알고리즘의 최악의 성능을 나타냅니다. 이를 통해 Big-O를 기반으로 알고리즘을 쉽게 비교할 수 있습니다. 예를 들어 Big-O가 O(1)인 알고리즘은 최악의 경우 런타임이 요소 수 "n"이 증가함에 따라 일정함을 의미하는 반면 Big-O 표기법이 O( n) 최악의 경우 런타임은 n이 증가함에 따라 선형적으로 증가함을 의미합니다. 이것은 100개의 요소가 있는 배열이 있고 O(n) 및 O(1)인 정렬 알고리즘 중에서 선택해야 하는 경우 O(1)이 O(100)보다 확실히 우수하기 때문에 O(1) 알고리즘을 선택한다는 것을 의미합니다. 버블 및 선택 정렬 알고리즘은 모두 최악의 경우 O(n^2)입니다. 이것은 요소 수가 증가함에 따라 알고리즘이 매우 느리게 수행된다는 것을 의미하기 때문에 그다지 유용하지 않습니다. 대조적으로, 병합 정렬은 n log(n)에서 수행되며, 이는 알고리즘이 버블 또는 선택 정렬만큼 효율성을 희생하지 않는다는 것을 의미합니다.

다이어그램의 예를 살펴보겠습니다. [38, 27, 43, 3, 9, 82, 10] 배열로 시작합니다. 그런 다음 단일 요소가 남을 때까지 배열을 반으로 나눕니다.

1. 시작 배열을 두 부분으로 나눕니다. [38, 27, 43, 3] 및 [9, 82, 10] .
2. 전반부를 다시 분할합니다. [38, 27] 및 [43, 3] .
3. 상반부를 단일 요소로 나눕니다. [38] , [27] , [43] , 및 [3] .
4. 38과 27을 정렬하여 [27, 38] 48과 3을 사용하여 [3, 43] .
5. 이것을 합치면 [3, 27, 38, 43]이 됩니다. .
6. 이제 [9, 82, 10]인 원래 배열의 후반으로 이동합니다. . 우리는 그것을 반으로 나누고 [9, 82]를 얻습니다. 및 [10] .
7. [9, 82]를 나눕니다. [9]로 및 [82] , 그리고 [10] , 이미 단수입니다.
8. [9, 82]를 정렬합니다. 다시 합친 다음 [10] 병합 다시 입력하면 [9, 10, 82]가 됩니다. .
9. 마지막으로 [3, 27, 38, 43]를 병합합니다. 및 [9, 10, 82] [3, 9, 10, 27, 38, 43, 82]를 얻으려면 .

루비 구현

다음은 Ruby로 작성된 병합 정렬 알고리즘입니다.

class MergeSort
  def sort(numbers)

    num_elements = numbers.length
    if num_elements <= 1
      return numbers
    end

    half_of_elements = (num_elements / 2).round

    left  = numbers.take(half_of_elements)
    right = numbers.drop(half_of_elements)

    sorted_left = sort(left)
    sorted_right = sort(right)

    merge(sorted_left, sorted_right)
  end

  def merge(left_array, right_array)
    if right_array.empty?
      return left_array
    end

    if left_array.empty?
      return right_array
    end

    smallest_number = if left_array.first <= right_array.first
      left_array.shift
    else
      right_array.shift
    end

    recursive = merge(left_array, right_array)

    [smallest_number].concat(recursive)
  end
end

여기서 무슨 일이 일어나고 있는지 살펴보겠습니다. 먼저 sort 방법은 상단에 있습니다.

  def sort(numbers)

    num_elements = numbers.length
    if num_elements <= 1
      return numbers
    end

    half_of_elements = (num_elements / 2).round

    left  = numbers.take(half_of_elements)
    right = numbers.drop(half_of_elements)

    sorted_left = sort(left)
    sorted_right = sort(right)

    merge(sorted_left, sorted_right)
  end

코드의 이 부분의 목표는 각각에 하나의 항목만 남을 때까지 주어진 숫자를 반으로 나누는 것입니다. 작동하는 모습을 보려면 마지막 줄(merge(sorted_left, sorted_right))을 주석 처리하고 대신 sorted_left를 출력하세요. 및 sorted_right . 예제 배열을 전달하여 프로그램을 실행하면 터미널에 다음이 표시되어야 합니다.

merge_sort = MergeSort.new
puts merge_sort.sort([38, 27, 43, 3, 9, 82, 10])

ruby ruby-merge-sort.rb

27
43
38

3
9
82
10

엄청난! 우리 코드는 초기 배열을 가져와 반으로 나눴습니다. merge을 살펴보겠습니다. 다음 코드의 일부입니다.

  def merge(left_array, right_array)
    if right_array.empty?
      return left_array
    end

    if left_array.empty?
      return right_array
    end

    smallest_number = if left_array.first <= right_array.first
      left_array.shift
    else
      right_array.shift
    end

    recursive = merge(left_array, right_array)

    [smallest_number].concat(recursive)
  end

먼저 하위 배열 중 하나가 비어 있는지 확인합니다. 그렇다면 단순히 다른 하나를 반환할 수 있습니다. 그렇지 않으면 두 하위 배열이 모두 비어 있지 않은 경우 각 배열의 첫 번째 요소 값을 비교한 다음 비교된 값을 이동하여 무한 루프 생성을 방지합니다. 다음으로 우리는 두 개의 배열을 멋지게 정렬하여 연결할 수 있을 때까지 원래 배열에서 재귀를 활용합니다.

재귀에 대한 추가 정보

우리 코드에서 이상해 보이는 것이 있다면 다음 줄일 것입니다. recursive = merge(left_array, right_array) 우리는 merge이라고 부릅니다. 자체의 메소드 . 와! 이것은 우리가 재귀라고 부르는 것입니다. 지정된 조건이 충족될 때까지 함수가 자신을 한 번 이상 호출하는 기술입니다. 우리의 경우 merge 왼쪽 또는 오른쪽 배열이 비어 있을 때까지 계속 호출됩니다. 재귀에 대해 자세히 알아보려면 다음 예제에서 Ruby와 재귀를 사용하여 피보나치 수열에 대한 함수를 작성하는 방법을 살펴보세요.

요약

병합 정렬에 대해 더 많이 배우셨기를 바랍니다! 상위 수준에서 작동하는 방식과 버블 정렬 또는 선택 정렬보다 더 효율적인 선택인 이유를 이해하면 면접이나 일상 업무에 도움이 될 것입니다. 또한 관심이 있는 경우 Wikipedia에서 자세히 읽을 수 있는 여러 병합 정렬 변형이 있습니다. 다음 시간까지...행복한 정렬!