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

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

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

По своей сути 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}$

Быстрая сортировка на самом деле довольно проста для понимания, если они понимают основы подсчета и деления на 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!

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

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

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

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

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

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

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

Посмотрите на графическую прелесть этой маленькой демонстрации .

,