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

21 сентября 2026

# encoding: utf-8
# frozen_string_literal: true
#
# @author ESV Corp. (C) 21.09.2026
#
# алгоритм: сортировка методом "пузырька"
# Д. Кнут "Искусство программирования", т.3 "Сортировка и поиск",
# глава 5.2.2, раздел "Обменная сортировка"
#
# математически "метод пузырька" не считается эффективным,
# метод вставок эффективнее
#

# ---
# сортировка методом "пузырька"
def sort_bubble(list)

  bound = list.size - 1

  while bound > 0

    t = 0

    # с первого элемента до предпоследнего (относительно рассматриваемой границы ещё не отсортированных)
    # после обмена элементов граница смещается
    for j in 0...bound do

      if list[j] > list[j+1]
        list[j], list[j+1] = list[j+1], list[j]
        t = j
      end

    end

    bound = t

  end

  list

end


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

puts "Donald E. Knuth algorithm test: bubble"

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 = sort_bubble(list)

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