Читайте также:
|
Алгоритм основан на разделениии сортируемого массива на части и перестановке элементов таким образом, чтобы элементы в левой части массива не превосходили элементов в правой. На каждом шаге выбирается 'средний' элемент массива, в результате ряда перестановок он занимает свое свое законное место, затем каждая из частей упорядочивается:
void qSort(int L, H; int @Buff) if H<=L+1 then return end int I=L; int J=H-1; int K=(L+H)/2; while TRUE do while I<K & Buff[I]<=Buff[K] do inc I; end while J>K & Buff[K]<=Buff[J] do dec J; end if I=J then exit end int Temp=Buff[I]; Buff[I]=Buff[J]; Buff[J]=Temp; select case I=K: K=J; case J=K: K=I; end end qSort(L, K,@Buff); qSort(K+1,H,@Buff); endЕсли 'средние' элементы находится не слишком далеко от своих законных мест, все хорошо - оценка времени выполнения ~N*Log(N) (~N+2*N/2+4*N/4+...+N*1), но можно так упорядочить элементы исходного массива, что 'быстрая' сортировка потребует ~N*N операций и, что еще хуже, N фреймов стека. Следующая функция заполняет массив самым неблагоприятным для qSort способом:
void Fill(int N; int @Buff) if N>0 then dec N; Fill(N,@Buff); int M=(N+1)/2; Buff[N]=Buff[M]; Buff[M]=N; end endВ более сложных реализациях алгоритма 'средний' элемент выбирается как средний из трех или случайным образом. Но как минимум, необходимо заменить один из рекурсивных вызовов циклом, это предотвратит разрушение стека:
void qSort(int L, H; int @Buff) while TRUE do if H<=L+1 then return end int I=L; int J=H-1; int K=(L+H)/2; while TRUE do while I<K & Buff[I]<=Buff[K] do inc I; end while J>K & Buff[K]<=Buff[J] do dec J; end if I=J then exit end int Temp=Buff[I]; Buff[I]=Buff[J]; Buff[J]=Temp; select case I=K: K=J; case J=K: K=I; end end if K-L<H-K then qSort(L, K,@Buff); L=K+1; else qSort(K+1,H,@Buff); H=K; end end endВ 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"); } |
Код программы на Pascal:
| 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 | program ShellSorting; uses crt; type massiv=array[1..100] of integer; var i, j, n, d, count: integer; A: massiv; procedure Shell(A: massiv; n: integer); {сортировка Шелла} begin d:=n; d:=d div 2; while (d>0) do begin for i:=1 to n-d do begin j:=i; while ((j>0) and (A[j]>A[j+d])) do begin count:=A[j]; A[j]:=A[j+d]; A[j+d]:=count; j:=j-1; end; end; d:=d div 2; end; writeln; for i:=1 to n do write(' ', A[i]); {вывод массива} end; {основной блок программы} begin write('Размер массива > '); read(n); for i:=1 to n do {ввод массива} begin write(i, ' элемент > '); readln(A[i]); end; write('Результирующий массив: '); Shell(A, n); end. |
Сортировка Шелла уступает в эффективности быстрой сортировки, но выигрывает у сортировки вставками. Сравнить скорость работы этих трех алгоритмов можно, воспользовавшись следующей таблицей.
| Сортировка вставками | Сортировка Шелла | Быстрая сортировка | |
| Худший случай | 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) |
21 октября 2013 в 11:50
Дата добавления: 2015-01-30; просмотров: 178 | Поможем написать вашу работу | Нарушение авторских прав |