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

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

def shellsort(r)

  n = r.size

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

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

  # смещения могут быть разными, но последнее - всегда должно быть 1
  # Кнут предлагает в примере [8, 4, 2, 1]
  [7, 5, 3, 1].each do | h |

    j = h

    while j < n

        t = r[j]
        i = j

        while i >= h

            check = r[i-h]

            break if check < t

            r[i] = check

            i -= h

        end

        # моё дополнение - чтобы не перезаписывать одно и то же
        # значение, если оно не подлежит перемещению
        r[i] = t if i < j

        j += 1

    end

  end

  r

end


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

puts "Donald E. Knuth algorithm test: shellsort"

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

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

sorted_list = shellsort(list)

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