If l<j then begin

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

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

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

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

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

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

Внаслідок цього маємо послідовність пар, кожна з яких є послідовністю довжиною 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

 

 

 

 

Type

Item = record

Key: integer

End;

High = array [1..T] of integer;

Const H: High = (9, 5, 3, 1); {Н-масив констант для описания приращений. H[1]<N}

Type index = 1..N;

Var A: array [Index] of item; i: integer;

Procedure ShellSort;

Var i,j,k,s:integer; x: item; m: 1..T;

Begin

For m:=1 to T do {Управление приращениями} Begin k:=H[m]; {установка m-го приращения}

for i:=k+1 to N do {формирование (перменная i) очередной группы h[m]сортировки} begin x:=a[i]; j:=i-k; {координата предидущего элемента в группе}

{Обработка группы}

While x.key<a[j].key do begin a[j+k]:=a[j]; j:=j-k; {координата очередного обрабатываемого элемента в группе} if j<=0 then break; end; a[j+k]:=x; {Размещенение элемента на своем месте в группе} end; end; end; {ShellSort}

Пирамидальная сортировка:

Метод основан на повторном выборе наименьшего ключа среди n элементов, затем среди n-1 элементов и т.д. Количество сравнений образует арифм. прогрессию, а их сумма равна (n²-n)/2.После каждого прохода оставлять больше информации, чем простое указание на значение и координату наименшего в данном проходе элемента. ShiftMin выполняет добавление к пирамиде нового элемента, состоящего на позиции ls, а затем сдвигами уст. этот эл. в наджлежащую позицию, пирамида разширяется влево на 1 эл.

Const N=…; Type index =1..N; Item = record Key: integer end; Var array [index] of item; i: integer;

Procedure HeapSort;

Var l,r:index; x:item;

Procedure ShiftMax(ls,rs: index); var I,j: integer; x: item; begin i:=ls; j:=2*ls; x:=a[ls]; { нов. эл. ставится в вершину пирамиды (пирамида расширяется влево) } if (j<rs)and(a[j].key<a[j+1].key) then j:=j+1; while (j<=rs) and (x.key<a[j].key) do { сдвиги соотв. эл. для освобождения места пришедшему элементу } begin a[i]:=a[j]; i:=j; j:=2*j; if (j<rs) and (a[j].key<a[j+1].key) then j:=j+1; end; a[i]:=x; { пришедший эл. размещается на своем месте } end;

Begin l:=(n div 2)+1; r:=n; while l>1 do { самый большой эл. помещается в вершину пирамиды (в эл. a[1]) } begin l:=l-1; shiftmax (l, r); end; while r>1 do { перемещение очередного самого большого элемента из вершины пирамиды на его место в отсортированной последовательности } begin x:=a[1]; a[1]:=a[r]; a[r]:=x; r:=r-1; shiftmax (l, r); end; end; {HeapSort}

Быстрая сортировка (рекурсивная):

Суть метода для достижение наибольшей эффективности желательно производить обмены эл. на больших растояниях. Например, пусть дан массив из n эл. с ключами, расположеными в обратном порядке. Этот массив можно отсортировать, выполнил всего n/2 обменов, если поменять сначала самый левый и самый правый элементы. Затем среди оставшихся эл. проделаем те же действия и т.д. постепенно продвигаясь с двух концов массива к середине. Расм. Алгоритм {Sort}:

1. Выбирается сл. образом, какой-то эл. и обозначается как x. 2. Выполняется просмотр массива слева (от начала) пока не встретится эл. a_i>x. 3. Выполняется просмотр массива справа (от начала) пока не встретится эл. a_j>x. 4. Меняются местами эл. a_i и a_j. 5. Продол. процесс просмотра с обменом, пока оба просмотра не встретятся где-то посредине.

Const N=…; Type index =1..N; Item = record Key: integer end; Var array [index] of item; i: integer;

Procedure QuickSort;

Procedure Sort(l,r: index);

Var i,j: integer; w,x:item; begin i:=l; j:=r; { определяется эл. х, который будет выступать в качестве барьера посреди обрабатываемого массива } x:=a[(l+r) div 2]; repeat { просмотр массива } while a[i].key<x.key do i:=i+1; while x.key<a[j].key do j:=j-1;

if i<=j then begin w:=a[i]; a[i]:=a[j]; a[j]:=w; i:=i+1; j:=j-1; end; until i>j;

if l<j then Sort(l,j); { Обрабатывается левый подмассив } if i<r then Sort(l,j); { Обрабатывается правый подмассив } end; {Sort}

begin Sort (1, N); end; {QuickSort}

 

Быстрая сортировка:

Procedure NotRecQuickSort(var A: Tarr); var i,j,l,r: integer; w,x: item;

Qstack: array of Record L,r: integer; end;

TopQStack: integer; N: integer;

Begin

N:= length (A); SetLenght (Qstack, Ln(N) div (2)); TopQStack:=0; Qstack[1].l:=0;

Qstack[1].r:=N-1;

Repeat

L:=Qstack[TopQStack].l;

R:=Qstack[TopQStack].r;

TopQStack:=TopQStack-1;

Repeat

i:=l; j:=r; x:=A[(l+r) div 2];

Repeat

while a[i].key<x do i:=i+1;

while x.key<a[j].key do j:=j-1;

if i<=j then begin

w:=a[i];

a[i]:=a[j];

a[j]:=w;

i:=i+1;

j:=j+1;

end;

until i>j;

if l<j then begin

TopQStack:=TopQStack+1;

Qstack[TopQstack].L:=i;

Qstack[TopQstack].R:=r;

R:=j;

Until l>=r;

Until TopQStack=0;

End; {NotRecQuickSort}