Алгоритмы сортировки в Ruby

Сортируйте левую часть от A и правую от A, затем объедините их.

Мы можем на самом деле разделить каждую половину на дальнейшие половины (четверти исходной части) и продолжить рекурсивно. Оказывается, мы в конечном итоге достигнем массива размера 1, который автоматически сортируется. Затем возьмите все части и, наконец, объедините их, чтобы получить эквивалент A.sort Однако процесс объединения немного сложен.

Допустим, нам даны два отсортированных массива, например [1, 3, 5] и [2, 4, 6, 7], и мы хотим объединить их в один отсортированный массив. Вот как это сделать, в этом случае. Посмотрите на первые элементы обоих массивов и поместите меньший в конечный результат. После одного запуска этого у нас есть это в конечном результате:

 [1]

Повторите процесс, за исключением перемещения по массиву, делая следующий элемент «первым элементом». В этом случае сделайте 3 «первым элементом» из [1, 3, 5] и сравните его с 2 из [2, 4, 6, 7]. Мы продолжаем делать это, пока не исчерпаем один из списков. На данный момент, конечный результат выглядит так:

 [1, 2, 3, 4, 5]

Затем просто нажмите на остальную часть второго списка, чтобы получить комбинированный, хорошо отсортированный список:

 [1,2,3,4,5,6,7]

Мы можем использовать процедуру, описанную в примере, как шаг «слияния» или «объединения». Итак, вот схема слияния для массива An

 Mergesort(A):
1. return A if n == 1
2. left = left half of A
3. right = right half of A
4. sorted_left = Mergesort(left)
5. sorted_right = Mergesort(right)
6. return merge(sorted_left, sorted_right)

Давайте посмотрим на представление Ruby этого:

 def mergesort(array)
  def merge(left_sorted, right_sorted)
    res = []
    l = 0
    r = 0

    loop do
      break if r >= right_sorted.length and l >= left_sorted.length

      if r >= right_sorted.length or (l < left_sorted.length and left_sorted[l] < right_sorted[r])
        res << left_sorted[l]
        l += 1
      else
        res << right_sorted[r]
        r += 1
      end
    end

    return res
  end

  def mergesort_iter(array_sliced)
    return array_sliced if array_sliced.length <= 1

    mid = array_sliced.length/2 - 1
    left_sorted = mergesort_iter(array_sliced[0..mid])
    right_sorted = mergesort_iter(array_sliced[mid+1..-1])
    return merge(left_sorted, right_sorted)
  end

  mergesort_iter(array)
end

Основная интересная процедура здесь — merge По сути, двигайтесь вдоль двух половин, добавляя меньшее значение к концу res На этом этапе просто сложите то, что осталось от другого списка. И это MergeSort для вас!

В чем смысл?

Итак, в чем выгода реализации значительно более сложного алгоритма, чем старый добрый BubbleSort? Это все в цифрах.

Не вдаваясь в подробности (они включают решение повторения), мы скажем, что сортировка слиянием \ [O (n log_2 {n}) \] Оказывается, это * намного * лучше, чем \ [O ( п ^ 2) \] Давайте сделаем еще одно упрощение. Скажем, MergeSort использует операции \ [n / log_2 (n) \], а BubbleSort использует операции \ [n ^ 2 \] для сортировки массива длины nn = 1,000,000

Разделяй и властвуй

MergeSort показывает нам хорошую стратегию: разделяй и властвуй. Оказывается, есть много проблем, которые можно решить, разбив их на подзадачи и объединив получившиеся «подрешения». Требуются навыки и практика, чтобы определить случаи, когда вы можете использовать разделяй и властвуй, но MergeSort является отличным примером для использования в качестве трамплина.

Вот основные моменты: если у вас есть какой-то тривиальный базовый случай (в MergeSort, список длиной 1) или вы каким-то образом можете разбить вашу проблему до этого базового случая и у вас есть идея объединить решения, разделить и Завоевание может быть проспектом для изучения.

Тратить память как завтра

Но подождите, мы можем сделать даже лучше, чем MergeSort! Но на этот раз нам придется потратить немного больше памяти. Мы перейдем прямо к Ruby:

 def mark_sort(array)
  array_max = array.max
  array_min = array.min
  markings = [0] * (array_max - array_min + 1)
  array.each do |a|
    markings[a - array_min] += 1
  end

  res = []
  markings.length.times do |i|
    markings[i].times do
      res << i + array_min;
    end
  end

  res
end

p mark_sort([3,2,19,18,17])

У нас есть массив под названием markingsarray Каждый индекс markingsarray.maxarray.min Мы инициализируем markings Наконец, просто распечатайте числа, которые вы видели нужное количество раз. Мы делаем несколько проходов массива, но мы никогда не делаем «проход внутри прохода», то есть вложенный цикл. Итак, наш алгоритм выполняет \ [c * n \] операции для некоторой константы cn

Можно сказать, что это \ [O (n) \], другими словами, молниеносно. Но это не всегда полезно, так как мы должны использовать потенциально гигантский кусок памяти. Например, если бы нам дали [1,1000000] Но если мы знаем, что наши диапазоны будут маленькими или у нас будет много памяти, этот алгоритм может пригодиться.

Завершение

Надеюсь, вам понравился этот тур по алгоритмам сортировки в Ruby. Оставьте вопросы в комментариях ниже!