Головна

Природне злиття

  1. Віра в надприродне як джерело протиріч культового мистецтва
  2. Збалансоване багатошляхове злиття
  3. ЗЛИТТЯ ІЗОЛЬОВАНИХ ПРОТОПЛАСТІВ
  4. Природне середовище
  5. Пряме злиття
  6. Сортування злиттям

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

Серією називається підпослідовність записів аі, а(i+1), ..., aj така, що ak<=a(k+1) для всіх i<= k<j, аі < а(і-1) і aj>a(j+1). Метод природного злиття ґрунтується на розпізнаванні серій при розподілі і їх використанні при подальшому злитті.

Як і у разі прямого злиття, сортування виконується за декілька кроків, в кожному з яких спочатку виконується розподіл файла А по файлам В і С, а потім злиття В і С у файл А. При розподілі розпізнається перша серія записів і переписується у файл В, друга - у файл С і т.ін. При злитті перша серія записів файлу В зливається з першою серією файлу С, друга серія В з другою серією С і т.ін. Якщо перегляд одного файлу закінчується раніше, ніж перегляд іншого (внаслідок різної кількості серій), то залишок не до кінця переглянутого файла повністю копіюється в кінець файла А. Процес завершується, коли у файлі А залишається тільки одна серія. Приклад сортування файла показаний на рисунках 34 і 35.

Рисунок 34 - Зовнішнє пряме сортування злиттям. Перший крок.

Рисунок 35 - Зовнішнє пряме сортування злиттям. Другий крок.

Очевидно, що кількість зчитувань/перезаписів файлів при використанні цього методу буде не більша, ніж при застосуванні методу прямого злиття, а в середньому - менша. З другого боку, збільшується кількість порівнянь за рахунок тих, які потрібні для розпізнавання кінців серій. Крім того, оскільки довжина серій може бути довільною, то максимальний розмір файлів В і С може бути близький до розміру файла А.

 



  4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   Наступна

Алгоритм проходження графу вшир | Методи обчислення адреси | Методи обчислення адреси | Сортування злиттям | Метод простого включення | Метод Шелла | Сортування вибором | Сортування за допомогою дерева | Сортування злиттям | Багатофазне сортування |

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