4. Сортування Шелла
Перелік алгоритмів, що розглядаються
- сортування методом вставки;
- сортування методом Шелла.
Короткі теоретичні відомості
Питання для повторення
- Заповнення масиву згідно з рекурентною формулою.
Постановка задачі
Задано масив записів, одне поле яких виконує роль ключа. Необхідно знайти таку перестановку записів, після якої ключі розташувалися б у порядку неспадання.
Опис алгоритмів
Розглядається упорядкування масива a цілих чисел, занумерованих від 0 до N-1.
1.Сортування методом вставки
Ідея
Для кожного елемента з індексом i (i = 2, 3, ..., n-1) знайти його місце серед попередніх
i-1 елементів, які уже впорядковані. При пошуку позиції доцільно порівнювати ai з елементами ai - 1, ai - 2, ..., поки не з'явиться менше число або не буде досягнуто початок масиву, при цьому більші елементи зсуваються вправо, "звільняючи" місце для ai.
Псевдокод
для і від 1 до N-1
{
x = a[i]; j=i-1
поки j>=0 і x < a[j]
{
a[j+1] = a[j]; j = j-1
}
a[j+1] = x
}
{
x = a[i]; j=i-1
поки j>=0 і x < a[j]
{
a[j+1] = a[j]; j = j-1
}
a[j+1] = x
}
2. Сортування методом Шелла
Ідея
Розбити масив на групи елементів, що знаходяться на певній відстані один від одного, і здійснити незалежне сортування цих груп (як правило, методом вставки). На кожній ітерації крок між елементами групи зменшується і на останній ітерації він дорівнює одиниці. Складність сортування залежить від способу вибору кроку.Псевдокод
h = ПочатковийКрок;
поки h>0
{
для i від h до n-1
{
x = a[i]; j = i - h;
поки j>=0 і x < a[j]
{
a[j+h]=a[j]; j = j - h
}
a[j+h] = x
}
h=НовийКрок(h)
}
поки h>0
{
для i від h до n-1
{
x = a[i]; j = i - h;
поки j>=0 і x < a[j]
{
a[j+h]=a[j]; j = j - h
}
a[j+h] = x
}
h=НовийКрок(h)
}
Завдання для виконання
Постановка задачі
Скласти програми, що реалізують різні алгоритми сортування масиву, і зберегти їх у власній папці. Програми повинні забезпечувати:- автоматичну генерацію масиву цілих чисел та виведення його на екран;
- сортування масиву за певним алгоритмом;
- підрахунок кількості порівнянь і зміни значень елементів масиву в процесі впорядкування.
Технічні умови
- кількість елементів у масиві не перевищує 100;
- елементи масиву є невід'ємними цілими числами, що не перевищують 50.
Хід роботи
- Скласти програму Insertion.cpp, що забезпечує сортування масиву методом вставки.
- Змінити програму, забезпечивши реалізацію метода Шелла з вибором кроку за правилом НовийКрок=Крок / 2 (ПочатковийКрок=N/2). Зберегти під назвою ShellSort.cpp.
- Скласти програму для заповнення масиву h елементами однієї з наведених нижче послідовностей за вказівкою викладача:
- 1, 3, 7, 15, 31, ...; hk+1=2hk+1;
- 1, 4, 13, 40, 121, ...;hk+1=3hk+1.
Заповнення масиву припинити, коли черговий елемент стане більше заданого числа N.
- Змінити програму сортування масиву методом Шелла, задавши обчислення кроку згідно з послідовністю, сформованою у масиві h. Зберегти під назвою ShellSort2.cpp.
- Скласти таблицю виконання алгоритму сортування масиву 6 чисел методом Шелла з кроком, що обчислюється за вказаною викладачем формулою.
Запитання для самоконтролю
- Поясніть алгоритм методу вставки сортування масиву.
- У чому полягає сутність методу Шелла сортування масиву?
- За рахунок чого досягається покращення часової складності сортування в методі Шелла?
- Від чого залежить часова складність сортування масиву методом Шелла?
- Які послідовності можуть використовуватися для обчислення кроку між елементами групи в методі Шелла?