програм, програм для обробки текстів і баз даних [2].
2. ПОСТАНОВКА ЗАВДАННЯ
В
2.1 АНАЛІЗ ІСНУЮЧИХ РІШЕНЬ ПОСТАВЛЕНОЇ ЗАВДАННЯ
В даний час існує безліч алгоритмів cортировка [5] масивів, які застосовуються залежно від того які умови функціонування стоять перед разрабатимаемой програмою.
1. Методи вставки. Алгоритм простих вставок. p align=left> 1.1. Бінарні вставки
1.2. Двоколійному вставки
1.3. Вставки одночасно декількох елементів. p align=left> 1.4. Вставки з убутним кроком (метод Шелла)
1.5. Вставки в зв'язаний список
1.6. Вставки в кілька пов'язаних списків
2. Обмінна сортування
2.1. Метод бульбашки
2.2. Модифікація методу бульбашки
2.3. Швидке сортування. p align=left> 2.4. Обмінна поразрядное сортування
2.5. Паралельна сортування Бетчера
3. Сортування за допомогою вибору
(Використання пов'язаного списку для зберігання
інформації про проміжні максимумах.)
4. Сортування за допомогою злиття
В
Методи вставки. Алгоритм простих вставок. p> Нижче описаний основний алгоритм простих вставок, який породжує кілька модифікацій, використовуються в завданнях. Алгоритм використовує прийом, яким користуються гравці в карти при сортуванні щойно розданої колоди: чергова карта вставляється між уже впорядкованими раніше.
Опис алгоритму простих вставок. Файл, що підлягає сортуванню, в загальному випадку складається з елементів-записів, що включають інформаційну частину і ключі, за якими виробляється впорядкування по зростанню. Оскільки інформаційна частина майже не впливає на процес соріровкі, будемо припускати, що файли, використовувані в прикладах, состот тільки з елементів-ключів, а інформаційна частина записи від сутствует.
Час роботи алгоритму t приблизно оцінюється формулою:
t = a * NР… + b * N
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Бінарні вставки
Для прискорення числа порівнянь при пошуку місця, в яке потрібно вставити елемент X, можна використовувати логарифмічний [5] пошук. Це означає, що спочатку Х порівнюється з елементом k [j/2], потім, залежно від результату порівняння, з елементом, що лежить посередині між 1 і j/2 або посередині між j/2 +1 і j і т.д. . При цьому чіслосравненій для кожного j дорівнює приблизно log (j). Число пересилань еле ментів у своїй не змінюється і залишається приблизно рівним NР…/4.
Час роботи алгоритму t приблизно оцінюється формулою:
t = a * NР… + b * N + c * N * logN
де a, b, c - невідомі константи, що залежать від програмної реалізації алгоритму.
В
двоколійному вставки
Число пересилань можна скоротити приблизно в 2 рази до NР…/8, якщо допустити зрушення елементів не тільки вправо, але і вліво. Для вихідного файлу резервується місце в пам'яті, рівне 2N +1, де N - число елементів у вихідному файлі. Перший елемент пересилається в середину вихідного файлу. Надалі елементи вихідного файлу зсуваються вправо або вліво залежно від того, в яку сторону потрібно зсувати менше елементів. Приєднання нових елементів до вихідного файлу відбувається як праворуч, так і ліворуч від центрального елемента з можливим зсувом вправо або вліво.
Час роботи алгоритму t приблизно оцінюється формулою:
t = a * NР… + b * N
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Вставки одночасно декількох елементів.
Модифікація методу простих вставок полягає в тому, що замість однієї змінної Х можна використовувати кілька змінних Х1, Х2, ... Xm, які мають значення елементів, що підлягають вставці у вже впорядковану частину файлу. Х1, X2, ... Xm впорядковані за зростанням, тому порівнюючи Xm в циклі по змінній i з елементами впорядкованої частини, ми можемо гарантувати, що, якщо черговий елемент k [i] більше Xm, то він більше і інших елементів. Перенесення елементів вихідного файлу вперед у циклі по i виконується на m елементів, тобто замість k [i +1] = k [i] у вихідному алгоритмі в модифікованому алгоритмі записується k [i + m] = k [i]. При знаходженні k [i] такого, що він менше Хm, Хm ставиться на місце k [i + m] і m зменшується на 1. Далі цикл по i продовжується з новим m. Економія числа переносів елементів досягається за рахунок переносів відразу на m елементів.
Час роботи алгоритму t приблизно оцінюється формулою
t = a * NР… + b * N + c * N * logN
де a, b, c - невідомі константи, що залежать від програмної реалізації алгоритму.
Вставки з убутним кроком (метод Шелла)
Ідея алгоритму полягає в обміні елементів, розташованих не тільки п...
