Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи сортування. Швидкий метод сортування.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2007
Тип роботи:
Методичні вказівки
Предмет:
Алгоритми і структури даних
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти України
Національний університет "Львівська політехніка"
М Е Т О Д И Ч Н А В К А З І В К А
До лабораторної роботи № 3
На тему: “ Методи сортування. Швидкий метод сортування.”
з дисципліни
" Алгоритми і структури даних"
Для базового напрямку 6.0804 "Комп’ютерні науки"
ЗАТВЕРДЖЕНО
на засіданні кафедри
програмного забезпечення
протокол № від 2007 р.
Львів – 2007
Методичні вказівки до лабораторних робіти з дисципліни " Алгоритми і структури даних" Для базового напрямку 6.0804 "Комп’ютерні науки"
Укладач: Коротєєва Т. О.
Вовчак І. Г.
Відповідальний за випуск:
Рецензенти:
Тема роботи: Ознайомлення із методами сортування. Зокрема із методом швидкого сортування.
Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із швидким методом сортування. Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема по швидкому методу.
ТЕОРЕТИЧНІ ВІДОМОСТІ
"Швидке сортування", хоч і було розроблено більше 40 років тому, є найбільше вживаним і одним з найефективніших алгоритмів сортування.
Метод заснований на підході "разділяй і керуй". Загальна схема така:
з масиву вибирається деякий контрольний елемент а,
запускається процедура розділення масиву, яка переміщає всі ключі, менші, або рівні а, ліворуч від нього, а всі ключі, більші, або рівні а[i] – в право
тепер масив складається з двох підмножин, причому ліве менше, або рівно правого
для обох підмасивів: якщо в підмасиві більше двох елементів, рекурсивно запускаємо для нього ту ж процедуру.
В кінці вийде повністю відсортована послідовність.
Розділення масиву
На вході масив а[0]...a[N] і контрольного елементу p, по якому проводитиметься розділення.
Введемо два індекса: i і j. На початку алгоритму вони вказують, відповідно, на лівий і правий кінець послідовності.
Переміщати покажчик i з кроком в 1 елемент у напрямку до кінця масиву, поки не буде знайдений елемент а[i] >= р. Потім аналогічним чином почнемо переміщати покажчик j від кінця масиву до початку, поки не буде знайдений а[j] <= р.
Якщо i <= j, міняємо а[i] і а[j] місцями і продовжуємо переміщати i та j по тих же правилах.
Повторюємо крок 3, поки i <= j.
Розглянемо роботу процедури для масиву а[0]...a[6] і контрольного елементу p = а[3].
Тепер масив розділений на дві частини: всі елементи з ліва менше або рівні p, всі елементи з права - більше, або рівні р. Розділення закінчене.
Реалізація на С++.
template<class T>
void quickSortR(T* а, long N){
// На вході - масив a[], а[N] - його останній елемент.
long i = 0, j = N; // поставити покажчики на початкові місця
T temp, p;
p = а[ N>>1 ]; // центральний елемент
// процедура розділення
do {
while ( а[i]< p ) i++;
while ( а[j]> p ) j--;
if (i <= j) {
temp = а[i]; а[i]= а[j]; а[j]= temp;
i++; j--;
}
} while ( i<=j );
// рекурсивні виклики, якщо є, що сортувати
if ( j > 0 ) quickSortR(а, j);
if ( N > i ) quickSortR(a+i, N-i);
}
Кожне розділення вимагає, очевидно, Theta(n) операцій. Кількість кроків ділення(глибина рекурсії) складає приблизно log n, якщо масив ділиться на більш-менш рівні частини. Таким чином, загальна швидкодія: O(n log n), що і має місце на практиці.
Проте, можливий випадок таких вхідних даних, на яких алгоритм працюватиме за O(n2) операцій. Таке відбувається, якщо кожного разу як центральний елемент вибирається максимум або мінімум вхідної послідовності. Якщо дані взяті випадково, вірогідність цього рівна 2/n. І ця вірогідність повинна реалізовуватися на кожному кроці.
Модифікація коду і методу
За рекурсії та інших "накладних витрат" Quicksort може виявитися не такою вже швидкою для коротких масивів. Тому, якщо в масиві менше MINSIZE елементів (константа залежить від реалізації, зазвичай рівна від 3 до 40), викликається сортування вставками. Збільшення швидкості може складати до 15%.
Для впровадження методу в життя можна модифікувати функцію quickSortR, замінивши останні 2 рядки на
if ( j > MINSIZE ) quickSortR(а, j);
if ( N > i + MINSIZE ) quickSortR(a+i, N-i);
Таким чином, масиви з MINSIZE елементів і менше досортовуватися не будуть, і в кінці роботи quickSortR() масив розділиться на послідовні частини з <=MINSIZE елементів, відсортовані один щодо одного. Близькі елементи мають близькі позиції, тому, аналогічно сортуванню Шелла, викликається insertSort(), яка доводить процес до кінця.
template<class T>
void qsortR(T *a, long size){
quickSortR(а, size-1);
insertSort(а, size); // insertSortGuarded швидше, але потрібна функція setmax()
}
У разі явної рекурсії, як в програмі вище, в стеку зберігаються не тільки межі підмасивів, але і ряд абсолютно непотрібних параметрів, таких як локальні змінні. Якщо емулювати стек програмно, його розмір можна зменшити у декілька разів.
Чим на рівніші частини ділитиметься масив - тим краще. Тому як опорного доцільно брати середній з трьох, а якщо масив достатньо великий - те з дев'яти довільних елементів.
2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ
При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати алгоритм швидкого сортування.
Використовувати мову програмування C/C++.
Лабораторна робота вважається зданою при наявності програмного продукту звіту і проведеного відповідного захисту виконаної роботи.
3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ
Отримати індивідуальне завдання у викладача;
Уточнити завдання(можливі різні трактування завдання);
Написати програмну реалізацію виконання індивідуального завдання із використанням вивченого методу(алгоритму) на даній лабораторній роботі;
Протестувати на наявність логічних помилок програми;
Оформити звіт відповідно до стандарту;
Захистити виконану роботу.
4. КОНТРОЛЬНІ ПИТАННЯ
Які ви знаєте методи сортування?
Який метод сортування був розглянений на даній лабораторній роботі?
Від чого прямо – залежним являється швидкість сортування?
Опишіть характеристики даного методу.
Порівняєте даний метод із іншими методами сортування вам відомими.
Наскільки являється ефективним даний метод сортування?
Чи використовують даний метод на практиці, і наскільки часто?
Чи можлива оптимізації даного методу? Якщо так, то яка? Якщо ні, то по яких причинах?
Чим оригінальним виділяється даний метод від інших?
5. ІНДИВІДУАЛЬНЕ ЗАВДАНЯ
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора