На головну

Третє розбиття і злиття призводять до потрібного результату

  1. У чому особливості комп'ютерів третього покоління?
  2. Введення до третьої частини
  3. Всеросійського ринку. Почалося злиття окремих земель в єдину
  4. Другого, третього і загального видів
  5. Гіпотеза Максвелла про струмі зміщення. Взаімопревращаемость електричних і магнітних полів. Третє рівняння Максвелла
  6. Дія третя - Нієншанц
  7. Дія третя. Сума (різниця) матриць.

Про, 12, 18, 42, 44, 55, 67, 94

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

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

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



 масиву. Після кожного проходу масиви «міняються ролями», вихідний стає вхідним і навпаки.

Мал. 3.22. Схема сортування прямим злиттям для двох файлів

Програму можна спростити, об'єднавши два масиви в один масив подвійної довжини. Отже, масив даних представимо в такий спосіб:

а = (int *) malloc (2 * п * sizeoj {ini)); . нехай l, j - Фіксують два вихідних елемента; до, I - Два вихідних. Вихідні дані - це елементи а \, ..., ап. Для вказівки напряму пересилання введемо логічну змінну up. якщо ір = 1, то в поточному проході компоненти cii, ..., an рухаються на місце ап+ \, ..., А2г' якщо ж ір = 0, то ап+ \, ..., А1п пересилаються в at, ..., An. Між послідовними проходами значення up змінюється на протилежне. нехай р - Довжина зливаються послідовностей. Початкове значення р дорівнює 1, і перед кожним наступним проходом вона подвоюється. Для простоти ми припускаємо, що завжди п дорівнює ступеню двійки.




хешування таблиць | Введення в сортування | Функція сортування за допомогою методу прямого включення | початкові ключі | Функція сортування прямим обміном | Сортування включеннями з убутним збільшенням | Функція сортування Шелла | Сортування за допомогою дерева | пірамідальна сортування | Швидке сортування |

© um.co.ua - учбові матеріали та реферати