Сортировка пузырьком

Описание	Сортиро́вка простыми обменами, сортировка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.
Область знаний	Информатика
Область использования (ISTE)
Возрастная категория	9
Поясняющее видео
Близкие рецепту понятия	Сортировка
Среды и средства для приготовления рецепта:	Scratch

Сортировка пузырьком

Алгоритм состоит из повторяющихся проходов по сортируемому списку. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по списку повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — список отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце списка рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма).

Scratch

when green flag clicked
set [pass v] to [0]
set [swaps v] to [0]
repeat until <<(pass) > [0]> and <(swaps) = [0]>>
  set [item v] to [0]
  change [pass v] by (1)
  set [swaps v] to [0]
  repeat ((length of [data v]) - (1))
    change [item v] by (1)
    if <(item ((item) + (1)) of [data v]) < (item (item) of [data v])> then
      set [value v] to (item ((item) + (1)) of [data v])
      replace item ((item) + (1)) of [data v] with (item (item) of [data v])
      replace item (item) of [data v] with (value)
      change [swaps v] by (1)
    end
  end
end

Snap!

Результат:

---

• Сортировка вставками
• Быстрая сортировка

Теория

Сортировка. Алгоритм сортировки списка. Принципы сортировки пузырьком и вставкой.

Практика

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