МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів
Контакти
Тлумачний словник Авто Автоматизація Архітектура Астрономія Аудит Біологія Будівництво Бухгалтерія Винахідництво Виробництво Військова справа Генетика Географія Геологія Господарство Держава Дім Екологія Економетрика Економіка Електроніка Журналістика та ЗМІ Зв'язок Іноземні мови Інформатика Історія Комп'ютери Креслення Кулінарія Культура Лексикологія Література Логіка Маркетинг Математика Машинобудування Медицина Менеджмент Метали і Зварювання Механіка Мистецтво Музика Населення Освіта Охорона безпеки життя Охорона Праці Педагогіка Політика Право Програмування Промисловість Психологія Радіо Регилия Соціологія Спорт Стандартизація Технології Торгівля Туризм Фізика Фізіологія Філософія Фінанси Хімія Юриспунденкция |
|
||||||||||||||||||||||||||||||||||
Природне злиттяПряме злиття
Припустимо, що є послідовний файл А, що складається з записів а1,a2,…,an (знову для простоти припустимо, що n є ступенем числа 2). Вважатимемо, що кожен запис складається лише з одного елементу, що є ключем сортування. Для сортування використовуються два допоміжні файли В і С (розмір кожного з них буде n/2). Сортування складаєтся з послідовності кроків, в кожному з яких виконується розподіл стану файлу А у файли В і С, а потім злиття файлів В і С у файл А. (Помітимо, що процедура злиття для файлів ілюструється рисунком 33). На першому кроці для розподілу послідовно читається файл А, і записи а1, а3, …, а (n-1) пишуться у файл В, а записи а2, а4, …, аn – у файл С (початковий розподіл). Початкове злиття здійснюється над парами (а1,а2), (а3,а4), …, (а(n-1),аn), ш результат записується у файл А. На другому кроці знову послідовно читається файл А, і у файл В записуються послідовні пари з непарними номерами, а у файл С – з парними. При злитті утворюються і пишуться у файл А впорядковані четвірки записів. І так далі. Перед виконанням останнього кроку файл А міститиме дві впорядковані послідовності розміром n/2 кожна. При розподілі перша з них потрапить у файл В, а друга – у файл С. Після злиття файл А міститиме повність впорядковану послідовність записів. У таблиці 10 показаний приклад зовнішнього сортування простим злиттям. Заз начимо, що для виконання зовнішнього сортування методом простого злиття в основній памяті вимагається розташувати всього дві змінні – для розміщення записів з файлів В і С.
Таблиця 10 – Приклад зовнішнього сортування простим злиттям
При використанні методу прямого злиття не береться до уваги те, що початковий файл може бути частково відсортованим, тобто містити впорядковані підпослідовності записів. Серією називається підпослідовність записів аі, а(i+1), ..., aj така, що ak<=a(k+1) для всіх i<= k<j, аі < а(і-1) і aj>a(j+1). Метод природного злиття ґрунтується на розпізнаванні серій при розподілі і їх використанні при подальшому злитті. Як і у разі прямого злиття, сортування виконується за декілька кроків, в кожному з яких спочатку виконується розподіл файла А по файлам В і С, а потім злиття В і С у файл А. При розподілі розпізнається перша серія записів і переписується у файл В, друга - у файл С і т.ін. При злитті перша серія записів файлу В зливається з першою серією файлу С, друга серія В з другою серією С і т.ін. Якщо перегляд одного файлу закінчується раніше, ніж перегляд іншого (внаслідок різної кількості серій), то залишок не до кінця переглянутого файла повністю копіюється в кінець файла А. Процес завершується, коли у файлі А залишається тільки одна серія. Приклад сортування файла показаний на рисунках 34 і 35.
Рисунок 34 – Зовнішнє пряме сортування злиттям. Перший крок.
Рисунок 35 – Зовнішнє пряме сортування злиттям. Другий крок.
Очевидно, що кількість зчитувань/перезаписів файлів при використанні цього методу буде не більша, ніж при застосуванні методу прямого злиття, а в середньому – менша. З другого боку, збільшується кількість порівнянь за рахунок тих, які потрібні для розпізнавання кінців серій. Крім того, оскільки довжина серій може бути довільною, то максимальний розмір файлів В і С може бути близький до розміру файла А.
Читайте також:
|
|||||||||||||||||||||||||||||||||||
|