Сортировка вставками

Это часть моей серии статей об алгоритмах и структурах данных под названием «Алгоритмы с тетушкой Аей». Эта серия представляет собой введение в структуры данных и алгоритмы для людей, которые никогда их не изучали или забыли.

Алгоритмы с тетушкой Аей: Сортировка

Алгоритмы сортировки составляют большую часть любого курса алгоритмов. Они также часто появляются в интервью. По моему не столь скромному мнению, правильный ответ, когда кто-то просит вас что-то отсортировать на собеседовании, — использовать любую сортировку, встроенную в ваш язык. Сортировка обманчиво сложна. Многие считают, что это должно быть легко. Ведь 2-х и 3-х летние дети умеют сортировать вещи. Оказывается, есть много тонкостей, которые следует учитывать при написании алгоритма сортировки. Одним из распространенных примеров являются ошибки один за другим (ошибки столбов забора).

Сортировка вставками — это первая сортировка, о которой я расскажу. Есть несколько более простых алгоритмов сортировки (например, пузырьковая сортировка), но сортировку вставками объяснить несложно. Вы, вероятно, используете метод, похожий на сортировку вставками, когда сортируете вещи в повседневной жизни. Кроме того, он достаточно хорошо работает с небольшими наборами данных, и вам не нужно иметь все элементы заранее. Вы можете размещать новые предметы в правильном месте по мере их появления. Это делает его онлайн алгоритмом сортировки.

Настройка сортировки вставками проста. У вас есть две коллекции. Один содержит несортированные элементы. Другой содержит элементы, которые отсортированы. Если это сбивает с толку, подумайте о заказе колоды карт. Перетасованные (неотсортированные) карты находятся в колоде, а те, которые вы расставили по порядку, разложены на столе.

При запуске коллекция отсортированных элементов пуста. Чтобы отсортировать, вы смотрите на первый элемент в несортированной коллекции и помещаете его в нужное место в отсортированной коллекции. Затем вы кладете следующий элемент на место. Повторяйте, пока не отсортируете.

Код

В духе TDD я начну с трех основных тестов. Сортировка пустого массива, сортировка массива длины один и сортировка массива с более чем одним элементом.

require 'minitest/autorun'
require './insertion_sort'

class TestInsertionSort < Minitest::Test
  def test_sort_empty_list
    assert_equal [], [].insertion_sort
  end

  def test_sort_list_length_one
    assert_equal [3], [3].insertion_sort
  end

  def test_sort_random_list
    assert_equal [1, 2, 3, 4, 5], [3, 2, 5, 1, 4].insertion_sort
  end
end

Вот базовая реализация сортировки вставками. Я обезьяньи исправления (повторно открываю) класс Array, потому что мои тесты вызывают сортировку вставками в массиве.

class Array
  def insertion_sort
    sorted = []

    self.each do |item|
      (0..sorted.length).each do |index|
        if sorted.fetch(index, Float::INFINITY) > item then
          sorted.insert index, item
          break
        end
      end
    end

    sorted
  end
end

В этих 18 строках происходит довольно много. В строке 3 я создаю новый массив с именем sorted, который будет содержать отсортированные результаты (те, что на столе, по аналогии с карточками). Далее (строка 5) я перебираю все элементы self, которые представляют собой несортированный массив.

Строки 6–13 просматривают отсортированный массив и пытаются найти первый элемент, который больше, чем элемент, на который я сейчас смотрю. Как только он найден (строка 9), я использую Array#insert, который вставляет элемент в массив перед указанным индексом.

Если элемент, который я пытаюсь найти, больше, чем все остальные элементы в отсортированном массиве, индекс в конечном итоге будет sorted.length. Это потому, что я использую две точки для диапазона. Две точки означают, что включены оба конца диапазона. Если index имеет значение sorted.length, то sorted[index] будет равен нулю. Я ловлю этот случай в строке 8 и использую вставку, чтобы добавить элемент в конец отсортированного массива.

Сортировка на месте

Приведенная выше версия сортировки вставками работает, но создает копию массива и оставляет оригинал нетронутым. Если я хочу отсортировать исходный массив, я могу написать #insertion_sort!. Вот новые тесты:

def test_sort_bang_empty_list
    ary = []
    ary.insertion_sort!
    assert_equal [], ary
  end

  def test_sort_bang_list_length_one
    ary = [3]
    ary.insertion_sort!
    assert_equal [3], ary
  end

  def test_sort_bang_random_list
    ary = [3, 2, 5, 1, 4]
    ary.insertion_sort!
    assert_equal [1, 2, 3, 4, 5], ary
  end

Поскольку я тестирую метод, который изменяет массив, мне нужно присвоить массив, вызвать мой метод, а затем подтвердить, что он сделал правильно. Вот почему эти тесты длиннее, чем тесты для insertion_sort выше.

Вот код:

def insertion_sort!
  (1...self.length).each do |i|
    j = i
    while j > 0 and self[j - 1] > self[j]
      self[j], self[j - 1] = self[j - 1], self[j]
      j -= 1
    end
  end
end

Эта версия намного короче. Начиная со второго элемента массива (индекс 1), я беру этот элемент и сравниваю его со всеми элементами массива перед ним. Когда я нахожу тот, который меньше, я вставляю текущий элемент сразу после него. Если я сделаю это полностью вперед, текущий элемент должен быть наименьшим, поэтому я помещаю текущий элемент в начало массива.

Вывод

Сортировка вставками не является особенно эффективным алгоритмом, но его легко понять и относительно просто написать. Существует несколько различных способов его реализации, и я рекомендую вам пройти тесты, которые я предоставил, и попытаться найти другой способ его реализации.

Код, использованный в этом посте, доступен на Github.

08/28/16

Первоначально опубликовано на www.thagomizer.com 28 августа 2016 г.