Quicksort объяснил детям

Question

В прошлом году я читал фантастическую Бумага о «Квантовой механике для детского сада». Анкет Это была нелегкая бумага.

Теперь мне интересно, как объяснить QuickSort в самых простых словах. Как я могу доказать (или, по крайней мере, ручной волны), что средняя сложность - это $ o (n log n) $, а каковы лучшие и худшие случаи - для класса детских садов? Или, по крайней мере, в начальной школе?

Answer 1

По своей сути, QuickSort - это:

1. Возьмите первый предмет.
2. Переместите все меньше, чем этот первый предмет слева от него, все больше справа (при условии восходящего порядка).
3. Выяснение с каждой стороны.

Я думаю, что каждый 4-летний на планете может сделать 1 и 2. Рекурсия может потребоваться немного больше объяснений, но не должно быть так трудно для них.

1. Повторите на левой стороне, игнорируя справа на данный момент (но помните, где была середина)
2. Продолжайте повторять с левой стороны, пока не доберетесь до ничего. Теперь вернитесь к последней правой стороне, которую вы игнорировали, и повторите процесс там.
3. Как только у вас закончится правая и левая сторона, все готово.

Что касается сложности, худший случай должен быть довольно простым. Просто рассмотрим, что уже сортированный массив:

1 2 3 4
  2 3 4
    3 4
      4

Довольно легко увидеть (и доказать), что это $ frac {1} {2} n^2 $.

Я не знаком со средним доказательством, поэтому я не могу сделать предложение для этого. Вы могли бы сказать, что в несортированном массиве длины $ l $ вероятность выбрать наименьший или самый большой предмет - $ frac {2} {n} $, так ...?

Answer 2

Quicksort на самом деле довольно легко понять, если они понимают базовый подсчет и деление на 2. Сделайте кучу флэш-карт X, номер 1-x и перетасовывают его. Тогда вот объяснение:

Хорошо, у нас есть эта колода (скажем, 20) карт здесь. Мы хотим поместить их в порядок, так что 1 - сначала, затем 2, затем 3 и так далее. Вот очень быстрый способ сделать это.

Во -первых, давайте пройдемся через эту колоду и сделаем из нее две кучи. Половина из 20 составляет 10, поэтому все больше, чем 10, идет в эту кучу справа, и все меньшее идет в эту кучу слева. (Обязательно продемонстрируйте, как вы идете.)

Теперь давайте сделаем то же самое с меньшими кучами. Что половина из 10? (Кто -то говорит «пять!») Это верно! Таким образом, что -то больше, чем 5, идет в эту кучу справа, и все меньшее идет в эту кучу слева.

И здесь у нас есть группа, которая больше 10. Так половина из 10 - 5, а что 10 плюс 5? (Кто -то говорит «Пятнадцать!») Это верно! Таким образом, что -то больше, чем 15, идет в эту кучу справа, и все, что меньше 15, идет в эту кучу слева.

И теперь груды становятся достаточно маленькими, чтобы вы могли легко посмотреть на них и поставить их по порядку. Слушай, здесь у нас есть 2, 4, 5, 3, 1. Анкет Итак, мы просто переключаем их так, и вы можете увидеть 1, 2, 3, 4, 5Анкет Итак, давайте сделаем то же самое с другими кучами, а потом мы просто поставляем кучи в порядок и посмотрим! Они в порядке от 1 до 20!

Поздравляю. Вы только что научили группу детей основным принципам адаптивного алгоритма QuickSort! Вы можете пойти немного глубже, чем это в зависимости от умственной зрелости, но выходить намного дальше за этот момент, требует некоторого понимания формальной логики.

Что касается его сложности, это сложнее. Это одна из вещей, которая требует формальной логики, и они должны в первую очередь понять основные принципы нотации Big-O. Сначала вы можете задержать эту часть.

Answer 3

Как насчет этого?

Информатика отключена - алгоритмы сортировки

Это не совсем охватывает все ваши вопросы, но это хорошее начало.

Больше ресурсов по этой теме связаны здесь.

Они также сделали доступное видео, которое объясняет алгоритмы сортировки (включен QuickSort) здесь. Анкет Это видео действительно помогает понять разницу между различными алгоритмами сортировки для маленьких детей.

Answer 4

Смотрите графическую красоту этого Маленькая демонстрация.

.