Перелік рекомендованих джерел. 1. Brian W. KernighanandDennis M

1. Brian W. KernighanandDennis M. Ritchie «The C ProgrammingLanguage» (SecondEdition). — 1988. [ISBN 0–13–110362–8]

2. Donald E. Knuth «TheArtofComputerProgramming»: «Volume 3: SortingandSearching» (SecondEdition). — 1998. [ISBN 0–201–89685–0]

Лабораторна робота № 3

Лабораторна робота № 3

Тема роботи: Метод сортування Шелла.

Мета роботи: Вивчити алгоритм сортування Шелла. Здійснити програмну реалізацію алгоритму сортування Шелла. Дослідити швидкодію алгоритму сортування Шелла.

Короткі теоретичні відомості

Сортування Шелла (англійською «ShellSort») — це алгоритм сортування, що є узагальненням сортування включенням.

Алгоритм базується на двох тезах:

· Сортування включенням ефективне для майже впорядкованих масивів.

· Сортування включенням неефективне, тому що переміщує елемент тільки на одну позицію за раз.

Тому сортування Шелла виконує декілька впорядкувань включенням, кожен раз порівнюючи і переставляючи елементи, що знаходяться на різній відстані один від одного.

Сортування Шелла не є стабільним.

Сортування Шелла названо начесть автора — Дональда Шелла, який опублікував цей алгоритм у 1959 році. В деяких пізніших друкованих виданнях алгоритм називають сортуванням Шелла-Мацнера, за ім’ям НортонаМацнера. Але сам Мацнер стверджував: «Мені не довелось нічого робити з цим алгоритмом, і моє ім’я не має пов’язуватись з ним».

На початку обираються m елементів: d ₁, d ₂, …, d_m, причому d ₁ > d ₂ > … > d_m = 1.

Потім виконується m впорядкувань методом включення, спочатку для елементів, що стоять через d ₁, потім для елементів через d ₂і так далі до d_m = 1.

Ефективність досягається тим, що кожне наступне впорядкування вимагає меншої кількості перестановок, оскільки деякі елементи вже стали на свої місця.

Оскільки d_m = 1, то на останньому кроці виконується звичайне впорядкування включенням всього масиву, а отже кінцевий масивгарантовано буде впорядкованим.

Час роботи залежить від вибору значень елементів масиву d. Існує декілька підходів вибору цих значень:

· При виборі,,, …, d_m = 1 час роботи алгоритму, в найгіршому випадку, становить O (N ²).

· Якщо d — впорядкованний за спаданням набір чисел виду ½(3 ^j – 1), j Î ℕ, d_i < N, то час роботи є O (N ^1.5).

· Якщо d — впорядкованний за спаданням набір чисел виду 2 ⁱ 3 ^j, i, j Î ℕ, d_k < N, то час роботи є O (N ∙log² N).