Сортировка Шелла. Сортировка Шелла
 Скачать 29 Kb.
|
|
Сортировка Шелла Сортировка по методу Шелла также относится к обменным сортировкам, и даже принцип функционирования очень похож на "метод пузырька". В этом методе первоначально рассматриваются элементы отстоящие друг от друга на расстояние d=[n/2], где [ ] - операция взятия целой части, и n - количество элементов исходного массива. На следующих шагах d меняется по закону d=[d/2], при d=1 метод Шелла вырождается в метод стандартного обмена ("Метод Пузырка") Давайте рассмотрим пример: Дано множество {6,3,4,8,2,9} d=[n/2]=[6/2]=3 {6,3,4,8,2,9} - сравниваем 6 и 8 {6,2,4,8,3,9} - сравниваем 3 и 2, переставляем {6,3,4,8,2,9} - сравниваем 4 и 9 далее d=[d/2]=[3/2]=1 выродился в метод "Пузырька" В этом примере не очень видна эффективность этого метода, но представьте, что вы сортируете 1000 элементов. Этот метод обеспечивает более быстрое перебрасывание больших элементов вправо и меньших влево, чем метод "Пузырька" и этим обеспечивает большее быстродействие. #include #include int BubbleSort(int *array,int len) { /* Код сортировки из предыдущего шага */ }; int ShellSort(int *array,int len) { long d=len,i,j; int c; do { d=d/2; i=0; while ((j=i+d) { if (array[i]>array[j]) { c=array[i]; array[i]=array[j]; array[j]=c; }; i++; }; } while (d>1); BubbleSort(array,len); }; int main() { int k[10]={8,-5,1,7,3,-10,6,5,10,9}; printf("\n\n\n"); for (int i=0; i<10;i++) printf(" %d ",k[i]); printf("\n"); ShellSort(k,10); for (i=0; i<10;i++) printf(" %d ",k[i]); printf("\n"); return 0; }; Результат выполнения: 8 -5 1 7 3 -10 6 5 10 9 -10 -5 1 3 5 6 7 8 9 10 Для теста эффективности я создал счетчик циклов, и до вырождения в метод "Пузырька" было выполнено всего 3 прохода. Причем, что больше всего меня удивило, массив был вот в каком состоянии: -10 -5 1 3 5 6 7 8 9 10 А тут видно, что он уже отсортирован и метод "Пузырька" работал в холостую, но совершил всего один цикл, т.к. в нем выполнилось условие Айверсона. По-моему очевидно, что метод Шелла обладает большим быстродействием. |