Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи сортування. Шелла.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2007
Тип роботи:
Методичні вказівки
Предмет:
Алгоритми і структури даних
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти України
Національний університет "Львівська політехніка"
М Е Т О Д И Ч Н А В К А З І В К А
До лабораторної роботи № 5
На тему: “ Методи сортування. Шелла.”
з дисципліни
" Алгоритми і структури даних"
Для базового напрямку 6.0804 "Комп’ютерні науки"
ЗАТВЕРДЖЕНО
на засіданні кафедри
програмного забезпечення
протокол № від 2007 р.
Львів – 2007
Методичні вказівки до лабораторних робіти з дисципліни " Алгоритми і структури даних" Для базового напрямку 6.0804 "Комп’ютерні науки"
Укладач: Коротєєва Т. О.
Вовчак І. Г.
Відповідальний за випуск:
Рецензенти:
Тема роботи: Ознайомлення із методами сортування. Зокрема із методом Шелла.
Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із методом сортування Шелла. Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема по методу Шелла.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Сортування Шелла є досить цікавою модифікацією алгоритму сортування простими вставками.
Розглянемо наступний алгоритм сортування масиву а[0].. а[15].
INCLUDEPICTURE "http://algolist.manual.ru/sort/gif/11.gif" \* MERGEFORMATINET
1. Спочатку сортуємо простими вставками кожні 8 груп з 2-х елементів.
INCLUDEPICTURE "http://algolist.manual.ru/sort/gif/12.gif" \* MERGEFORMATINET
2. Потім сортуємо кожну з чотирьох груп по 4 елементи.
У нульовій групі будуть елементи 4, 12, 13, 18, в першій - 3, 5, 8, 9.
3. Далі сортуємо 2 групи по 8 елементів.
INCLUDEPICTURE "http://algolist.manual.ru/sort/gif/14.gif" \* MERGEFORMATINET
4. В кінці сортуємо вставками усі 16 елементів.
INCLUDEPICTURE "http://algolist.manual.ru/sort/gif/15.gif" \* MERGEFORMATINET
Очевидно, лише останнє сортування необхідне, щоб розташувати всі елементи по своїх місцях. Так навіщо потрібні останні ?
Hасправді вони просувають елементи максимально близько до відповідних позицій, так що в останній стадії число переміщень буде дуже маленьке. Послідовність і так майже відсортована.
Єдиною характеристикою сортування Шелла є приріст - відстань між сортованими елементами, залежно від проходу. В кінці приріст завжди рівний одиниці – мет3од завершується звичайним сортуванням вставками, але саме послідовність приростів визначає зростання ефективності.
Використаний в прикладі набір: 8, 4, 2, 1 - непоганий вибір, особливо, коли кількість елементів - ступінь двійки. Проте набагато кращий варіант запропонував Р.Седжвік. Його послідовність має вигляд
При використанні таких приростів середня кількість операцій: O(n7/6), у гіршому разі - порядку O(n4/3).
Звернемо увагу на те, що послідовність обчислюється в порядку, протилежному використовуваному: inc[0]= 1, inc[1]= 5 ... Формула дає спочатку менші числа, потім все більші і більші, тоді як відстань між сортованими елементами, навпаки, повинна зменшуватися. Тому масив приростів inc обчислюється перед запуском власне сортування до максимальної відстані між елементами, яка буде першим кроком в сортуванні Шелла. Потім його значення використовуються в зворотному порядку.
При використанні формули Седжвіка слід зупинитися на значенні inc[s-1], якщо 3*inc[s]> size.
int increment(long inc[], long size){
int p1, p2, p3, s;
p1 = p2 = p3 = 1;
s = -1;
do {
if (++s % 2) {
inc[s]= 8*p1 - 6*p2 + 1;
} else {
inc[s]= 9*p1 - 9*p3 + 1;
p2 *= 2;
p3 *= 2;
}
p1 *= 2;
} while(3*inc[s]< size);
return s > 0 ? --s : 0;
}
template<class T>
void shellSort(T a[], long size){
long inc, i, j, seq[40];
int s;
// обчислення послідовності приростів
s = increment(seq, size);
while (s >= 0) {
// сортування вставками з інкрементами inc[]
inc = seq[s--];
for (i = inc; i < size; i++) {
T temp = а[i];
for (j = i-inc; (j >= 0) && (а[j]> temp); j -= inc)
а[j+inc]= а[j];
а[j+inc]= temp;
}
}
}
Часто замість обчислення послідовності під час кожного запуску процедури, її значення розраховують заздалегідь і записують в таблицю, якою користуються, вибираючи початковий приріст за тим же правилом: починаємо з inc[s-1], якщо 3*inc[s]> size.
2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ
При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати алгоритм Шелла.
Використовувати мову програмування C/C++.
Лабораторна робота вважається зданою при наявності програмного продукту звіту і проведеного відповідного захисту виконаної роботи.
3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ
Отримати індивідуальне завдання у викладача;
Уточнити завдання(можливі різні трактування завдання);
Написати програмну реалізацію виконання індивідуального завдання із використанням вивченого методу(алгоритму) на даній лабораторній роботі;
Протестувати на наявність логічних помилок програми;
Оформити звіт відповідно до стандарту;
Захистити виконану роботу.
4. КОНТРОЛЬНІ ПИТАННЯ
Які ви знаєте методи сортування?
Який метод сортування був розглянений на даній лабораторній роботі?
Від чого прямо – залежним являється швидкість сортування?
Опишіть характеристики даного методу.
Порівняєте даний метод із іншими методами сортування вам відомими.
Наскільки являється ефективним даний метод сортування?
Чи використовують даний метод на практиці, і наскільки часто?
Чи можлива оптимізації даного методу? Якщо так, то яка? Якщо ні, то по яких причинах?
Чим оригінальним виділяється даний метод від інших?
5. ІНДИВІДУАЛЬНЕ ЗАВДАНЯ
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора