Следующие исправленные упражнения относятся к алгоритмам сортировки: сортировка выбором, сортировка вставками, пузырьковая сортировка, коктейльная сортировка, быстрая сортировка и сортировка слиянием.
Итеративные сортировки: сортировка по выбору
В массиве из n элементов (пронумерованных от 0 до n-1) принцип сортировки выбором следующий:
- искать наименьший элемент массива и обменивать его на элемент с индексом 0;
- найти второй наименьший элемент массива и обменять его на элемент с индексом 1;
- продолжайте таким образом, пока массив не будет полностью отсортирован.
Итеративные сортировки: сортировка вставками
Сортировка вставками — это алгоритм классическая сортировка. Большинство людей, естественно, используют его для сортировки игральных карт.
Сортировка вставками рассматривает каждый элемент массива и вставляет его в нужное место среди уже отсортированных элементов. Таким образом, при рассмотрении элемента предшествующие ему элементы уже отсортированы, а следующие за ним еще не отсортированы.
Чтобы найти место для вставки элемента среди предыдущих, его нужно сравнить с последними и сдвинуть их, чтобы освободить место для вставки. Смещение занимает место, оставленное свободным рассматриваемым элементом. На практике эти два действия выполняются за один проход, который состоит из «поднятия» элемента по мере его продвижения до тех пор, пока он не столкнется с меньшим элементом.
Вот пример, чтобы лучше понять принцип на доске [6, 5, 3, 1, 8, 7, 2, 4].
Вот его псевдокод:
То сложность сортировки вставками составляет O(n²) в худшем случае и линейна в лучшем случае. В худшем случае, достигаемом при сортировке массива в обратном порядке, алгоритм выполняет около n²/2 присваиваний и сравнений; Если массив уже отсортирован, имеется n-1 сравнений и не более n присваиваний.
Итеративные сортировки: пузырьковая сортировка
Пузырьковая или расширенная сортировка — это алгоритм сортировки. Он состоит в многократном сравнении последовательных элементов массива и замене их местами, если они плохо отсортированы. Своему названию она обязана тому, что быстро перемещает самые крупные элементы в конец картины, подобно пузырькам воздуха, которые бы быстро поднялись на поверхность жидкости.
Алгоритм перебирает массив и сравнивает последовательные элементы. Когда два последовательных элемента расположены не по порядку, они меняются местами.
После первого полного сканирования массива самый большой элемент обязательно оказывается в конце массива, в его конечной позиции. Действительно, как только во время обхода встречается самый большой элемент, он плохо сортируется по отношению ко всем последующим элементам, поэтому заменяется следующим до достижения конца обхода.
После первого прогона, когда самый большой элемент находится в своей конечной позиции, его больше не нужно обрабатывать. Однако остальная часть картины по-прежнему грязная. Поэтому его нужно пройти снова, остановившись на предпоследнем элементе. После этого второго хода два самых больших элемента занимают свое окончательное положение. Поэтому необходимо повторять пути таблицы, пока два самых маленьких элемента не будут помещены в их окончательное положение.
А оптимизация обычная практика этой сортировки состоит в том, чтобы прерывать ее, как только обход элементов, возможно, еще находящихся в беспорядке (внутренний цикл), выполняется без перестановки. Фактически это означает, что весь массив отсортирован. Для этой оптимизации требуется дополнительная переменная.
Вместо первого For можно поставить while. В этом случае необходимо увеличить i внутри цикла и больше не нужен разрыв.
Для неоптимизированной сортировки временная сложность составляет O (n²), где n — размер массива.
Для оптимизированной сортировки количество итераций внешнего цикла составляет от 1 до n. Действительно, можно показать, что после i-го шага последние i элементов массива находятся на своих местах. На каждой итерации выполняется ровно n-1 сравнений и не более n-1 перестановок.
Наихудший случай (n итераций) достигается, когда наименьший элемент находится в конце массива. Тогда сложность равна O(n²). Наилучший случай (одна итерация) достигается, когда массив уже отсортирован. В этом случае сложность линейна.
Итеративная сортировка: коктейльная сортировка
Коктейльная сортировка, сортировка в шейкере или двусторонняя пузырьковая сортировка — это разновидность пузырьковой сортировки1, которая одновременно является и алгоритмом сортировки, и сравнительной сортировкой. Отличие этого алгоритма от пузырьковой сортировки состоит в том, что он выполняет сортировку в каждом направлении при каждом проходе по сортируемому списку.
Этот алгоритм сортировки лишь немногим сложнее для понимания и реализации, чем пузырьковая сортировка, и он частично решает проблему черепашьей пузырьковой сортировки (черепашки — это маленькие элементы в конце исходного списка, которые возвращаются очень медленно, на одно место за один раз). итерации, к их конечному местоположению).
Во время первого прохода первый обход вправо перемещает элементы, большие, чем их непосредственные соседи справа, и, в частности, шаг за шагом перемещает самый большой элемент списка в его окончательное положение в конце листинга. Затем второе сканирование слева переместит элементы, меньшие, чем их непосредственные соседи слева, и, в частности, переместит наименьший элемент в списке на его конечное место вверху списка. влево. Точно так же во время второго прохода второй по величине элемент и второй по величине элемент, в свою очередь, соединятся со своим конечным местоположением и так далее.
После прохождения i первые элементы i и последние элементы i находятся в своем конечном местоположении. Поэтому их больше не нужно проверять. Поэтому можно оптимизировать этот алгоритм, проверяя на каждом проходе только центральную часть списка, еще не отсортированную окончательно. Это позволяет вдвое сократить количество сравнений.
Производным от пузырьковой сортировки является коктейльная сортировка или шейкерная сортировка. Этот метод сортировки основан на следующем наблюдении: при пузырьковой сортировке элементы могут быстро перемещаться в конец массива, но перемещаются в начало массива только на одну позицию за раз.
Идея сортировки коктейлей состоит в том, чтобы чередовать направление движения. Мы получаем сортировку немного быстрее, с одной стороны, потому что она требует меньше сравнений, с другой стороны, потому что она снова считывает самые последние данные на момент смены направления (таким образом, они все еще находятся в кеше памяти). Однако количество перестановок, которые необходимо выполнить, идентично. Таким образом, время выполнения всегда пропорционально n², поэтому посредственно.
Сложность в наихудшем и наилучшем случаях в O(.) такая же, как и при пузырьковой сортировке.
Рекурсивные сортировки: быстрая сортировка
Быстрая сортировка — это алгоритм сортировки сравнением, его работа довольно проста для понимания и широко используется для больших входных данных. Действительно, он имеет среднюю сложность O(NlogN) и O(N²) в худшем случае.
Быстрая сортировка использует принцип разделяй и властвуй, то есть мы выберем элемент таблицы (который мы называем сводным), затем мы реорганизуем исходную таблицу в две подтаблицы:
- Один, содержащий элементы ниже точки поворота.
- Другой, содержащий элементы над точкой опоры.
Мы продолжаем этот процесс (который мы называем разделение, т. е. выберите опорную точку и реорганизуйте массив), пока не получите массив, разделенный на N подмассивов (N — размер массива), который, следовательно, отсортирован.
Возьмем 5, 9, 7, 3, 8 как последовательность чисел и отсортируем ее в порядке возрастания с помощью алгоритма быстрой сортировки:
5, 9, 7, 3, 8 -> выбираем стержень, в нашем случае я выбираю средний элемент, 7.
5, 3 | 7 | 9, 8 -> мы разрезаем картину на три части: часть с элементами ниже оси (5 и 3), часть, содержащую точку опоры (7), и часть с элементами над точкой опоры (9 и 8). Мы уже можем сказать, что поставили точку опоры на ее окончательное место в картине, так как другие элементы либо выше, либо ниже ее.
5, 3 | 7 | 9, 8 -> мы начинаем снова, снова выбирая сводную точку для каждой созданной подтаблицы.
3 | 5 | 7 | 8 | 9 -> последний шаг разбиения, теперь ни один подмассив не содержит более одного элемента, поэтому сортировка завершена.
Рекурсивные сортировки: сортировка слиянием
Сортировка слиянием — один из самых популярных и эффективных алгоритмов сортировки. И это основано на парадигме «Разделяй и властвуй».
Предположим, нам нужно отсортировать массив T. Подзадача будет заключаться в сортировке подраздела (подмассива) этого массива, начиная с начала индекса и заканчивая концом индекса, обозначаемым T[start..end].
Если midpoint — это середина между start и end, то мы можем разбить подмассив T[start..end] на два массива T[start..mid] и T[mid + 1, end]. На этапе Conquer мы пытаемся отсортировать подсети T[start..middle] и T[middle + 1, end]. Если мы еще не дошли до базового случая (подмассив содержит только один элемент), мы снова разбиваем эти два подмассива и пытаемся их отсортировать.
Когда этап завоевания достигает базового этапа и мы получаем два отсортированных подмассива T[start..mid] и T[mid + 1, end] для массива T[start..mid], мы их объединяем полученные результаты путем создания отсортированного массива T[start..mid] из двух отсортированных подмассивов T[start..mid] и T[mid + 1, end].
Функция triMerge неоднократно разбивает массив на две половины (два подмассива), пока мы не достигнем точки, в которой мы пытаемся выполнить triMerge для подмассива размера 1, т. е. start == end.
После этого запускается функция слияния, которая объединяет отсортированные массивы в массив большего размера, пока весь массив не будет объединен. После этого функция слияния извлекает отсортированные подмассивы и объединяет их для постепенной сортировки всего массива.
Временная сложность сортировки слиянием составляет O(nLogn) во всех трех случаях (наихудший, средний и лучший), потому что сортировка слиянием всегда разбивает массив на две половины и требует линейного времени для слияния двух половин.
Этот псевдокод очень упрощен:
- В функции triFusion мы используем рекурсия чтобы вырезать, а затем объединить наш массив, и мы останавливаем рекурсивные вызовы, когда в обрабатываемом подмассиве остается только один элемент.
- Функция слияния довольно явная, она позволяет нам создать из двух отсортированных подмассивов массив, также отсортированный за линейное время.
RU 
FR 
EN 
ES