Лекція 4 метод Шелла

МЕТОДИ СОРТУВАННЯ

(продовження)

Сортування включенням

При сортуванні включенням до відсортованої множини R кожний раз приєднується один елемент, а саме: із невідсортованої вхідної множини М вибирається довільний елемент і розміщується у вихідну множину R.

Алгоритм V.

Нехай задано множину елементів М, | M|=n.

V1. k =1; повторювати кроки V2, V3, доки k<n.

V2. Вибір довільного елемента x вхідної множини М: x=M(k).

V3. Розміщення x у вихідній множині R так, щоб вона залишалась відсортованою.

V4. Кінець. Вихід.

Вихідну множину R при кожному включенні можна відсортовувати відомим методом сортування, наприклад, методом простої вибірки. Майже всі методи сортування включенням у найгіршому випадку вимагають порядку n² порівнянь, тому їх застосування пов‘язане з деяким ризиком. Є багато варіантів цього методу сортування.

Розглянемо метод Шелла. Його суть полягає в тому, що на кожному кроці групуються та сортуються елементи, що стоять один від одного на певній відстані h. Потім ця відстань зменшується на крок рівний степені двійки. На останньому кроці іде звичайне одинарне сортування. Перша відстань вибирається відносно кількості елементів в масиві поділена на 2.

Приклад:

44 55 12 42 94 18 06 67 n=8, h=n/2=4

44 18 06 42 94 55 12 67 h=h/2=4/2=2

06 18 12 42 44 55 94 67 h=h/2=2/2=11

06 12 18 42 44 55 67 94 стоп.

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

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

· · Якщо h - впорядкований за спаданням набір чисел виду (3^j – 1)/2, j Î N, h _i < N, то час роботи є O (N ^1.5).

· · Якщо h - впорядкований за спаданням набір чисел виду 2 ⁱ 3 ^j, i, j Î N,

h _k < N, то час роботи є O (N ∙log² N).