Сортировка вставками


ОПИСАНИЯ КОМБИНАТОРНЫХ АЛГОРИТМОВ (сортировка)

 

Сортировка вставками – простой алгоритм сортировки, преимущественно использующийся в учебном программировании. К положительной стороне метода относится простота реализации, а также его эффективность на частично упорядоченных последовательностях, и/или состоящих из небольшого числа элементов. Тем не менее, высокая вычислительная сложность не позволяет рекомендовать алгоритм в повсеместном использовании.

Рассмотрим алгоритм сортировки вставками на примере колоды игральных карт. Процесс их упорядочивания по возрастанию (в колоде карты расположены в случайном порядке) будет следующим. Обратим внимание на вторую карту, если ее значение меньше первой, то меняем эти карты местами, в противном случае карты сохраняют свои позиции, и алгоритм переходит к шагу 2. На 2-ом шаге смотрим на третью карту, здесь возможны четыре случая отношения значений карт:

1. первая и вторая карта меньше третьей;

2. первая и вторая карта больше третьей;

3. первая карта уступает значением третьей, а вторая превосходит ее;

4. первая карта превосходит значением третью карту, а вторая уступает ей.

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

Рассмотрим на примере числовой последовательности процесс сортировки методом вставок. Клетка, выделенная темно-серым цветом – активный на данном шаге элемент, ему также соответствует i-ый номер. Светло-серые клетки это те элементы, значения которых сравниваются с i-ым элементом. Все, что закрашено белым – не затрагиваемая на шаге часть последовательности.

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

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

Код программы на C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include "stdafx.h"#include <iostream> using namespace std; int i, j, key=0, temp=0; void InsertSort(int *mas, int n) //сортировка вставками { for (i=0; i<n-1; i++) { key=i+1; temp=mas[key]; for (j=i+1; j>0; j--) { if (temp<mas[j-1]) { mas[j]=mas[j-1]; key=j-1; } } mas[key]=temp; } cout<<endl<<"Результирующий массив: "; for (i=0; i<n; i++) //вывод массива cout<<mas[i]<<" "; } //главная функция void main () { setlocale(LC_ALL, "Rus"); int n; cout<<"Количество элементов в массиве > "; cin>>n; int *mas=new int[n]; for (i=0; i<n; i++) //ввод массива { cout<<i+1<<" элемент > "; cin>>mas[i]; } InsertSort(mas, n); //вызов функции delete[] mas; system("pause>>void"); }

. В основной части выполняются три операции: определение количества элементов в массиве, ввод этих элементов и вызов подпрограммы. Подпрограмма состоит из алгоритма сортировки и цикла, выводящего результирующую упорядоченную последовательность. Алгоритм включает в себя классическую для многих алгоритмов сортировки структуру вложенных циклов. Количество итераций внешнего цикла не превышает n-1, где n – число элементов в массиве; внутренний цикл, начиная с шага i+1, заканчивает свое выполнение при j=0 (значение переменной-счетчика j уменьшается с каждым шагом на 1). Переменным key и temp на i-ом шаге присваиваются значения, зависящие от шага и значения элемента массива mas на этом шаге. В переменной temp храниться значение элемента массива mas[i+1], оно во внутреннем цикле сравнивается со значениями других элементов. Key запоминает индекс элемента, который последним был больше temp, и ему, по завершению работы внутреннего цикла, присваивается значение переменной temp.

Гномья сортировка

Гномья сортировка впервые была предложена 2 октября 2000 года Хамидом Сарбази-Азадом (Hamid Sarbazi-Azad). Он назвал ее «Глупая сортировка, простейший алгоритм сортировки всего с одним циклом…». И действительно, глупый этот метод или нет, но в нем задействован, никак в большинстве сортировок – два или более циклов, а только один. Позже, голландский ученый Дик Грун, на страницах одной из своих книг, привел для гномьей сортировки следующую аналогию.

 

Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (Du.: tuinkabouter). Here is how a garden gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise he swaps them and steps one pot backwards. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.

Перевод:

Гномья сортировка основана на технике, используемой обыкновенным голландским садовым гномом. Вот как садовый гном сортирует ряд цветочных горшков. По существу, он смотрит на два соседних цветочных горшка, если они находятся в правильном порядке, то он переходит на один горшок вперед, иначе он меняет их местами и возвращается на один горшок назад. Граничные условия: если позади нет ни одного горшка – он шагает вперед, а если нет следующего горшка, тогда он закончил.

Так описал основную идею алгоритма гномьей сортировки Дик Грун. Заменим гнома и горшки на более формальные объекты, например на указатель (номер текущего элемента) и элементы массива, и рассмотрим принцип работы алгоритма еще раз. Вначале указатель ставиться на 2-ый элемент массива (в C++ он имеет номер 1, а в Паскале номер 2). Затем происходит сравнение двух соседних элементов A[i] и A[i-1], т. е. сравниваются первый элемент (i-1) и второй (i). Если те стоят на своих позициях, то сдвигаем указатель на позицию i+1 и продолжаем сравнение с нового положения; иначе меняем элементы местами, и, поскольку в какой-то момент может оказаться, что элементы в левом подмассиве стоят не на своих местах, сдвигаем указатель на одну позицию влево, осуществляя следующее сравнение с новой позиции. Так алгоритм продолжает выполняться до тех пор, пока весь массив не будет упорядочен. Здесь следует выделить два важных момента. Во-первых, процесс упорядочивания заканчивается, тогда когда не выполняется условие i<n, где n – размер массива. Во-вторых, как было сказано, указатель перемещается как вперед по списку, так и назад, и в том случае если он окажется над первым элементом, его сразу же следует сместить на одну позицию вправо, т. к. в противном случае придется сравнивать два элемента, одного из которых не существует.

Перейдем собственно к коду. На своем сайте Дик Грун выложил следующий листинг:

 

1 2 3 4 5 6 7 8 void gnomesort(int n, int ar[]) { int i = 0; while (i < n) { if (i == 0 || ar[i-1] <= ar[i]) i++; else {int tmp = ar[i]; ar[i] = ar[i-1]; ar[--i] = tmp;} } }

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

Код программы на C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include "stdafx.h"#include <iostream> using namespace std; int n; void Gnome_sort(int i, int j, int *mas) { while (i<n) { if (mas[i-1]<=mas[i]) { i=j; j++; } else { int t=mas[i]; mas[i]=mas[i-1]; mas[i-1]=t; i--; if (i==0) { i=j; j++; } }} cout<<"Отсортированный массив: "; for (i=0; i<n; i++) //вывод массива cout<<mas[i]<<" "; } void main() { setlocale(LC_ALL,"Rus"); int m, k; cout<<"Размер массива > "; cin>>n; int *a=new int[n]; for (k=0; k<n; k++) //ввод массива { cout<<k+1<<" элемент > "; cin>>a[k]; } k=1; m=2; Gnome_sort(k, m, a); //вызов функции сортировки delete []a; system("pause>>void"); }

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

  Гномья сортировка Сортировка вставками
Худший случай O(n2) O(n2)
Лучший случай O(n) O(n)
Средний случай O(n2) O(n2)

 

Сортировка Шелла

В 1959 году американский ученый Дональд Шелл опубликовал алгоритм сортировки, который впоследствии получил его имя – «Сортировка Шелла». Этот алгоритм может рассматриваться и как обобщение пузырьковой сортировки, так и сортировки вставками.

Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз. Далее, на примере последовательности целых чисел, показан процесс сортировки массива методом Шелла. Для удобства и наглядности, элементы одной группы выделены одинаковым цветом.

Первое значение, соответствующее расстоянию d равно 10/2=5. На каждом шаге оно уменьшается вдвое. Элементы, входящие в одну группу, сравниваются и если значение какого-либо элемента, стоящего левее того с которым он сравнивается, оказывается больше (сортировка по возрастанию), тогда они меняются местами. Так, элементы путем внутригрупповых перестановок постепенно становятся на свои позиции, и на последнем шаге (d=1) сортировка сводится к проходу по одной группе, включающей в себя все N элементов массива. При этом число требуемых обменов оказывается совсем небольшим.

Код программы на C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include "stdafx.h"#include <iostream> using namespace std; int i, j, n, d, count; 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]) { count=A[j]; A[j]=A[j+d]; A[j+d]=count; j--; } } d=d/2; } for (i=0; i<n; i++) cout<<A[i]<<" "; //вывод массива } //главная функция void main() { setlocale(LC_ALL,"Rus"); cout<<"Размер массива > "; cin>>n; int *A= new int[n]; //объявление динамического массива for (i=0; i<n; i++) //ввод массива { cout<<i+1<<" элемент > "; cin>>A[i]; } cout<<"\nРезультирующий массив: "; Shell(A, n); delete [] A; //освобождение памяти system("pause>>void"); }

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

  Сортировка вставками Сортировка Шелла Быстрая сортировка
Худший случай O(n2) O(n2) O(n2)
Лучший случай O(n) O(n log n) O(n log n)
Средний случай O(n2) Зависит от расстояния между элементами O(n log n)

 



Дата добавления: 2017-05-02; просмотров: 2116;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.009 сек.