ЗНАЙОМСТВО З СОРТУВАННЯМ ФАЙЛІВ

Отже, перший елемент масиву має найменше значення, і його можна вивести в файл, у якому будуються неспадаючі відрізки. Після цього можна замістити це значення наступним із початкового файла та відновити властивість (18.1) у масиві. Звичайно, якщо нове значення менше виведеного, то його доведеться виводити вже в наступний відрізок результатного файла. В такому разі це значення не заміщає виведене, а запам'ятовується в додатковому сховищі. Коли в цьому сховищі накопичиться MX елементів, тоді виведемо елементи масиву A у порядку неспадання в результатний файл без їх заміщення новими. Після цього скопіюємо зміст сховища в масив, розташуємо значення в ньому згідно (18.1) і продовжимо виводити їх у порядку неспадання, заміщаючи їх значеннями з початкового файла.

Коли початковий файл буде прочитано, тоді ми виведемо зміст масиву в результатний файл і заповнимо масив із сховища. Після цього упорядкуємо його згідно (18.1) і знову виведемо його.

Уточнення наведеного опису почнемо з подання даних. Нехай тип елементів файла має ім'я T. Означимо типи файлів та масиву типу T:

type FoT=file of T; ArrT=array [1..MX] of T;При сортуванні дуже часто виконується обмін місцями значень елементів масиву. Оскільки розміри елементів файла можуть бути великими, обмін місцями таких значень буде займати чимало часу. Спробуємо скоротити цей час, заплативши за це витратами пам'яті.

Нехай A – глобальний масив типу ArrT, і в ньому зберігаються n значень із початкового файла f, n  MX. Для подання дерева з властивістю (18.1) означимо додатковий глобальний масив P. У ньому зберігаються індекси елементів масиву A, тобто елементи масиву P своїми значеннями вказують на елементи масиву A. Властивість (18.1) відтворюється такою перестановкою значень масиву P, що за k=1, 2, … , n div 2

A[P[k]]  A[P[2*k]] та A[P[k]]  A[P[2*k+1]] (18.2)

Таким чином, виведення значення першого елемента масиву в результатний файл g задається як write(g, A[P[1]]). Замість обміну місцями значень у масиві A відбувається обмін значень у масиві P, заданий процедурою indswap:

procedure indswap(i, k : Longint);

var v : Longint;

begin

v := P[i]; P[i] := P[k]; P[k] := v.

end;

Із описання розв'язання нашої задачі побудови файла з якомога довшими відрізками неважко виділити окремі підзадачі та задати їх розв'язання підпрограмами.

Однією з підзадач є "заповнити масив змістом сховища". Реалізуємо сховище додатковим файлом типу T. Нехай копіювання значень із нього в масив задає процедура із заголовком

procedure copyfa(var f : FoT; var A : ArrT; var m : Longint);

Третій параметр служить для повернення кількості скопійованих значень. Оскільки сховище має таке саме подання, що і початковий файл, цією процедурою можна скористатися і для початкового заповнення масиву з файла.

Наступна підзадача – "вивести елементи масиву A у порядку неспадання в результатний файл без їх заміщення новими". Нехай це виведення задає процедура outtree із заголовком

procedure outtree(var f : FoT; var A : ArrT; m : Longint);