Алгоритм сортировки путём вставок. Дональд Э. Кнут. Ruby

21 сентября 2026

# encoding: utf-8
# frozen_string_literal: true
#
# @author ESV Corp. (C) 21.09.2026
#
# алгоритм "сортировка путём вставок"
# Д. Кнут "Искусство программирования", т.3 "Сортировка и поиск",
# глава 5.2.1. Сортировка путём вставок
#

# ---
# сортировка методом вставок
def sort_by_inserts(r)

  n = r.size

  puts "sort_by_inserts: nothing to sort" unless n > 1

  puts "Sort by inserts source: #{r.inspect}"

  j = 1;

  while j < n

      t = r[j]
      i = j

      while i > 0

          check = r[i-1]

          break if check < t

          r[i] = check
          i -= 1

      end

      # в оригинальном алгоритме Кнута значение может быть
      # записано в ту же самую позицию
      # видимо потому, что лишняя проверка индексов дополнительно занимает
      # память программы, и ещё и для выполнения требует время
      r[i] = t

      j += 1

  end

  r

end


# ===
# основная программа

puts "Donald E. Knuth algorithm test: sort by inserts"

src_list = [5, 3, 2, 7, 1, -5, 10, 4, -3, 0, 12, 6, 7, 9, 11, 8]

# в процессе сортировки модифицируем исходный массив, поэтому нужна копия
list = src_list.dup

sorted_list = sort_by_inserts(list)

puts "source: #{src_list.inspect}"
puts "sorted: #{sorted_list.inspect}"