Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

Пряме злиття

 

Припустимо, що є послідовний файл А, що складається з записів а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 – Приклад зовнішнього сортування простим злиттям

 

Початковий стан файла 8 23 5 65 44 33 1 6
Перший крок  
Розподіл
Файл В 8 5 44 1
Файл С 23 65 33 6
Злиття: файл А 8 23 5 65 33 44 1 6
Другий крок Розподіл  
Файл В 8 23 33 44
Файл С 5 65 1 6
Злиття: файл А 5 8 23 65 1 6 33 44
Третій крок Розподіл  
Файл В 5 8 23 65
Файл С 1 6 33 44
Злиття: файл А 1 5 6 8 23 33 44 65

 

 

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

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

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

 

 

 

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

 

 

 

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

 

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

 


Читайте також:

  1. А. Структурно-функціональна класифікація нирок залежно від ступеню злиття окремих нирочок у компактний орган.
  2. Антропогенний вплив на природне середовище та сучасні екологічні проблеми
  3. Види і мотиви злиття і поглинання
  4. Види освітлення. Природне. Штучне: робоче та аварійне.
  5. Глобальний менеджмент і природне середовище
  6. Загальні закономірності виникнення техногенних небезпек, їх вплив на природне середовище та людину. Засоби та заходи зниження їх наслідків.
  7. Загальні закономірності виникнення техногенних небезпек, їх вплив на природне середовище та людину. Засоби та заходи зниження їх наслідків.
  8. Культурне і природне в мові
  9. Платежі за забруднення та інші негативні впливи на навколишнє природне середовище
  10. Приклади злиття горизонтального типу в Україні
  11. Природне забруднення біосфери




Переглядів: 1566

<== попередня сторінка | наступна сторінка ==>
Багатофазне сортування | Багатофазне сортування

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.003 сек.