Что следует обучать студентов сначала, когда сначала изучают алгоритмы сортировки?

Ответ 1

Я не уверен, что смогу стать преподавателем в области информатики и только научить одному алгоритму сортировки.

Как минимум, ученикам следует преподавать по крайней мере один из основных типов сортировки , а именно: обменный сортировка, сортировка сортировки, сортировку вставки и сортировку слияния. В дополнение к одному из этих типов, я бы также рассмотрел Quicksort, который попадает под заголовок сортировки разделов.

Что касается конкретных видов от каждого из типов, которые я бы рассмотрел:

• Bubble Sort в качестве примера обмена категории сортировки, поскольку это один из простейших типов сортировки и тот, который они, вероятно, уже видели или наткнулись друг на друга. Это также тот вид, который они, скорее всего, будут использовать чаще всего, если им придется сворачивать свои собственные для чего-то простого, поэтому имеет смысл понять их.
• Heapsort из категории сортировки выбора. Вероятно, это будет самый запутанный вид рядом с Quicksort, но как только они поймут, как он устанавливает их для понимания алгоритма Quicksort.
• Вставка Сортировка в качестве примера категории сортировки вставки будет покрыта, поскольку это также простой вид, который может получить много пользы снаружи. Поскольку они могут столкнуться с сценариями, где им необходимо объединить два списка вместе, зная, что это имеет смысл.
• Merge Sort - это несколько специализированный вид, поэтому вы не видите его слишком часто, но он очень хорош в том, что он делает и по-прежнему полезно в ситуациях, когда вам нужно сортировать данные, которые вы получаете по частям.

Если бы мне пришлось сузить все до одного вида, который я мог бы преподавать, но у меня было время, чтобы убедиться, что ученик точно понял, что происходит, тогда я бы научил Quicksort. Хотя это нелегко понять, подавляющее большинство фреймворков используют его для своего алгоритма сортировки, поэтому понимание того, как это работает, полезно в вашем развитии с помощью этой структуры. Кроме того, вполне вероятно, что, если кто-то сможет понять Quicksort, они должны уметь самостоятельно сортировать и сортировать Bubble.

Ответ 2

Независимо от того, какой учебный алгоритм преподаётся, если ученики не узнают о bogosort, они упускаются, и учитель теряет очевидный способ привлечь свою аудиторию:)

Ответ 3

Пусть ваши ученики решат.

Прежде чем вводить какие-либо алгоритмы сортировки, дайте каждому учащемуся несколько игральных карт, возможно, около 10. Затем попросите их отсортировать карточки. Попросите их записать шаги, которые они предпримут, что будет по сути их алгоритмом. Вероятно, они обнаружат сортировку вставки или выбора. Вы также можете попросить их оценить, сколько шагов они предпримут, если у них будет 100 или 1000 карт, что хорошо ведет к большой нотации.

PS - Кто-нибудь думает, что они обнаружат сортировку пузырьков?

Ответ 4

Если вы хотите научить сортировке, то, пожалуй, проще всего понять, как выглядит пузырь. Если вы хотите преподавать алгоритмы сортировки, то вам действительно нужно преподавать quicksort, mergesort, insertsort и, возможно, даже heapsort, чтобы учащиеся могли почувствовать компромиссы между различными методами сортировки.

Ответ 5

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

Ответ 6

Я сначала узнал Bubble Sort - думаю, если вы делаете только одно, вам, вероятно, нужно будет сделать один из алгоритмов O (n ^ 2), потому что их легче понять.

Есть много визуализаторов вида, которые помогут быстро показать сравнение:

• http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html
• http://math.hws.edu/TMCM/java/xSortLab/
• http://vision.bc.edu/~dmartin/teaching/sorting/anim-html/all.html
• http://maven.smith.edu/~thiebaut/java/sort/

Ответ 7

Сортировка сортировки - это, вероятно, самый простой алгоритм сортировки для обучения и простейшего понимания. Это также отличный пример того, почему простые решения не всегда являются лучшими, что может привести к обсуждению более интересных и быстрых типов, таких как mergesort и quicksort.

Ответ 8

Я считаю, что методы сортировки - очень хороший пример того, что такое алгоритм. Но это только хороший пример, когда вы сравниваете различные методы. Если вы можете только учить его, я не уверен, что это стоит.

Реалистично, мы называем метод сортировки в некоторых рамках. Поэтому, если вы не можете эффективно преподавать сортировочные алориты, это может не стоить времени.

Никто больше не должен писать метод сортировки, но это все еще очень хороший пример воздействия алгоритмов.

Ответ 9

Я бы посоветовал как Selection, так и Merge Sort на общих алгоритмах сортировки. Оба они относительно прямолинейны по сравнению с их друзьями. Но если вы можете только учить одного, и люди могут справиться с этим, я бы пошел с Merge Sort. Поскольку сортировка слияния эффективна, стабильна и учит нескольким важным понятиям (слияние, разделение и завоевание).

Выбор Сортировка:
Найдите минимальное/максимальное значение и поместите его на место, затем сделайте это снова в остальной части списка... это очень интуитивно понятно. Для меня выбор гораздо более интуитивно понятен, чем даже сорт пузыря. Вероятно, вы могли бы это учить за очень короткое время. И у людей, реализующих это, будет чувство удовлетворения... Хотя Bubble и Insertion могут уйти рано и не будут тратить время на сортированный список. Выбор, вероятно, самый простой способ сделать. Вставка, вероятно, сложнее всего реализовать.

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

Основная концепция слияния интуитивно понятна. Возьмите меньший элемент из отсортированного списка и поместите его в окончательный список. И деление проблемы сортировки слияния вверх также является своего рода интуитивным.
mergesort (первая половина) mergesort (вторая половина)
слияние (первая половина, вторая половина)

Если вы можете преподавать только один вид и делать это быстро (или аудитория совсем не заинтересована), я бы склонялся к выбору, потому что это сложнее, и выбор можно было быстро обучать. Но если аудитория более мотивирована, я бы сделал Merge, потому что он учит многим дополнительным фундаментальным понятиям.

Из более эффективных сортов это намного проще, чем быстрый и куча сортировки. Хотя быстрая сортировка, вероятно, самая быстрая на практике (если у вас много RAM), а куча, вероятно, может сортировать самые большие списки (если они реализованы не рекурсивно).

Ковш Сортировать:
Я бы коснулся этого, потому что он также интуитивно понятен и представляет собой другой тип алгоритма сортировки. Во многих ситуациях это подходит, и время O (n) очень привлекательно.

Подсчет Сортировка:
Он имеет свое применение. Есть некоторые случаи, когда это очень эффективно... Это также относительно легко.

Ответ 10

Я бы научил сортировку "вызывать фреймворк".

Было бы эффективно преподавать и изучать этот вид. Студенты имели бы высокую степень успеха и низкий уровень ошибок при реализации такого рода.

Изменить: Есть много критических комментариев по этому вопросу о качестве моего одного класса сортировки. Эти критические замечания применимы к любому ответу на этот вопрос, который - "Если бы вы были учителем программирования, и вам нужно было выбрать один алгоритм сортировки, чтобы научить ваших учеников одному?

Ответ 11

Uhm... алгоритмы сортировки - действительно интуитивный, конкретный способ преподавания хороших уроков о нотах Big O, оптимизации, здравого смысла и компьютерных наук в целом и, возможно, "сортировка пузыря" + "выбор сортировки" + merge sort "может оказаться полезным для сравнения. Я считаю, что наиболее интуитивным (и эффективным во многих случаях) является сортировка.

Ответ 12

Я думаю, что только учение одного рода искажает. Помните, что "Все быстро" для Small n, поэтому с точки зрения обучения, это не вопрос производительности, а понимание алгоритма.

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

Ответ 13

Это будет сортировка radix. Потому что это удивительно легко и пока не очевидно. Такие вещи нужно просто научить.

Ответ 14

Сорт Bubble является классическим, и очень легко понять, почему он работает.

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

Ответ 15

Я думал, что выбор сортировки был самым простым для понимания, и ИМО была бы лучшей, чтобы ввести сортировку.

Я думаю, было бы глупо не учить им хотя бы один алгоритм сортировки O (nlog (n)), а также объяснение большой записи O.

Ответ 16

Пусть все приносят колоду карт и выбирают один костюм. Разделитесь на две команды. Один перетасовывает 13 карт и кладет их лицом вниз подряд. Партнер указывает на две карты. Другой подбирает их, смотрит на них и говорит "В порядке" или "Не в порядке", Затем паттерн может сказать ему обменять их и снова положить их (лицом вниз)

Задача партнера - сортировать карты по порядку (что вам нужно определить спереди).

Когда собеседник считает, что они отсортированы, он говорит "Стоп". Другой поворачивает карты лицом вверх, и они проверяют.

Когда это будет сделано, обсудите, что сработало для всех. Затем расскажите о выборе BUBBLE SORT vs SELECTION

Затем поговорим о QUICK SORT.

Попросите их попробовать каждый из них с их карточным карточкой.

Ответ 17

Если вы хотите научить концепции сортировки, то я считаю, что вы должны преподавать по крайней мере два разных способа сортировки - иначе ученики будут думать, что сортировка - это только то, как вы их научили.

Я думаю, что ученики получат максимальную отдачу от изучения классического алгоритма O (n ^ 2) (желательно сортировки вставки или выбора, но, пожалуйста, не пузырьковая сортировка, которая не имеет оснований для того, чтобы быть используется в реальных приложениях), а также алгоритм O (nlogn) с делением и победой, такой как сортировка quicksort или merge.

Если вы опасаетесь, что эти виды будут слишком трудными для обучения ваших учеников, посмотрите эти действия из Computer Science Unplugged, которые предназначены для учащихся начальной школы.

Ответ 18

Лучшая лекция, которую я когда-либо посещал на алгоритмах, продемонстрировал их все как графические диаграммы, нарисованные с помощью java-апплетов. Затем вы можете увидеть структуру сортировки, а также характеристики O (N)...

Научите пузырь, потому что он невероятно прост и показывает остальное как анимацию, может быть?

Ответ 19

Сорт Bubble является самым легким для новичков, и он также служит отличным примером того, почему простые решения могут быть дорогими. Может ли быть хорошим способом перечислить асимптотическую сложность и обозначение большого О?

Ответ 20

Я бы научил Bubble сортировать, если бы мне пришлось выбирать только один, так как это проще понять (я думаю). Тем не менее, самое ценное, что я получил от изучения различных алгоритмов сортировки, было то, что было более одного способа сделать это (что в конечном итоге привело меня к Perl, но эта другая история), каждая из которых имеет преимущества и недостатки. Таким образом, изучение одного алгоритма сортировки может быть способом пропустить критический аспект всего этого.

Ответ 21

Quicksort - это, безусловно, еще один очень простой в понимании алгоритм сортировки, и он является инструментом для его реализации. Он имеет на месте amd "вне места" версии, которые интересно думать. И это быстро.

Достаточно быстро для вас, по крайней мере, старик.

Ответ 22

Er, вы должны дать им выбор O (n ^ 2) и O (n log n). Пузырь и куча были бы моими выборами.

Ответ 23

Независимо от выбранного алгоритма, я рекомендую вам представить два алгоритма (вместо одного) и объяснить компромиссы (в памяти, скорость выполнения и т.д.), которые они делают.

Тогда вы должны забить его, чтобы не было такого понятия, как идеальный алгоритм сортировки, который можно было бы слепо применить к любой задаче. Однако есть хорошие кандидаты. На этом этапе покажите им сортировку quicksort и introspection (как домашнее задание) и решите вашу задачу:)

Ответ 24

Помня о том, что вашему ученику, вероятно, никогда не придется самостоятельно кодировать сортировку, вопрос действительно должен быть решен: "Какова ценность изучения этого алгоритма?" вместо "что делает этот алгоритм?"

Ответ 25

IntroSort - отличный алгоритм для обучения, когда ученики научились понимать Quick и Heap sort. IntroSort (короткий для Introspective sort) запускается как QuickSort и переключается на HeapSort, если глубина рекурсии превышает уровень, основанный на логарифме количества отсортированных элементов.

В целом вы получаете лучшие из быстрых и быстрых миров и наихудшего времени работы O (n log n).

IntroSort в Википедии

Ответ 26

Я бы сравнил и сравнил o (n-squared), например сортировку с сортировкой o (n log n), типа quicksort.

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

Ответ 27

Я только что сделал это на прошлой неделе с моим ребенком Я прошу его придумать свой собственный алгоритм сортировки и спросить, сколько времени потребуется, чтобы отсортировать колоду карт, используя его метод. Затем я показал ему Bubble Sort (проще всего объяснить ребенку) "Это пузырь!" и заставил его посчитать шаги снова. Он понял, что это было легче и быстрее.

Затем, если вы хотите, вы можете научить более продвинутых (Quicksort является самым неожиданным), В идеале вы должны учить трех, по крайней мере, разных (не вариаций одного и того же)

Ответ 28

Если вы в конечном итоге можете полностью учить алгоритм ОДИН, я думаю, что SelectionSort еще проще учить (и внедрять IMHO) в качестве BubbleSort. Это может быть крайне неэффективно, но каждый получит свою концепцию, каждый с небольшим знанием программирования может прочитать свой код, и есть одна вещь, которая делает SelectionSort весьма уникальной среди всех алгоритмов сортировки: для n-1 свопов требуется только n-1 свопов entries:-) Не только, что ему никогда не нужно делать больше, чем n-1 свопов, на самом деле ему нужно точно n-1 свопов. Количество выполненных свопов является 100% детерминированным и известным до его начала. Я думаю, что это неверно для любого другого алгоритма сортировки на месте (хотя люди могут исправить меня в комментариях).

В противном случае я голосую за BubbleSort и SelectionSort, это проще всего понять и показать, как сортировать простой способ (они достаточно просты, студенты могут придумать эти решения, даже не слышав о каком-либо алгоритме сортировки) иногда не очень эффективный. В отличие от этого, я бы показал QuickSort и MergeSort, являясь очень хорошими алгоритмами разделения и завоевания, а также очень быстрыми.

Алгоритмы, которые я бы не использовал, поскольку их концепция сложнее получить, являются ShellSort, RadixSort, HeapSort и BucketSort. Кроме того, они довольно специальные (вы обычно используете их только при сортировке определенного типа данных или при наличии определенных ограничений для сортировки).

Вы можете упомянуть младшую сестру ShellSort, InsertionSort (которая в основном представляет собой оболочку, где ширина шага, наконец, достигает одного), но только потому, что многие реализации QuickSort используют InesrtionSort в качестве спада, когда рекурсия становится слишком глубокой (или оставшийся набор данных для рекурсивного сортировки становится слишком маленьким)... но здесь он начинает становиться действительно сложным, и вы не должны делать его слишком сложным.

Ответ 29

Им следует сначала попросить реализовать свой собственный алгоритм сортировки - с нуля, без ссылки на любой существующий алгоритм заранее. Это будет объяснять им больше, чем рассказать им об алгоритме, что они не имели бы представления о том, как оно было получено.

Ответ 30

Я думаю, что фильм Sorting Out Sorting, который был выпущен 30 лет назад, по-прежнему является довольно хорошей учебной помощью, чтобы лучше понять сортировать алгоритмы.. heres 12x speed version