Тема: Швидкі алгоритми сортування. Сортування Хоара




Скачати 86.81 Kb.
НазваТема: Швидкі алгоритми сортування. Сортування Хоара
Дата27.01.2014
Розмір86.81 Kb.
ТипДокументы
nauch.com.ua > Информатика > Документы

http://antibotan.com/ - Всеукраїнський студентський архів

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

модуль 1

Тема: Швидкі алгоритми сортування. Сортування Хоара. Динамічне сортування. (2 год)


Мета: Закріпити поняття складності алгоритма. Сформувати вміння застосовувати швидкі алгоритми сортування.

Література:


  1. Архангельский А.Я. Язык Pascal и основы программирования в Delphi

  2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.– 536 с.

  3. Культин Н.Б. Turbo Pascal в задачах и примерах

  4. М.С.Львов, О.В. Співаковський. Основи алгоритмізації та програмування.

  5. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0

  6. Меженный О.А. Turbo Pascal

  7. Немцова Т.И., Голова С.Ю., Абрамова И.В. Программирование на языке высокого уровня. программирование на языке Object Pascal

  8. Окулов С.М. Основы программирования.– М.: ЮНИМЕДИАСТАЙЛ, 2002.– 424 с.

  9. Павловская Т.А. Паскаль. Программирование на языке высокого уровня

  10. Пильщиков В.Н. Сборник упражнений по языку Паскаль. Москва, Наука, 1989 г., 160 с.
^

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


Удосконаливши метод сортування, заснований на обмінах, К. Хоар запропонував алгоритм QuickSort сортування масивів, який дає на практиці відмінні результати і дуже просто програмується. Автор назвав свій алгоритм швидким сортуванням.

Ідея К. Хоара полягає в наступному:

1. Оберемо деякий елемент x масива A випадковим чином;

2. Переглядаємо масив у прямому напрямку (i = 1, 2,...), шукаючи в ньому елемент A[i] не менший, ніж x;

3. Переглядаємо масив у зворотному напрямку (j = n, n-1,..), шукаючи в ньому елемент A[j] не більший, ніж x;

4. Міняємо місцями A[i] і A[j].

Пункти 2-4 повторюємо до тих пір, поки i < j.

В результаті такого зустрічного проходу початок масива A[1..i] і кінець масива A[j..n] виявляються розділеними “бар’єром” x: A[k]  x при k < i, A[k]  x при k > j , причому на розмежування ми витратимо не больше n/2 перестановок. Тепер залишилось зробити ті ж дії з початком і кінцем маси­ва, тобто застосувати їх рекурсивно! Таким чином, описана нами процедура Hoare залежить від параметрів k і m – початкового і кінцевого індексів відрізка масива, що обробляється.
Procedure Swap(i, j : Integer);

Var b : Real;

Begin

b := a[i]; a[i] := a[j]; a[j] := b

End;
Procedure Hoare(L, R : Integer);

Var left, right : Integer;

x : Integer;

Begin

If L < R then begin

x := A[(L + R) div 2]; {вибір бар’єра x}

left := L; right := R ;

Repeat {зустрічний проход}

While A[left] < x do Inc(left); {перегляд вперед}

While A[right] > x do Dec(right); {перегляд назад}

If left <= right then begin

Swap(left, right); {перестановка}

Inc(left); Dec(right);

end

until left > right;

Hoare(L, right); {сортуємо початок}

Hoare(left, R) {сортуємо кінець}

end

End;
Program QuickSort;

Const n = 100;

Var A : array[1..n] of Integer;

{ процедури Swap, Hoare, введення і виведення }

Begin

Inp; Hoare(1, n); Out

End.
Аналіз складності алгоритма в средньому, який використовує гіпотезу про рівну ймовірність всіх входів, показує, що C(n) = O(n log2 n), M(n) = O(n log2 n).

У найгіршому випадку, коли у якості бар’єрного обирається, наприклад, максимальний елемент підмасива, складність алгоритма квадратична.
Алгоритм пірамідального сортування HeapSort використовує представлення масива у вигляді дерева. Цей алгоритм не потребує допоміжних масивів, сортуючи “на місці”. Розглянемо спочатку метод представлення масива у вигляді дерева:

Нехай A[1 .. n] – деякий масив. Співставимо йому дерево, використовуючи наступні правила:




1.A[1] – корінь дерева ;

2.Якщо A[i] – вузол дерева і 2i  n, то A[2*i] – вузол  “лівий син” вузла A[i];

3.Якщо A[i] – вузол дерева і 2i + 1  n, то A[2*i+1] – вузол - “правий син” вузла A[i].
Правила 1 - 3 визначають у масиві структуру дерева, причому глибина дерева не перевищує [log2 n] + 1. Вони ж задають і спосіб руху по дереву від кореня до листів. Рух вверх задається правилом 4:
4.Якщо A[i] – вузол дерева і i > 1, то A[i mod 2] – вузол - “батько” вузла A[i].
П
риклад: Нехай A = [45 13 24 31 11 28 49 40 19 27] - масив. Відповідне йому дерево має вигляд:
Зверніть увагу на те, що всі рівні дерева, за виключенням останнього, повністю заповнені, останній рівень заповнений зліва і індексація елементів масива здійснюється зверху-вниз і зліва-направо. Тому дерево упорядкованого масива задовольняє наступним властивостям: A[i]  A[2*i], A[i]  A[2*i+1], A[2*i]  A[2*i+1].

Як це не дивно, алгоритм HeapSort спочатку будує дерево, яке задовольняє прямо протилежним співвідношенням

A[i]  A[2*i], A[i]  A[2*i+1],

а потім міняє місцями A[1] (найбільший елемент) і A[n].

Алгоритм HeapSort працює в два этапа:

I. Побудова сортуючого дерева;

II. Просівання елементів по сортуючому дереву.

Дерево, що представляє масив, називається сортуючим, якщо виконуються умови. Якщо для деякого i ця умова не виконується, будемо говорити, що має місце (сімейний) конфлікт у трикутнику i.

І на I-ому, і на II-ому етапах елементарна дія алгоритма полягає в розв’язанні сімейного конфлікта: якщо найбільший з синів бі­ль­ше, ніж батько, то переставляються батько и цей син (процедура ConSwap).

В результати перестановки може виникнути новий конфлікт у тому трикутнику, куди переставлений батько. Таким чином можна говорити про конфлікт (рода) у піддереві з коренем у вершині i. Конфлікт рода розв’язується послідовним розв’язуванням сімейних конфліктів проходом по дереву зверху-вниз. Конфлікт рода розв’язаний, якщо прохід закінчився (i > n div 2) або в результаті перестановки не виник новий сімейний конфлікт. (процедура Conflict)
Procedure ConSwap(i, j : Integer);

Var b : Real;

Begin

If a[i] < a[j] then begin

b := a[i]; a[i] := a[j]; a[j] := b

end

End;
Procedure Conflict(i, k : Integer);

Var j : Integer;

Begin

j := 2*i;

If j = k

then ConSwap(i, j)

else if j < k then begin

if a[j+1] > a[j] then j := j + 1;

ConSwap(i, j); Conflict(j, k)

end

End;
I етап – побудова сортуючого дерева – оформимо у вигляді рекурсивної процедури, використовуючи визначення:

Якщо ліве і праве піддерева T(2i) і T(2i+1) дерева T(i) сортуючі, то для пере­стройки T(i) необхідно розв’язати конфлікт рода в цьому дереві.
Procedure SortTree(i : Integer);

begin

If i <= n div 2 then begin

SortTree(2*i); SortTree(2*i+1); Conflict(i, n)

end

end;
На II-ому етапі – етапі просіювання – для k від n до 2 повторюються наступні дії:

1.Переставити A[1] і A[k];

2.Побудувати сортуюче дерево початкового відрізка масива A[1..k-1], усунувши конфлікт рода в корені A[1]. Зауважимо, що 2-а дія вимагає введення в процедуру Conflict параметра k.
Program HeapSort;

Const n = 100;

Var A : Array[1..n] of real;

k : Integer;

{процедури ConSwap, Conflict, SortTree, введення, виведення}

Begin

{ введення }

SortTree(1);

For k := n downto 2 do begin

ConSwap(k, 1); Conflict(1, k - 1)

end;

{ виведення }

End.

Нескладно підрахувати, що С(n) = O( n log2 n ), М(n) = O( n log2 n ).


^

Задачі для самостійного розв’язування


  1. Нехай дано масив a1, a2, ... , an. Необхідно переставити його елементи так, щоб спочатку йшла група елементів, більших того елемента, який у вхідному масиві розташовувався на першому місці, потім – сам цей елемент, потім – група елементів, менших або рівних йому. Кількість порівнянь і переміщень, кожна окремо, не повинна перевищувати n-1.

  2. Реалізувати ітеративну версію алгоритму HeapSort:

a) Замінити рекурсію у процедурі SortTree арифметичним циклом For...downto, який обробляє дерево по рівням, починаючи з нижнього;

б) Замінити рекурсію у процедурі Conflict ітераційним циклом, який керується змінною i. { i := 2i або i := 2i + 1 }.

  1. Реалізувати ітеративну версію алгоритму процедури HoareSeach, замінивши рекурсію ітераційним циклом.

  2. Реалізувати алгоритм “тернарного” пошуку елемента в упорядкованому масиві, розділяючи ділянку пошуку на 3 приблизно рівні частини. Оцінити складність алгоритму у термінах C(n). Порівняти ефектив­ність бінарного і тернарного пошуку.

  3. Відсортувати масив х за зростанням методом злиття (кількість дій не повинна перевищувати C*n*log(n).

Зауваження: Нехай k – додатне ціле число. Розіб’ємо масив x[1]..x[n] на відрізки довжини k. (Перший – x[1]..x[k], потім x[k+1]..x[2k] і т.і.) Останній відрізок буде неповним, якщо n не ділиться на k. Назвемо масив k-упорядкованим, якщо кожний з цих відрізків окремо упорядкований. Будь-який масив 1-упорядкований. Якщо масив k-упорядкований і n<=k, то він упорядкований. Алгоритм перетворення k-упорядкованого масиву в 2k-упорядкований:

k:=1;

{масив x є k-упорядкованим}

while k < n do begin

| .. перетворити k-упорядкований масив у 2k-упорядкований;

| k := 2 * k;

end;

2. Знайти кількість різних чисел серед елементів даного масиву. Число дій порядку n*log n.

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

6. Дано n точок на площині. Побудувати їх опуклу оболонку – мінімальну опуклу фігуру, яка містить ці точки. Кількість операцій не більше n*log n.

Вказівка. Упорядкуємо точки. Потім, розглядаючи точки по черзі, будемо будувати опуклу оболонку вже розглянутих точок.

7. Маємо масив цілих чисел a[1]..a[n], причому всі числа невід’ємні і не перевищують m. Відсортувати цей масив; число дій порядку m+n.

Вказівка. Для кожного числа від 0 до m підраховуємо, скільки разів воно зустрічається у масиві. Після цього вхідний масив можна стерти і заповнити знову у порядку зростання, використовуючи відомості про кратність кожного числа. Відзначимо, що цей алгоритм не переставляє числа у масиві, як більшість інших, а "записує їх туди знову".

8. У масиві a[1]..a[n] цілих чисел переставити елементи так, щоб парні числа йшли перед непарними (не змінюючи взаємний порядок у кожній з груп).

Вказівка. Спочатку спишемо (у допоміжний масив) всі парні, а потім – всі непарні.

9. Маємо масив з n чисел від 0 до (2 в степені k) – 1, кожне з яких ми будемо розглядати як k-бітове слово з нулів і одиниць. Використовуючи перевірки "i-ий біт дорівнює 0" і "i-ий біт дорівнює 1" замість порівнянь, відсортувати всі числа за час порядка n*k.

Вказівка. Відсортуємо числа за останнім бітом, потім за передостаннім і таке інше. В результаті вони будуть відсортовані.

10. Маємо квадратну таблицю a[1..n, 1..n]. Відомо, що для деякого i рядок з номером i заповнений одними нулями, а стовбець з номером i – одними одиницями (за виключенням їх перетину на діагоналі, де стоїть невідомо що). Знайти таке i (воно єдине). Кількість дій не перевищує C*n. (Зауважимо, що це суттєво менше кількості елементів у таблиці).

Вказівка. Розгляньте a[i][j] як результат "порівняння" i з j та згадайте, що самий важкий з n каменів може бути знайдений за n порівнянь.

11.Нехай дано масив a1, a2, ... , an. Необхідно переставити його елементи так, щоб спочатку йшла група елементів, більших того елемента, який у вхідному масиві розташовувався на першому місці, потім – сам цей елемент, потім – група елементів, менших або рівних йому. Кількість порівнянь і переміщень, кожна окремо, не повинна перевищувати n-1.

12.Реалиізувати ітеративну версію алгоритма HeapSort:

a) Замінити рекурсію у процедурі SortTree арифметичним циклом For...downto, який обробляє дерево по рівням, починаючи з нижнього;

б) Замінити рекурсію у процедурі Conflict ітераційним циклом, який керується змінною i. { i := 2i або i := 2i + 1 }.

13.Реалізувати ітеративну версію алгоритма процедури HoareSeach, замінивши рекурсію ітераційним циклом.

14.Реалізувати алгоритм “тернарного” пошуку елемента в упорядкованому масиве, розділяючи ділянку пошуку на 3 приблизно рівні частини. Оцінити складність алгоритма у термінах C(n). Порівняти ефектив­ність бінарного і тернарного пошуку.

15.Відсортувати масив х за зростанням методом злиття (кількість дій не повинна перевищувати C*n*log(n).

Зауваження: Нехай k – додатнє ціле число. Розіб’ємо масив x[1]..x[n] на відрізки довжини k. (Перший – x[1]..x[k], потім x[k+1]..x[2k] і т.і.) Останній відрізок буде неповним, якщо n не ділиться на k. Назвемо масив k-упорядкованим, якщо кожний з цих відрізків окремо упорядкований. Будьякий масив 1-упорядкований. Якщо масив k-упорядкований і n<=k, то він упорядкований. Алгоритм перетворення k-упорядкованого масива в 2k-упорядкований:

k:=1;

{масив x є k-упорядкованим}

while k < n do begin

| .. перетворити k-упорядкований масив у 2k-упорядкований;

| k := 2 * k;

end;



Схожі:

Тема: Швидкі алгоритми сортування. Сортування Хоара iconТема уроку: Сортування І фільтрація даних у таблицях. Мета
Мета: Сформувати поняття сортування, фільтрація, автофільтр; пояснити правила впорядкування І пошуку даних; сформувати вміння створювати...
Тема: Швидкі алгоритми сортування. Сортування Хоара iconОсновні алгоритми сортування масивів
На і-му кроці значення і-го елемента масиву тимчасово запам'ятовується в змінній
Тема: Швидкі алгоритми сортування. Сортування Хоара iconТема: Алгоритми впорядкування табличних величин. Впорядкування обміном
Мета: Познайомити учнів з принципами впорядкування табличних величин методом обміном. Засвоїти відомості з основ програмування а...
Тема: Швидкі алгоритми сортування. Сортування Хоара iconЗнайомство з сортуванням файлів
Наприклад, у великому місті може бути кілька мільйонів абонентів телефонної мережі. Звичайно, для швидкого пошуку дані про абонентів...
Тема: Швидкі алгоритми сортування. Сортування Хоара iconТема: Реалізація абстрактного типу даних «Сортування масивів»
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.– 536 с
Тема: Швидкі алгоритми сортування. Сортування Хоара iconДискретне перетворення Фур’є
Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень І порівняти їх з алгоритмами безпосереднього обчислення...
Тема: Швидкі алгоритми сортування. Сортування Хоара icon1. 1Введення даних
Як І в програмі Microsoft Word в програмі Excel можна створювати звичні текстові документи, бланки, прайс-листи, проводити сортування,...
Тема: Швидкі алгоритми сортування. Сортування Хоара iconУрок 20 Тема: Алгоритми
Розширити й поглибити поняття “алгоритм”. Сформувати поняття “виконавець алгоритму”. Учити складати алгоритми
Тема: Швидкі алгоритми сортування. Сортування Хоара icon“Створення та налагодження звітів”
Призначення І порядок створення звітів. Розділи бланка звітів. Елементи управління. Форматування елементів управління. Сортування...
Тема: Швидкі алгоритми сортування. Сортування Хоара iconЗакон України «Про стандартизацію»
Як ручний метод вимірювання застосовується метод серединного перерізу (метод Губера). Похибка вимірів між двома зазначеними методами...
Додайте кнопку на своєму сайті:
Школьные материалы


При копіюванні матеріалу обов'язкове зазначення активного посилання © 2013
звернутися до адміністрації
nauch.com.ua
Головна сторінка