Чему следует учить студентов в первую очередь при изучении алгоритмов сортировки?
Если бы вы были учителем программирования, и вам нужно было выбрать один алгоритм сортировки, чтобы научить своих учеников, какой это будет? Я прошу только один, потому что я просто хочу представить концепцию сортировки. Должна ли это быть пузырьковая сортировка или выборочная сортировка? Я заметил, что этим двум учат чаще всего. Есть ли другой тип сортировки, который объяснит сортировку в более понятном виде?
33 ответа
Я не уверен, что мог бы быть учителем информатики и учить только одному алгоритму сортировки.
Как минимум, ученики должны обучаться, по крайней мере, одному из каждого из основных типов сортировки, а именно: обменной сортировке, сортировке выбора, вставке и сортировке слиянием. В дополнение к одному из этих типов, я бы также охарактеризовал быструю сортировку, которая относится к разделу сортировки по разделам.
Что касается конкретных видов из каждого из типов, которые я бы охватил:
- Пузырьковая сортировка в качестве примера категории сортировки с обменом, поскольку она является одним из простейших типов сортировки и тем, который они, вероятно, уже видели или наткнулись самостоятельно. Это также тот тип, который они, скорее всего, будут использовать чаще всего, если им придется свернуть свои собственные вещи для чего-то простого, чтобы им было понятно это понять.
- Heapsort из категории сортировки выбора. Скорее всего, это будет наиболее запутанная сортировка рядом с быстрой сортировкой, но как только они поймут, как она настраивает их для понимания алгоритма быстрой сортировки.
- Сортировка вставкой в качестве примера категории сортировки вставкой будет рассмотрена, так как это также простая сортировка, из которой они могут получить много пользы. Поскольку они могут столкнуться со сценариями, в которых им необходимо объединить два списка, знание этого имеет смысл.
- Сортировка слиянием является своего рода специализированной сортировкой, поэтому вы не видите ее слишком часто, но она очень хороша в том, что делает, и все еще полезна в ситуациях, когда вам нужно сортировать данные, которые вы получаете по частям.
Если бы мне пришлось сузить круг вещей только до одного вида, которому я мог бы научить, но у меня было время убедиться, что ученик точно понял, что происходит, я бы научил быстрой сортировке. Хотя это нелегко понять, подавляющее большинство фреймворков используют его для алгоритма сортировки, поэтому понимание того, как это работает, полезно при разработке с этой фреймворком. Кроме того, вполне вероятно, что если кто-то сможет понять Быструю сортировку, то он сможет самостоятельно изучать сортировку по пузырям и вставку.
Пусть ваши ученики решают.
Прежде чем вводить какие-либо алгоритмы сортировки, дайте каждому ученику несколько игральных карт, может быть, около 10. Затем попросите их отсортировать карточки. Попросите их записать шаги, которые они предпримут, что по сути будет их алгоритмом Скорее всего, они обнаружат вставку или выбор сортировки. Вы также можете попросить их оценить, сколько шагов их сортировка сделала бы, если бы у них было 100 или 1000 карт, что является хорошим выводом в большую букву O.
PS - кто-нибудь думает, что они обнаружат пузырьковую сортировку?
Если вы хотите научить сортировку, то пузырьковая сортировка, вероятно, легче всего понять. Если вы хотите обучить алгоритмам сортировки, то вы должны действительно обучать быстрой сортировке, слиянию, вставке и, возможно, даже сортировке, чтобы студенты могли найти компромисс между различными методами сортировки.
Я бы начал с показа сортировки вставок. Каждый, кто сортировал карточную комбинацию (а это в основном все), знает этот вид. Плюс у этого нет ужасной работы пузырчатой сортировки.
Сначала я выучил Bubble Sort - я думаю, что если вы делаете только один, вам, вероятно, нужно сделать один из O(n^2) алгоритмов, потому что их легче понять.
Есть много визуализаторов сортировки, которые помогут быстро показать сравнение:
Я бы посоветовал и Selection и Merge Sort по общим алгоритмам сортировки. Оба относительно прямолинейны по сравнению со своими друзьями. Но если вы можете учить только одного, а люди могут справиться с этим, я бы выбрал Merge Sort. Поскольку сортировка слиянием эффективна, стабильна и учит нескольким важным концепциям (слияние, разделение и завоевание).
Выбор сортировки:
Найдите минимальное / максимальное значение и поместите его на место, затем сделайте это снова в остальной части списка... это очень интуитивно понятно. Для меня выбор намного более интуитивен, чем даже пузырьковая сортировка. Вы могли бы научить этому в очень короткое время. И у людей, которые это реализуют, будет чувство выполненного долга... Хотя Bubble и Insertion могут выйти рано и не будут тратить время на отсортированный список. Отбор, наверное, самый простой. Вставка, вероятно, труднее всего реализовать.
Сортировка слиянием:
Это научит, как объединять (что важно, потому что есть тонна ускорений, которые вы можете получить, объединяя два отсортированных списка вместе), а также как разделить проблему на более мелкие подзадачи (важно для работы с иерархическими структурами и также используется в быстрая сортировка). Быстрая сортировка, хотя быстрее, понять гораздо сложнее. Вам нужны две переменные сканирования, элемент сводки и т. Д. Объединение более простое, и объединение пригодится для других целей, кроме сортировки (например, объединение двух записей, отсортированных по полю)....
Основная концепция слияния интуитивно понятна. Возьмите меньший элемент из отсортированного списка и поместите его в окончательный список. И разделение проблемы сортировки слиянием также является интуитивно понятным.
mergesort (первая половина) mergesort (вторая половина)
объединить (первая половина, вторая половина)
Если вы можете преподавать только один вид и должны делать это быстро (или аудитория на самом деле не заинтересована вообще), я бы склонялся к выбору, потому что это сложнее, и отбору можно научиться быстро. Но если аудитория более мотивирована, я бы сделал Merge, потому что она учит так много дополнительных фундаментальных концепций.
Из более эффективных сортировок этот намного проще, чем быстрый и кучный. Хотя быстрая сортировка, вероятно, самая быстрая на практике (при условии, что у вас много оперативной памяти), и куча, вероятно, способна сортировать самые большие списки (если реализованы не рекурсивно).
Ковш Сортировка:
Я бы коснулся этого, потому что он также интуитивно понятен и представляет собой другой тип алгоритма сортировки. Во многих ситуациях это уместно, и время O(n) очень привлекательно.
Подсчет сортировки:
Это имеет свое применение. В некоторых случаях это очень эффективно... Это также относительно просто.
Я думаю, что методы сортировки являются очень хорошим примером того, что такое алгоритм. Но это становится хорошим примером только тогда, когда вы сравниваете различные методы. Если вы можете научить только одному, я не уверен, что оно того стоит.
Реально, мы вызываем метод сортировки в некоторых рамках. Так что, если вы не можете эффективно учить сортировке, это может не стоить времени.
Никто больше не должен писать метод сортировки, но это все еще очень хороший пример воздействия алгоритмов.
Сортировка выбора, вероятно, является наиболее простым алгоритмом сортировки для обучения и наиболее простым для понимания. Это также прекрасный пример того, почему простые решения не всегда являются лучшими, что может привести к обсуждению более интересных и более быстрых сортировок, таких как mergesort и quicksort.
Это было бы радикально. Потому что это на удивление легко и все же неочевидно. Подобным вещам просто нужно учить.
Я думаю, что только обучение одного вида наносит вред. Помните, что все быстро для малого n, поэтому с точки зрения обучения сортировке речь идет не о производительности, а о понимании алгоритма.
Я думаю, что введение должно быть пузырчатым, чтобы представить концепцию, но, по крайней мере, ввести другой вид, чтобы студенты думали о других способах выполнения задачи. Убедитесь, что они понимают компромисс между производительностью и сложностью кода, а также что существуют разные инструменты для разных ситуаций.
Я бы научил "называть рамки".
Было бы эффективно учить и учить такого рода. Студенты будут иметь высокую степень успеха и низкий уровень ошибок при реализации такого рода.
Изменить: Есть много критикующих комментариев к этому ответу о качестве моего единственного класса сортировки. Эта критика применима к любому ответу на этот вопрос, а именно: "Если бы вы были учителем программирования, и вам нужно было выбрать один алгоритм сортировки, чтобы научить своих студентов, какой это будет?"
Хм... алгоритмы сортировки - это действительно интуитивный, конкретный способ преподавать некоторые хорошие уроки о нотациях Big O, оптимизации, здравом смысле и информатике в целом, и, возможно, "пузырьковая сортировка" + "выборочная сортировка" + "сортировка слиянием" подход может быть полезным, для сравнения. Я думаю, что наиболее интуитивным (и эффективным во многих случаях) является выборочный тип.
Если вы хотите научить концепции сортировки, то я считаю, что вы должны научить как минимум двум различным способам сортировки, иначе студенты подумают, что сортировка - это примерно один способ, которым вы их учили.
Я думаю, что студенты извлекут максимальную пользу из изучения классического алгоритма O(n^2) (желательно, вставка или сортировка выбора, но не пузырьковая сортировка, которая не имеет оснований для использования в реальных приложениях), а также разделяй и властвуй, алгоритм O(nlogn), такой как быстрая сортировка или сортировка слиянием.
Если вы беспокоитесь о том, что этим видам будет слишком сложно обучать ваших учеников, ознакомьтесь с этими упражнениями из раздела "Информатика без подключения к электросети", которые предназначены для учащихся начальной школы.
Я думал, что сортировку по выбору проще всего понять, и IMO будет лучшим вариантом для сортировки.
Я думаю, что было бы глупо не учить их хотя бы одному алгоритму сортировки O(nlog(n)) вместе с объяснением больших O-обозначений.
Пузырьковая сортировка - это классика, и очень легко понять, почему она работает.
Но если это не очень вводный курс, то он должен включать в себя обзор других алгоритмов сортировки, поскольку это, безусловно, лучший способ показать компромиссы, вовлеченные в разработку алгоритма, и объяснить наилучший случай, наихудший случай, среднее поведение (как во время выполнения, так и в памяти).
Пусть все принесут колоду карт и выберут одну масть. Разделитесь на команды из двух человек. Один тасует 13 карт и кладет их лицом вниз подряд. Партнер получает указывать на две карты. Другой поднимает их, смотрит на них и говорит: "В порядке" или "Не в порядке". Партнер может сказать ему, чтобы они поменяли их и снова сложили (лицом вниз).
Работа партнера заключается в сортировке карточек по порядку (что-то, что вам нужно будет определить заранее).
Когда партнер думает, что они отсортированы, он говорит "Стоп". Другие поворачивают карты лицом вверх, и они проверяют.
Когда это будет сделано, обсудите, что сработало для всех. Тогда поговорим о BUBBLE SORT vs SELECT sort
Тогда поговорим о быстрой сортировке.
Пусть они попробуют каждого из них с их карточным мастом.
Сначала их следует попросить реализовать собственный алгоритм сортировки - с нуля, без предварительной ссылки на какой-либо существующий алгоритм. Делая это, вы узнаете больше о том, как сортировать, чем рассказывать об алгоритме, чтобы они не знали, как он был получен.
Помня о том, что вашему ученику, вероятно, никогда не придется самим кодировать какую-то разновидность, вопрос действительно должен быть решен: "Какова ценность изучения этого алгоритма?". вместо "что делает этот алгоритм?"
Другими словами, ваших учеников должны обучать множеству различных алгоритмов - будь то для сортировки, поиска, сжатия и т. Д., В значительной степени не имеет значения.
Я бы сравнил и сопоставил o(n-квадрат), как сортировка выбора, с сортировкой a o(n log n), как быстрая сортировка.
Но если они не люди, работающие в области компьютерных наук, и не обязательно будут такими, то просто покажите легкий для понимания вид, например, выбор или пузырь.
Я только что сделал это на прошлой неделе с моим ребенком, я попросил его придумать собственный алгоритм сортировки и спросил, сколько времени потребуется, чтобы отсортировать колоду карт, используя его метод. Затем я показал ему Bubble Sort (проще всего объяснить ребенку) "Это пузырь!" и заставил его пересчитать шаги снова. Тогда он понял, что это было проще и быстрее.
Тогда, если вы хотите, вы можете учить более продвинутым (Быстрая сортировка является наиболее удивительным), в идеале вы должны учить как минимум три, которые отличаются (не вариации одного и того же)
Э-э, вы должны дать им O(n^2) и O(n log n) сортировку. Пузырь и Куча были бы моими выборами.
Не забывайте про спагетти... будьте готовы к квантовым вычислениям:-)
Лучшая лекция, которую я когда-либо посещал по алгоритмам, продемонстрировала их все в виде гистограмм, нарисованных с помощью Java-апплетов. Затем вы можете увидеть шаблон сортировки, а также характеристики O(N)...
Научите пузырь, потому что он невероятно прост, а остальное покажите как анимацию?
Я бы научил Bubble сортировать, если бы мне пришлось выбирать только один, так как его легче понять (я думаю). Однако наиболее ценная вещь, которую я извлек из изучения различных алгоритмов сортировки, заключалась в том, что существует несколько способов сделать это (что в итоге привело меня к Perl, но это уже другая история), каждый из которых имеет свои преимущества и недостатки. Таким образом, изучение одного алгоритма сортировки может быть способом пропустить критический аспект всего этого.
Независимо от того, какой алгоритм вы выберете, я советую вам представить два алгоритма (вместо одного) и объяснить компромиссы (в памяти, скорости выполнения и т. Д.), Которые они создают.
Затем вы должны понять, что не существует идеального алгоритма сортировки, который можно было бы слепо применять к любой задаче. Однако есть хорошие кандидаты. На этом этапе покажите им быструю сортировку и самоанализ (как домашнюю работу) и учтите, что ваша задача выполнилась:)
Я думаю, что фильм Sorting Out Sorting, который был выпущен 30 лет назад, все еще является довольно хорошим учебным пособием для лучшего понимания алгоритмов сортировки.. вот 12-скоростная версия
Пузырьковая сортировка является самой легкой для начинающих, а также служит отличным примером того, почему простые решения могут быть дорогими. Может ли быть хорошим способом перейти к асимптотической сложности и обозначению Big-O?
Quicksort, безусловно, является еще одним очень простым для понимания алгоритмом сортировки, и его легко реализовать. У него есть свои "неуместные" версии, о которых интересно думать. И это быстро.
Достаточно быстро для тебя, по крайней мере, старик.
Начните с inserttionSort, затем переходите к mergeSort, quickSort и heapSort, избегайте bubbleSort (есть масса исследований, которые показывают, что inserttionSort не так сложен для понимания / реализации, и в отличие от bubbleSort он имеет практическое применение (быстрее небольшие массивы, чем слияние, например).