САНКТ-ПЕТЕРБУРГСКИЙ ТЕХНИЧЕСКИЙ КОЛЛЕДЖ УПРАВЛЕНИЯ И КОМЕРЦИИ

Наше знайомство з методами сортування масивів ще не закінчене. Але для засвоєння більш довершених методів слід спочатку познайомитися зі складними структурами даних (дерева, списки, стеки тощо). Це буде зроблено пізніше, а зараз займемося сортуванням послідовностей.

І. Метод простого злиття (двофазний метод)

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

Візьмемо для прикладу масив:

Загальна кількість записів може бути невідомою, тому записи у дві підпослідовності направляють через один:

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

Внаслідок цього маємо послідовність пар, кожна з яких є послідовністю довжиною 2, що вже є відсортованою:

.

.

.

.

.

.

.

.

На другому проході знову ділимо послідовність на дві з рівною кількістю пар (перша фаза другого проходу).

		.			.			.			.
		.			.			.			.

Друга фаза другого проходу - злиття пар по одній з кожного пристрою у четвірки, всередині яких запроваджено впорядкованість:

.

.

.

.

У загальному випадку на k-му проході послідовність розкладається на групи по 2k елементів, причому всередині кожна група вже є впорядкованою підпослідовністю. Процес продовжується до тих пір, поки довжина 2k не стане довше за n - довжину всієї послідовності. У даному разі послідовність буде розбито на дві з четвірками,

				.					.
				.					.

які зіллються у вісімки:

.

.

Після цього залишиться останній етап, хід якого є очевидним.

ІІ. Метод простого злиття (однофазний метод)

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

На k-му проході маємо 2 послідовності, у яких записи утворюють групи по 2k штук і є відсортованими в середині кожної групи. Протягом проходу з кожних двох груп довжиною 2k утворюється злиттям одна група довжиною 2k+1 і нові групи записуються по черзі на вихідні два носії.

Вихідні та вхідні носії послідовно міняються місцями до тих пір, поки весь файл не утворюватиме єдиної впорядкованої послідовності.

 

3. Сортування масива рядків

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

Порівняння рядків здійснюється зліва направо до першого незбіжного символу, і той рядок вважають більшим, в якому перший незбіжний символ має більший номер у стандартній таблиці кодів:

‘Іванчук’ > ’Іванченко’

З двох збіжних за символами рядків різної довжини меншим є коротший: ’ABR’ < ’ABRAKAD’

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

Для сортування використовуємо метод швидкого сортування.

Процедура сортування рядкiв має вигляд:

Procedure SortString (Var inm:StringArray; n:Integer);

{StringArray – масив рядків, n– кількість рядків}

Procedure InSort (left,right:Integer; Var m:StringArray);

Var

a,b: InData;

i,j: Integer;

Begin

i:=left;

j:=right;

a:= m[(left + right) div 2];

Repeat

While m[i] < a Do i:=i+1;

While a < m[j] Do j:=j–1;

If i<=j Then

Begin

b:=m[i];

m[i]:=m[j];

m[j]:=b;

i:=i+1;

j:=j–1

End

Until i>j;

If left<j Then InSort (left,j,m);

If i<right Then InSort (i,right,m);

End;

Begin

InSort (1,n,inm);

End;

4. Сортування файлів

Сортування здійснюється відповідно до значення якої-небудь ознаки (наприклад, за табельним номером).

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

В залежності від засобу доступу до файлу сортування поділяється на послідовне та пряме. Розглянемо алгоритм прямого сортування записів у типізованому файлі.

 

{ Створити файл записів: табельний номер, прізвище, ім’я, по батькові, оклад; відсортувати за табельним номером. Сортування виконується без створення додаткового файлу, на тому ж місці.}

 

 

Uses Crt;

Type

Karta = Record

tabnomer: Integer;

fio: String[20];

oklad: Real;

End;

Stroka = String[80];

Fv = File Of Karta;

Var

test: Karta;

t,t2: Integer;

namef: Fv;

{------------------------}

{ Створення файлу }

Procedure Sozd;

Begin

Assign(namef, ’a:Sps.txt’);

ReWrite(namef);

While True Do

Begin

Write(’Табельний номер:’);

Readln(test.tabnomer);

If test.tabnomer = 0 Then

Begin

Close(namef);

Exit;

End;

Write(’Оклад:’);

Readln(test.oklad);

Write(’Прізвище...:’);

Readln(test.fio);

Write(namef,test);

End;

End; {Sozd}

{-----------------------------------------------}

Function Poisk(Var fpoisk:Fv; i:Integer):Integer;

Var

t: Karta;

Begin

i:=i-1;

Seek(fpoisk,i);

Read(fpoisk,t);

Poisk:=t.tabnomer;

End; {Poisk}

{----------------------------------------}

Procedure SortFile(Var zam:Fv; count:Integer);

Procedure SortIn(left,right:Integer);

Var

i,j,s: Integer;

x,y,z: Karta;

 

Begin

i:=left;

 

j:=right;

s:=(left+right) div 2;

Seek(zam,s–1);

Read(zam,x);

Repeat

While Poisk(zam,i) < x.tabnomer Do i:=i+1;

While x.tabnomer < Poisk(zam,j) Do j:=j–1;

If i<=j Then

Begin

Seek(zam,i–1);

Read(zam,y);

Seek(zam,j–1);

Read(zam,z);

Seek(zam,j–1);

Write(zam,y);

Seek(zam,i–1);

Write(zam,z);

i:=i+1;

j:=j–1;

End

Until i>j;

If left<j Then SortIn(left,j);

If i<right Then SortIn(i,right);

End; {SortIn}

Begin

SortIn(1,count);

End; {SortFile}

{---------------------------------}

Begin

ClrScr;

Sozd;

Assign(namef,’a:Sps.txt’);

Reset(namef);

t:=FileSize(namef);

SortFile(namef,t);

Reset(namef);

ClrScr;

Writeln(’Вiдсортований список’);

While Not Eof (namef) Do

Begin

Read(namef, test);

Writeln(test.tabnomer:10, test.fio:20, test.oklad:10);

End;

Close(namef);

Repeat Until KeyPressed

End

 

 

 

 

САНКТ-ПЕТЕРБУРГСКИЙ ТЕХНИЧЕСКИЙ КОЛЛЕДЖ УПРАВЛЕНИЯ И КОМЕРЦИИ