45)Загальні відомості про сортування. Сортування методом обміну.

Основними операціями, що виконуються над таблицями, є впорядкування (сортування) записів і пошук в таблиці запису по заданій умові( по ключу ). Сортування є операцією розстановки записів таблиці в певному порядку відповідно до деякого критерію впорядкування. Сортування здійснюється відповідно до значення ключів всіх записів (напр., впорядкування прізвищ за абеткою або чисел за збільшенням ). Існує достатньо багато методів сортування, що принципово відрізняються один від одного. Якщо таблиця цілком поміщається в оперативній пам'яті ЕОМ, то її впорядкування називають внутрішнім. Якщо для зберігання упорядковуваних даних використовуються зовнішній пристрій, що запам'ятовує, то таке впорядкування називають зовнішнім. Критеріями оцінки методів сортування є :

З - кількість операцій порівняння пар ключів,

Р - число перестановок елементів,

s - резерв пам'яті.

Середня кількість операцій порівняння залежить від методу сортування і при раціональному виборі методу досягає деякого мінімуму, залежного від n, - розміру таблиці ( розмір таблиці - кількість записів, що містяться в ній). Методи внутрішнього сортування можна розділити на дві групи:

- методи, що не вимагають резерву пам'яті;

- методи, що вимагають резерву пам'яті.

До першої групи відносяться такі методи, як метод вибірки, "бульбашки", вставки, Шелла. До другої групи відносяться метод квадратичної вибірки, метод злиття та інші. Прості методи сортування (вибором, обміном, вставкою) вимагають приблизно n**2 порівнянь. Складніші алгоритми зазвичай забезпечують отримання результату за n*log2(n) порівнянь в середньому: сортування методом Шелла, злиттям, "швидке сортування". Проте оптимального у будь-якому випадку сортування не існує, оскільки їх ефективність істотно залежить від типу ключів в таблиці і їх попередній впорядкованості.

Розглянемо алгоритми найбільш рараспространенних методів внутрішнього сортування ( впорядкування виконується за збільшенням значень ключа ).

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

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

Використовуються два індекси i і j з початковими значеннями меж таблиці. Порівнюються ключі до[i] і до[j], і якщо перестановка не потрібна, то j зменшується на 1, і процес повторюється. У тому випадку, коли до[i]>=k[j], записи r[i] і r[j]

міняються місцями. Потім цей процес повторюється з i, збільшеним на 1, і фіксованим j до тих пір, поки не виникає інша перестановка. У цей момент j знову буде зменшене на 1, а i залишиться фіксованим, і так далі Процес виконується до тих пір, поки i< p>

Кожного разу таблиця розбивається на дві підтаблиці, одна з яких обробляється, тоді як межі другої запам'ятовуються з тим, щоб вона була оброблена пізніше. У цих цілях може бути використаний стек, що є матрицею з двох стовпців. У першому стовпці зберігаються нижні межі підтаблиць, що розділяються, в другому - верхні межі. Всякий раз одна з отриманих в результаті розділення підтаблиць піддається подальшому розділенню, а межі іншою поміщаються у вільний рядок стека (зазвичай в стек поміщаються межі більшої по довжині таблиці, оскільки це зменшує необхідний розмір стека). Як тільки завершується процес розділення поточної підтаблиці, тобто її довжина стане менше трьох, для розділення береться підтаблиця, межі якої були занесені в стек останніми. Рядок стека, в якому зберігалися ці межі, звільняється. Процес впорядкування завершується, коли стек повністю звільняється.

Розділення слід застосовувати для підтаблиць, довжина яких більше 9, а короткі подтаюліци упорядковувати методом вставки.

Стек займає мало місця.Например,стек з 20 рядків дозволяє упорядкувати таблицю, що містить до 10**7 записів.Крім того, в сучасних мовах програмування при роботі рекурсивних програм занесення і витягання із стека виконується автоматично, тому рекомендується використовувати саме цей

механізм. Середнє число порівнянь для даного алгоритму складає n*log(n)

де n - число записів в сортованій таблиці, m - розмір підтаблиці, сортованої методом вставки.

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

Як приклад розглянемо записи з наступними ключами:

42 23 74 11 36 58 94

Нижче приведена послідовність перестановок при переміщенні запису з ключем 42 на його кінцеву позицію. Підкреслені ключі, значення яких порівнювалися.

42 23 74 11 36 58 94

~~~ ~~~

42 23 74 11 36 58 94

~~~ ~~~

42 23 74 11 36 58 94

~~ ~~~

-----------------------------------

36 23 74 11 42 58 94

~~~ ~~~

36 23 74 11 42 58 94

~~~ ~~~

-----------------------------------

36 23 42 11 74 58 94

~~~ ~~~

----------------------------------

36 23 11 42 74 58 94

~~

В результаті запису з початковими ключами розбиті на дві подтабліци,а саме, на набори [36,23,11] і [74,58,94],к яким застосовується той же метод.

Як розділяє можна вибрати x - будь-який елемент таблиці, наприклад, середній (l=n/2) .сначала таблиця розглядається зліва від x до тих пір, поки не виявиться ключ до[i]>x (до[i]<=x, i:=i+1; якщо до[i]>x,то i фіксується). Потім таблиця є видимою справа, поки виконується до[j]>=x (j:= j-1; якщо до[j]

Для кожної з отриманих частин процес повторюється.