Метод Шелла

0

Підготували студенти групи РПЗ-3: Костюк Ярослав та Крамаров Юрій

 

У 1959 році американський вчений Дональд Шелл опублікував алгоритм сортування, який згодом отримав його ім’я – «Сортування Шелла». Цей алгоритм може розглядатися і як узагальнення бульбашкового сортування, так і сортування вставками.


      Ідея методу полягає в порівняння розділених на групи елементів послідовності, що знаходяться один від одного на деякій відстані. Спочатку це відстань дорівнює d або N / 2, де N – загальне число елементів. На першому кроці кожна група включає в себе два елементи розташованих один від одного на відстані N / 2; вони порівнюються між собою, і, в разі необхідності, міняються місцями. На наступних кроках також відбуваються перевірка і обмін, але відстань d скорочується на d / 2, і кількість груп, відповідно, зменшується. Поступово відстань між елементами зменшується, і при d = 1 прохід по масиву відбувається в останній раз.


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

Демонстрація сортування Шелла: 

Shell_sorting_algorithm_color_bars.svg

Відео: Метод Шелла

 Приклад коду на мові С++

#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");
}

Share.

Comments:

Leave A Reply

'