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

16

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

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

jonaprieto
источник
9
Вы хотите доказать сложность быстрой сортировки ... группе трехлетних ...? Удачи.
2
Попробуйте использовать их язык, проблема в том, что он очень ограничен и биологически они не готовы к такой сложности. Следующие шаги, как в алгоритме, не полностью разработаны, пока им не исполнится шесть или семь лет. Вы сталкиваетесь с биологической проблемой.
4
На самом деле, я бы не советовал это для детского сада, но поиск на youtube для быстрой сортировки (и других алгоритмов сортировки) дает много хороших представлений. Я лично предпочитаю хугарские народные танцы. Смотрите youtube.com/watch?v=ywWBy6J5gz8 .
2
У статьи, о которой вы говорите, есть броское название, но очень сложное содержание, такое как «Пространственная модель Гильберта», так чего же вы действительно хотите?
2
Я бы отказался от попытки полностью объяснить быструю сортировку и вместо этого попытался бы дать детям понимание «разделяй и властвуй». Даже если они не достаточно взрослые, чтобы полностью справиться с рекурсией, идея разбить большую проблему на более мелкие была бы действительно ценной. Лично я бы взял твердое фундаментальное понимание «разделяй и властвуй» в любой день из-за неполного представления о сложных алгоритмах.
Винсент Гейбл

Ответы:

14

По своей сути Quicksort таков:

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

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

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

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

1 2 3 4
  2 3 4
    3 4
      4

Довольно легко увидеть (и доказать), что это .12N2

Я не знаком с доказательством среднего случая, поэтому я не могу сделать предложение для этого. Можно сказать, что в несортированном массиве длины вероятность выбора наименьшего или наибольшего элемента равна 2L , так ...?2N

Kevin
источник
Возможно (d & c) рекурсия лучше всего и наиболее естественно объясняется внутренним параллелизмом.
Рафаэль
2
Я бы согласился. Мой инстинкт был в том, чтобы использовать метафору предоставления двум кучам своим друзьям для работы.
Кристиан Манн
3
Я утверждаю, что четырехлетние дети (за некоторыми исключениями) принципиально неспособны понять рекурсию, как бы вы ни старались. Мозг просто недостаточно зрел. Существуют четко определенные фазы развития мозга, например, когда дети начинают осознавать себя, где они узнают о будущих последствиях текущих действий, и где они впервые понимают сарказм, который следует строго контролируемому графику, который не может быть изменен преднамеренно и высоко консервативен среди детей. Я считаю, что понимание рекурсии относится к той же категории.
Конрад Рудольф
16

Быстрая сортировка на самом деле довольно проста для понимания, если они понимают основы подсчета и деления на 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. Вы могли бы хотеть задержаться на этой части сначала.

Мейсон Уилер
источник
Я не думаю, что ваш пример не очень хорош, потому что вы по сути сортируете по ключам, а не по значениям, и вы можете узнать, что находится в позиции 15, только отсортировав.
Торбьерн Равн Андерсен
@ Thorbjørn: Кто сказал что-нибудь о парах ключ / значение? Это простая целочисленная сортировка для объяснения основной концепции.
Мейсон Уилер
Размышление над алгоритмом, который вы описываете, не является быстрой сортировкой, так как вы не используете элемент pivot.
Турбьёрн Равн Андерсен
1
@ ThorbjørnRavnAndersen: Конечно, он делает; просто он знает, какие элементы есть, поэтому может выбрать медиану.
Рафаэль
@ Рафаэль и их распространение. Карты могут быть любого значения и цвета и иметь наклейку с номером от 1 до 20. Отсюда моя ссылка на ключ / индекс, а не значение.
Торбьерн Равн Андерсен
2

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

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

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

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

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

Timb
источник
круто один! Довольно легко понять.
Майур Патил
1

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

быстрая сортировка,

gbjbaanb
источник
1
Я думаю, что это может быть слишком абстрактно для детей.
Рафаэль
3
Не смущать себя, но я не понимал эту графику, пока мне наконец не объяснили быструю сортировку в классе.
Кристиан Манн
Имейте +1, потому что это то, что впервые пришло мне в голову, когда я прочитал вопрос, но потом я визуальный ученик.
Джошуа Дрейк
3
Это действительно неправильный способ объяснить, как работает быстрая сортировка . Если вы уже знаете быструю сортировку, вы можете подтвердить, что эта анимация предназначена для быстрой сортировки. Если вы не знаете быстрой сортировки, она ничего не говорит, за исключением того, что быстрая сортировка является довольно быстрым алгоритмом сортировки, который использует некоторую магию. В зависимости от того, кто является аудиторией, вы можете мотивировать аудиторию, чтобы узнать о быстрой сортировке, показывая эту анимацию, но она не объясняет ничего важного о том, как она работает.
Tsuyoshi Ito
Анимация довольно приятная, но она настолько понятна как для новичка, так и для старшекурсника.
jonaprieto