Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Рекурсивное доупорядочивание
|
|
Если в какой-то из получившихся в результате разбиения массива частей находиться больше одного элемента, то следует произвести рекурсивное упорядочивание этой части, то есть выполнить над ней операцию разбиения, описанную выше. Для проверки условия «количество элементов > 1», нужно действовать примерно по следующей схеме:
Имеется массив Mas [ L.. R ], где L и R – индексы крайних элементов этого массива. По окончанию разбиения, указатели first и last оказались примерно в середине последовательности, тем самым образуя два отрезка: левый от L до last и правый от first до R. Выполнить рекурсивное упорядочивание левой части нужно в том случае, если выполняется условие L < last. Для правой части условие аналогично: first < R.
Реализации алгоритма быстрой сортировки:
Код программы на 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 39 40 41 42 43 44 45 46 47 | #include " stdafx.h" #include < iostream> #include < ctime> using namespace std; const int n=7; int first, last; //функция сортировки void quicksort(int *mas, int first, int last) { int mid, count; int f=first, l=last; 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 (first< l) quicksort(mas, first, l); if (f< last) quicksort(mas, f, last); } //главная функция void main() { setlocale(LC_ALL, " Rus"); int *A=new int[n]; srand(time(NULL)); cout< < " Исходный массив: "; for (int i=0; i< n; i++) { A[i]=rand()%10; cout< < A[i]< < " "; } first=0; last=n-1; quicksort(A, first, last); cout< < endl< < " Результирующий массив: "; for (int i=0; i< n; i++) cout< < A[i]< < " "; delete []A; system(" pause> > void"); } |
Стоит отметить, что быстрая сортировка может оказаться малоэффективной на массивах, состоящих из небольшого числа элементов, поэтому при работе с ними разумнее отказаться от данного метода. В целом алгоритм неустойчив, а также использование рекурсии в неверно составленном коде может привести к переполнению стека. Но, несмотря на эти и некоторые другие минусы, быстрая сортировка все же является одним из самых эффективных и часто используемых методов.
Сортировка Шелла
В 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(n 2) | O(n 2) | O(n 2) |
| Лучший случай | O(n) | O(n log n) | O(n log n) |
| Средний случай | O(n 2) | Зависит от расстояния между элементами | O(n log n) |
|
|