Алгоритм "Быстрая сортировка", Quicksort, Обменная сортировка с разделением. Ч. Э. Р. Хоар. Р. Седжвик, Дональд Э. Кнут. Ruby

21 сентября 2026

# encoding: utf-8
# frozen_string_literal: true
#
# @author ESV Corp. (C) 21.09.2026
#
# алгоритм: сортировка методом "быстрая сортировка" Quicksort, Обменная сортировка с разделением
# Ч. Э. Р. Хоар (C. A. R. Hoare)
# Р. Седжвик "Алгоритмы",
# Д. Кнут "Искусство программирования", т.3 "Сортировка и поиск",
# глава 5.2.2, раздел "Обменная сортировка"
#
# сначала происходит разделение массива на подмассивы, размер которых
# подходит для быстрой сортировки методом вставок, далее каждый подмассив
# сортируется методом вcтавки
# сортировка всего массива производится "по месту", т.е. без создания дополнительных
# массивов
#

M = 5 # размер подмассива для сортировки методом вставок

# ---
# "разделение" массива на подмассивы:
# в результате возвращается индекс (index) в массиве, такой, что
# элементы list[l...index] <= list[index] <= list[index+1..r]
#
# Parameters
#
# @param l [Integer] левая (меньшая) граница исходного массива
# @param r [Integer] правая (большая) граница исходного массива
# @param list [Array<Integer>] изменяемый массив, который разделяется
#
# Returns
#
# @return [Integer] индекс элемент в массиве, который делит массив на левую и правую части
#
def split(l, r, list)

  i = l
  j = r + 1

  k = list[l]

  while i < j

    # гарантированный сдвиг индексов
    # !!! важно: этот код выполняется и после обмена соседних элементов [i] и [j]
    # при этом более важен j -= 1 , т.к. после этого он будет указывать
    # на элемент, который подлежит обмену с "центральным" элементом после
    # выхода из цикла while i < j
    i += 1
    j -= 1

    while i < r && k > list[i]
      i += 1
    end

    while j > l && k < list[j]
      j -= 1
    end

    # достаточно условия i < j , но дополнительно list[i] != list[j], чтобы не менять
    # одинаковые элементы
    if i < j && list[i] != list[j]
      # обмен элементов из левой и правой частей
      list[i], list[j] = list[j], list[i]
    end

  end

  # обмен левого элемента и "центрального", который должен находится между разделёнными массивами
  # тут можно тоже в условие добавить && list[i] != list[j] , но для наглядности:
  # алгоритм Кнута и Седжвика не делает эту проверку
  if l != j
    # установим "центральный" элемент между массивами "меньше" и "больше"
    list[l], list[j] = list[j], list[l]
  end

  j

end


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

  puts "sort_by_inserts: nothing to sort" unless (ri - li + 1) > 1

  puts "Sort by inserts source: (#{li}-#{ri}) #{r[li..ri].inspect}"

  j = 1 + li

  while j <= ri

    t = r[j]
    i = j

    while i > li

      check = r[i-1]

      break if check < t

      r[i] = check
      i -= 1

    end

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

    j += 1

  end

  r

end


# ---
# быстрая сортировка
# рекурсивный вызов
def quicksort_recursive(l, r, list)

  if l >= r
    return list
  end

  # разделяем на подмассивы
  s = split(l, r, list)

  center_elem = list[s]
  left_slice  = list[l...s]
  right_slice = list[s+1..r]

  puts("---")
  puts("splited:")
  puts("index = #{s}, list[s] = #{center_elem}")
  puts("left  = #{left_slice.inspect}")
  puts("right = #{right_slice.inspect}")
  puts("#{left_slice.inspect} #{center_elem} #{right_slice.inspect}")
  puts("===")

  left_size  = s - l
  right_size = r - s

  # сортировка левой части
  if left_size > 1

    if left_size > M
      quicksort_recursive(l, s - 1, list)
    else
      sort_by_inserts(list, l, s - 1)
    end

  end

  # сортировка правой части
  if right_size > 1

    if right_size > M
      quicksort_recursive(s + 1, r, list);
    else
      sort_by_inserts(list, s + 1, r)
    end

  end

  list

end


# ---
# быстрая сортировка
# использование стека индексов
def quicksort_stack(l, r, list)

  if l >= r
    return list
  end

  qs_stack = []
  ins_stack = []

  qs_stack.push([l, r])

  while qs_stack.any?

    l, r = qs_stack.pop

    if (r - l + 1) <= M
      ins_stack.push([l, r])
      next
    end

    # разделяем на подмассивы
    s = split(l, r, list)

    center_elem = list[s]
    left_slice  = list[l...s]
    right_slice = list[s+1..r]

    puts("---")
    puts("splited:")
    puts("index = #{s}, list[s] = #{center_elem}")
    puts("left  = #{left_slice.inspect}")
    puts("right = #{right_slice.inspect}")
    puts("#{left_slice.inspect} #{center_elem} #{right_slice.inspect}")
    puts("===")

    left_size  = s - l
    right_size = r - s

    if left_size > 1
      if left_size > M
        qs_stack.push([l, s - 1])
      else
        ins_stack.push([l, s - 1])
      end
    end

    if right_size > 1
      if right_size > M
        qs_stack.push([s + 1, r])
      else
        ins_stack.push([s + 1, r])
      end
    end

  end

  # сортировка коротких участков методом вставки
  while ins_stack.any?
    l, r = ins_stack.pop
    sort_by_inserts(list, l, r)
  end

  list

end


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

puts "Robert Sedgewick, Donald E. Knuth algorithm test: quicksort"

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

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

sorted_list = quicksort_recursive(0, list.size-1, list)

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

puts "\n#{'*' * 30}\n\n"

list = src_list.dup

sorted_list = quicksort_stack(0, list.size-1, list)

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