Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Теоретичні відомості. Швидке сортування (англ. Quick Sort) — алгоритм сортування, добре відомий, як алгоритм, розроблений Чарльзом Хоаром






Швидке сортування (англ. Quick Sort) — алгоритм сортування, добре відомий, як алгоритм, розроблений Чарльзом Хоаром, який не потребує додаткової пам’яті і виконує у середньому операцій. Однак, у найгіршому випадку робить порівнянь. Оскільки алгоритм використовує дуже прості цикли і операції, він працює швидше за інші алгоритми, що мають таку ж асимптотичну оцінку складності. Наприклад, зазвичай більш ніж удвічі швидший порівняно з сортуванням злиттям.

Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв’язному списку.

У класичному варіанті, запропонованому Хоаром, з масиву обирався один елемент, і весь масив розбивався на дві частини по принципу: в першій частині — ті що не більші даного елементу, в другій частині — ті що не менші даного елемента. На сьогодні в стандартних бібліотеках використовують таку реалізацію алгоритму:

1 2 3 for to 4 do if 5 then 6 Поміняти 7 8 Поміняти 9 return 1 if return; 2 3 4

Сортува́ ння Ше́ лла — це алгоритм сортування, що є узагальненням сортування вставкою.

Алгоритм базується на двох тезах:

· Сортування вставкою ефективне для майже впорядкованих масивів.

· Сортування вставкою неефективне, тому що переміщує елемент тільки на одну позицію за раз.

Тому сортування Шелла виконує декілька впорядкувань вставкою, кожен раз порівнюючи і переставляючи елементи, що розташовані на різній відстані один від одного.

Сортування Шелла названо на честь автора — Дональда Шелла, який опублікував цей алгоритм у 1959 році. У деяких пізніших друкованих виданнях алгоритм називають сортуванням Шелла-Мацнера, за ім’ям Нортона Мацнера.

Ідея алгоритму. На початку обираються m елементів: , причому, .

Потім виконується m впорядкувань методом вставки, спочатку для елементів, що стоять через , потім для елементів через і т.д. до .

Ефективність досягається тим, що кожне наступне впорядкування вимагає меншої кількості перестановок, оскільки деякі елементи вже стали на свої місця.

Сам алгоритм не залежить від вибору m і d, тому будемо вважати, що вони задані.

1. for to 2. do for to 3. do 4. 5. while і 6. do 7. 8.

Оскільки то на останньому кроці виконується звичайне впорядкування вставкою всього масиву, а, отже, кінцевий масив буде впорядкованим.

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

· При виборі час роботи алгоритму, в найгіршому випадку, є .

· Якщо d — впорядкованний за спаданням набір чисел виду , то час роботи є .

· Якщо d — впорядкованний за спаданням набір чисел виду , то час роботи є .

Проілюструймо алгоритм на вхідному масиві A = (5, 16, 1, 32, 44, 3, 16, 7), d = (5, 3, 1).

1. Масив після впорядкування з кроком в 5: (3, 16, 1, 32, 44, 5, 16, 7) — зроблено 1 обмін.

2. Масив після впорядкування з кроком 3: (3, 7, 1, 16, 16, 5, 32, 44) — зроблено 3 обміна.

3. Масив після впорядкування з кроком 1: (1, 3, 5, 7, 16, 16, 32, 44) — зроблено 5 обмінів.

Отже, весь масив впорядковано за 8 операцій обміну.

Сортування злиттям — алгоритм сортування, в основі якого лежить принцип «Розділяй та володарюй».

В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, які вишикувалися за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він діє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової.

Тепер розглянемо сортування масиву A злиттям. На першому кроці елементи A[1], …, A[n] копіюються в допоміжний масив B[1], …, B[n]. Його елементи розглядаються парами B[1] і B[2], B[3] і B[4] тощо як упорядковані послідовності довжиною lp = 1 і зливаються в масив A. Тепер там є впорядковані ділянки довжиною 2. За непарного n останній елемент A[n] залишається без змін як послідовність довжиною 1. На наступному кроці після копіювання в масив B зливаються пари упорядкованих ділянок B[1]B[2] і B[3]B[4], B[5]B[6] і B[7]B[8] тощо. З’являються впорядковані ділянки довжиною 4. Нехай t=n mod 4 – довжина залишку масиву після останньої повної четвірки елементів. При t=1 або t=2 останні t елементів утворюють упорядковану ділянку після попереднього кроку. При t=3 зливаються упорядкована пара B[n-1]B[n-2] та ділянка B[n] у ділянку довжиною t. Кроки повторюються з подвоєнням довжин упорядкованих ділянок lp, поки lp < n.

Складність наведеного алгоритму O(nlogn).

Сортування злиттям можна задати рекурсивно: масив поділяється на дві приблизно рівні частини, які після сортування тим самим способом (рекурсія!) зливаються. Коли ж довжина частини масиву зменшується до 1, відбувається просто повернення з рекурсії.

Алгоритм злиттям є першим із ефективних алгоритмів сортування. У 1945 році його винайшов Джон фон Нейман.

 

Наведемо псевдокод алгоритму.

Процедура здійснює часткове впорядкування масиву , впорядковуючи його елементи з p-го по q-ий; здійснить впорядкування всього масиву).

 

Проілюструємо алгоритм сортування на такій послідовності:

42 – 5 – 30 – 36 – 25 – 10 – 37 – 49 – 0 – 0

На початку сортування відсортовані підпослідовності містять в собі по одному елементу.

Крок 1: 5 42 | 30 36 | 10 25 | 37 49 | 0 0

Крок 2: 5 30 36 42 | 10 25 37 49 | 0 0

Крок 3: 5 10 25 30 36 37 42 49 | 0 0

Крок 4: 0 0 5 10 25 30 36 37 42 49

 

Проведемо сортування наступної послідовності:

56 – 19 – 3 – 95 – 23 – 17 – 38 – 44 – 69 – 73 – 84

На початку сортування послідовність є розбиваються на відсортовані підпослідовності по одному елементу в кожній.

56 | 19 | 3 | 95 | 23 | 17 | 38 | 44 | 69 | 73 | 84

далі кожні дві підпослідовності зливаються в одну відсортовану підпослідовність:

19 56 | 3 95 | 17 23 | 38 44 | 69 73 | 84

на наступному кроці отримаємо наступний результат злиття:

3 19 56 95 | 17 23 38 44 | 69 73 84 |

потім:

3 17 19 23 38 44 56 95 | 69 73 84 |

на останньому кроці отримаємо відсортовану послідовність:

3 17 19 23 38 44 56 69 73 84 | 95

Послідовність була відсортована за 4 кроки.

 

Алгоритми сортування, які міняють порядок розташування однакових елементів, називаються нестабільними, а ті, що не міняють - стабільними.

Алгоритми Шелла та швидкого сортування є нестабільними, а алгоритм злиття – стабільним.


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.01 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал