Добавлен: 23.05.2023
Просмотров: 139
Скачиваний: 4
Как отмечалось, алгоритм редко используется на практике, поскольку имеет низкую производительность.
|
Лучший случай |
Средний случай |
Наихудший случай |
|
O(n) |
O(n2) |
O(n2) |
2.3 Сортировка вставками
Сортировка вставками – простой алгоритм сортировки, преимущественно использующийся в учебном программировании. К положительной стороне метода относится простота реализации, а также его эффективность на частично упорядоченных последовательностях, и/или состоящих из небольшого числа элементов. Тем не менее, высокая вычислительная сложность не позволяет рекомендовать алгоритм в повсеместном использовании.
Рассмотрим алгоритм сортировки вставками на примере колоды игральных карт. Процесс их упорядочивания по возрастанию будет следующим. Обратим внимание на вторую карту, если ее значение меньше первой, то меняем эти карты местами, в противном случае карты сохраняют свои позиции, и алгоритм переходит к шагу 2. На 2-ом шаге смотрим на третью карту, здесь возможны четыре случая отношения значений карт:
- n1 < n3; n2 < n3;
- n1 > n3; n2 > n3;
- n1 < n3 < n2;
- n1 > n3; n2 < n3.
В первом случае не происходит никаких перестановок. Во втором – вторая карта смещается на место третьей, первая на место второй, а третья карта занимает позицию первой. В третьем случае первая карта остается на своем месте, в то время как вторая и третья меняются местами. Ну и наконец, последний случай требует рокировки лишь первой и третьей карт. Все последующие шаги полностью аналогичны расписанным выше.
Рассмотрим на примере числовой последовательности процесс сортировки методом вставок (Рисунок 1). Клетка, выделенная темно-серым цветом – активный на данном шаге элемент, ему также соответствует i-ый номер. Светло-серые клетки это те элементы, значения которых сравниваются с i-ым элементом. Все, что закрашено белым – не затрагиваемая на шаге часть последовательности.
Рисунок 1
Таким образом, получается, что на каждом этапе выполнения алгоритма сортируется некоторая часть массива, размер которой с шагом увеличивается, и в конце сортируется весь массив целиком.
Код на С++:
|
int i, j, k = 0, tmp = 0; void InsertSort(int *mas, int n) { for (i = 0; i<n - 1; i++) { k = i + 1; tmp = mas[k]; for (j = i + 1; j>0; j--) { if (tmp<mas[j - 1]) { mas[j] = mas[j - 1]; k = j - 1; } } mas[k] = tmp; } cout << endl << "Отсортированный массив: "; for (i = 0; i<n; i++) cout << mas[i] << " "; } |
В основной части выполняются три операции: определение количества элементов в массиве, ввод этих элементов и вызов подпрограммы.
Подпрограмма состоит из алгоритма сортировки и цикла, выводящего результирующую упорядоченную последовательность. Алгоритм включает в себя классическую для многих алгоритмов сортировки структуру вложенных циклов. Количество итераций внешнего цикла не превышает n-1, где n – число элементов в массиве; внутренний цикл, начиная с шага i+1, заканчивает свое выполнение при j=0 (значение переменной-счетчика j уменьшается с каждым шагом на 1). Переменным k и tmp на i-ом шаге присваиваются значения, зависящие от шага и значения элемента массива mas на этом шаге. В переменной tmp храниться значение элемента массива mas[i+1], оно во внутреннем цикле сравнивается со значениями других элементов. Переменная k запоминает индекс элемента, который последним был больше tmp, и ему, по завершению работы внутреннего цикла, присваивается значение переменной tmp.
|
Лучший случай |
Средний случай |
Наихудший случай |
|
O(n) |
O(n2) |
O(n2) |
2.4 Быстрая сортировка
Выбирая алгоритм сортировки для практических целей, программист, вполне вероятно, остановиться на методе, называемом «Быстрая сортировка» (также «qsort» от англ. quick sort). Его разработал в 1960 году английский ученый Чарльз Хоар, занимавшийся тогда в МГУ машинным переводом.
Алгоритм, по принципу функционирования, входит в класс обменных сортировок, выделяясь при этом высокой скоростью работы.
Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному. Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.
Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:
- разбиение массива относительно опорного элемента;
- рекурсивная сортировка каждой части массива.
Разбиение массива. Еще раз об опорном элементе. Его выбор не влияет на результат, и поэтому может пасть на произвольный элемент. Тем не менее, как было замечено выше, наибольшая эффективность алгоритма достигается при выборе опорного элемента, делящего последовательность на равные или примерно равные части. Но, как правило, из-за нехватки информации не представляется возможности наверняка определить такой элемент, поэтому зачастую приходиться выбирать опорный элемент случайным образом.
В следующих пунктах описана общая схема разбиения массива (сортировка по возрастанию):
- вводятся указатели frst и lst для обозначения начального и конечного элементов последовательности, а также опорный элемент mid;
- вычисляется значение опорного элемента (frst+lst)/2, и заноситься в переменную mid;
- указатель frst смещается с шагом в 1 элемент к концу массива до тех пор, пока Mas[frst]>mid. А указатель lst смещается от конца массива к его началу, пока Mas[lst]<mid;
- каждые два найденных элемента меняются местами;
- пункты 3 и 4 выполняются до тех пор, пока frst<lst.
После разбиения последовательности следует проверить условие на необходимость дальнейшего продолжения сортировки его частей. Этот этап будет рассмотрен позже, а сейчас на конкретном примере выполним разбиение массива.
Имеется массив целых чисел Mas [6 7 2 5 9 1 3 8], состоящий из 8 элементов Mas[1..8]. Начальным значением frst будет 1, а lst – 8.
В качестве опорного элемента возьмем элемент со значением 5, и индексом 4. Его мы вычислили, используя выражение (frst+lst)/2, отбросив дробную часть. Теперь mid=5.
Первый элемент левой части сравнивается с mid. Mas[1]>mid, следовательно frst остается равным 1. Далее, элементы правой части сравниваются с mid. Проверяется элемент с индексом 8 и значением 8. Mas[8]>mid, следовательно lst смещается на одну позицию влево. Mas[7]<mid, следовательно lst остается равным 7. На данный момент frst=1, а lst=7. Первый и седьмой элементы меняются местами. Оба указателя смещаются на одну позицию каждый в своем направлении - [3 7 2 5 9 1 6 8].
Алгоритм снова переходит к сравнению элементов. Второй элемент сравнивается с опорным: Mas[2]>mid, значит frst остается равным 2. Далее, элементы правой части сравниваются с mid. Проверяется элемент с индексом 6 и значением 1: Mas[6]<mid, значит lst не изменяет своей позиции. На данный момент frst=2, а lst=6. Второй и шестой элементы меняются местами. Оба указателя смещаются на одну позицию каждый в своем направлении – [3 1 2 5 9 7 6 8].
Алгоритм снова переходит к сравнению элементов. Третий элемент сравнивается с опорным: Mas[3]<mid, таким образом, frst смещается на одну позицию вправо. Далее, элементы правой части сравниваются с mid. Проверяется элемент с индексом 5 и значением 9: Mas[5]>mid, следовательно, lst смещается на одну позицию влево. Теперь frst=lst=4, а значит, условие frst<lst не выполняется, этап разбиения завершается –
[3 1 2 5 9 7 6 8].
На этом этап разбиения закончен. Массив разделен на две части относительно опорного элемента. Осталось произвести рекурсивное упорядочивание его частей.
Рекурсивная сортировка каждой части массива. Если в какой-то из получившихся в результате разбиения массива частей находиться больше одного элемента, то следует произвести рекурсивное упорядочивание этой части, то есть выполнить над ней операцию разбиения, описанную выше. Для проверки условия «количество элементов > 1», нужно действовать примерно по следующей схеме:
Имеется массив Mas[L..R], где L и R – индексы крайних элементов этого массива. По окончанию разбиения, указатели frst и lst оказались примерно в середине последовательности, тем самым образуя два отрезка: левый от L до lst и правый от frst до R. Выполнить рекурсивное упорядочивание левой части нужно в том случае, если выполняется условие L<lst. Для правой части условие аналогично: frst<R.
Код программы на C++:
|
const int n = 7; int frst, lst; void quicksort(int *mas, int frst, int lst) { int mid, count; int f = frst, l = lst; mid = mas[(f + l) / 2]; do { while (mas[f]<mid) f++; while (mas[l]>mid) l--; if (f <= l) { count = mas[f]; mas[f] = mas[l]; mas[l] = count; f++; l--; } } while (f<l); if (frst<l) quicksort(mas, frst, l); if (f<lst) quicksort(mas, f, lst); } |
Стоит отметить, что быстрая сортировка может оказаться малоэффективной на массивах, состоящих из небольшого числа элементов, поэтому при работе с ними разумнее отказаться от данного метода. В целом алгоритм неустойчив, а также использование рекурсии в неверно составленном коде может привести к переполнению стека. Но, несмотря на эти и некоторые другие минусы, быстрая сортировка все же является одним из самых эффективных и часто используемых методов.
|
Лучший случай |
Средний случай |
Наихудший случай |
|
O(n log n) |
O(n log n) |
O(n2) |
В 1959 году американский ученый Дональд Шелл опубликовал алгоритм сортировки, который впоследствии получил его имя – «Сортировка Шелла». Этот алгоритм может рассматриваться и как обобщение пузырьковой сортировки, так и сортировки вставками.
Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз.
Далее, на примере последовательности целых чисел, показан процесс сортировки массива методом Шелла (Рисунок 2). Для удобства и наглядности, элементы одной группы выделены одинаковым цветом.
Рисунок 2
Первое значение, соответствующее расстоянию d равно 10/2=5. На каждом шаге оно уменьшается вдвое. Элементы, входящие в одну группу, сравниваются и если значение какого-либо элемента, стоящего левее того с которым он сравнивается, оказывается больше (сортировка по возрастанию), тогда они меняются местами. Так, элементы путем внутригрупповых перестановок постепенно становятся на свои позиции, и на последнем шаге (d=1) сортировка сводится к проходу по одной группе, включающей в себя все N элементов массива. При этом число требуемых обменов оказывается совсем небольшим.
Код на С++:
|
int i, j, n, d, cnt; void Shell(int A[], int n) { d = n; d = d / 2; while (d>0) { for (i = 0; i<n - d; i++) { j = i; while (j >= 0 && A[j]>A[j + d]) { cnt = A[j]; A[j] = A[j + d]; A[j + d] = cnt; j--; } } d = d / 2; } for (i = 0; i<n; i++) cout << A[i] << " "; } |
Сортировка Шелла уступает в эффективности быстрой сортировки, но выигрывает у сортировки вставками.
|
Лучший случай |
Средний случай |
Наихудший случай |
|
O(n log n) |
O(n2) |
Зависит от расстояния |
2.5 Шейкерная сортировка
Рассматриваемый алгоритм имеет несколько непохожих друг на друга названий. Среди них: сортировка перемешиванием, двунаправленная пузырьковая сортировка, шейкерная сортировка, пульсирующая сортировка (ripple sort), трансфертная сортировка (shuttle sort), и даже сортировка «счастливый час» (happy hour sort). Второй вариант (двунаправленная пузырьковая сортировка) наиболее точно описывает процесс работы алгоритма. Здесь, в его название, довольно-таки удачно включен термин «пузырьковая». Это действительно альтернативная версия известного метода, модификации в котором заключаются, по большей части, в реализации, упомянутой в названии, двунаправленности: алгоритм перемещается, ни как в обменной (пузырьковой) сортировке – строго снизу вверх (слева направо), а сначала снизу вверх, потом сверху вниз.