Знайомство з сортуванням файлів, Детальна інформація

if n > 0 then outtree(g, A, n);

if ch > 0 then

begin

copyfa(h, A, n); ch:=0;

indbld(n); outtree(g, A, n)

end

Із зазначених вище підпрограм уточнимо лише процедуру outtree, решта залишаються вправами (див.підр.17.4.2).

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

begin

while m>3 do

begin

write(g, A[P[1]]); indswap(1, m);

m:=m-1; indreorg(1, m);

end;

write(g, A[P[1]]);

if m=3 then

if A[P[2]] > A[P[3]] then indswap(2, 3);

if m > 1 then write(g, A[P[2]]);

if m=3 then write(g, A[P[3]])

end

Задача

18.1. Написати програму сортування файла на основі ідей, описаних у підр.18.1–18.2.

3. Індексові файли

Почнемо з прикладу. Дані про абонента телефонної мережі включають в себе його номер, прізвище, адресу та багато іншої інформації. Шукати дані про абонента доводиться, наприклад, як за його номером, так і за прізвищем. А пошуки у відсортованому файлі значно швидші, ніж у невідсортованому. Отже, за значеннями якого з полів – номера чи прізвища – слід сортувати файл?

Відповідь на це питання дає застосування так званих індексових файлів. Розглянемо послідовність пар із рядків і чисел:

<("qw", 31), ("er", 86), ("ty", 12), ("io", 24)>.

Якщо замінити пари їх номерами (індексами) у послідовності, то упорядкування пар за алфавітним зростанням їх рядків має вигляд <2, 4, 1, 3>, тобто найменшим є "er" із пари 2, наступним – "io" із 4 тощо. Така послідовність номерів і є змістом індексового файла, відповідного цій послідовності пар за упорядкуванням рядків. Водночас, можна так само упорядкувати пари за зростанням чисел: <3, 4, 1, 2>, і це буде змістом іншого індексового файла.

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

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

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