Метод Шелла.

Цей метод запропонував Donald Lewis Shell в 1959 p. Спочатку треба усунути масовий безлад в масиві, порівнюючи елементи, які далеко стоять один від одного. Далі інтервал між елементами, які порівнюються, поступово зменшується до одиниці. На останніх стадіях сортування зводиться до перестановки сусідніх елементів.

Весь масив розбивається на частини. Візьмемо деяке число t і розглянемо тільки ті елементи початкового набору, індекс яких буде кратний t: i=t, 2t,3t, ....

Розглянемо наступний набір даних:

-6,5,0,13,-9,4,8,-15,9,9,3,1

Порівнювати будемо за таким набором t=9, 5,3,2, 1.

Таблиця 4.1. Таблиця сортування за методом Шелла

і
t=9	-6			-9	-15
	-6			-9	-15
	-6			-9	-15
t=5	-6			-9	-15
	-6			-9	-15
	-6			-9	-15
	-6		-15	-9
	-6		-15	-9
	-6		-15	-9
	-6		-15	-9
t=3	-6		-15	-9
	-6		-15	-9
	-6	-9	-15
	-6	-9	-15
t=2	-6	-9	-15
	-15	-9	-6
t=l	-15	-9	-6
	-15 '	-9	-6

Єдиною характеристикою сортування Шелла є приріст - відстань між елементами, що впорядковують, в залежності від проходження. В кінці приріст завжди дорівнює одиниці - метод завершується звичайним сортуванням вставками, але саме послідовність приростів визначає ріст ефективності.

Одним з найкращим є послідовність, яка була представлена Р.Седжвіком. Його послідовшсть має вид

inc[S] =

9*2^s -9*2+1 якщо s парне

8*2^s-6*2+1 якщо s непарне

При використанні такого приросту середня кількість операцій O(n⁷^/⁶ ), найгіршому випадку - порядку O(n^4/3).

Приведемо один з варіантів програм реалізації метода Шелла.

int increment (long inc[], long size)

{

intpl,p2,p3,s;

_Pl=p2=p3=l;

s=-l;

{ if (++s%2)

inc[s]=8*pl-6*p2 + l;

else

inc[s]=9*pl-9*p3+l;

p2*=2;

p3*=2;

pl*=2;

} while (3*inc[s]<size);

return s>0? -s: 0;

}

template <class T>

void shellSort(T a[], long size){

long inc, i,j, seg[40];

int s;

// обчислення послідовності прирісту

s= increment(seg, size);

while (s>=0)

{//сортування включенням з інкрементами іпс[]

inc=seg[s--];

for (i=inc; i<size; i++)

{Ttemp=a[i];

for (j=i-inc; (j>=0)&&(a[j]>temp); j-=inc)

a[j+inc] = a[j];

a[j+inc]=temp;

}

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Сортування - це процес, який дозволяє впорядкувати множину подібних даних у порядку зростання або убування.	\|	Сортування злиттям.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.