Шейкерная сортировка

Лекция 13

Begin

Begin

Begin

While not EOF(F) do

Begin

Begin

Var

Begin

Ifnot AloneItem(sName, Salary, pNew) then

Begin

Var

Else

End

Begin

Begin

Begin

Begin

Implementation

Public

Protected

Type

Interface

Begin

Var

Uses

SysUtils,

Unit1 in 'Unit1.pas',

Unit2 in 'Unit2.pas',

Unit3 in 'Unit3.pas';

MyList1: MyList1Class;

MyList2: MyList2Class;

MyList3: MyList3Class;

MyList1:= MyList1Class.Create;

MyList1.AppendFromFile('c: List1.txt');

MyList1.ShowList;

WriteLN;

MyList2:= MyList2Class.Create;

MyList2.PrependFromFile('c: List2.txt');

MyList2.ShowList;

WriteLN;

MyList3:= MyList3Class.Create;

MyList3.InsertFromFile('c: List1.txt');

MyList3.ShowList;

Readln;

end.

Текст файла Unit1.pas:

unit Unit1;

pPersonType = ^PersonType;

PersonType = record

sName: string[40];

Salary: double;

pNext: pPersonType;

end;

MyList1Class = Class(TObject)

pHead, pTail: pPersonType;

constructor Create;

destructor Destroy;

function AloneItem(sName: string; Salary: double;

var pNew: pPersonType): boolean;

procedure AppendItem(sName: string; Salary: double);

procedure AppendFromFile(sFileName: string);

procedure ShowList;

end;

constructor MyList1Class.Create;

pHead:= Nil;

pTail:= Nil;

end;

destructor MyList1Class.Destroy;

// Код будет написан позже!

end;

function MyList1Class.AloneItem(sName: string; Salary: double;

var pNew: pPersonType): boolean;

New(pNew);

if pNew = Nil then Halt; // Нет места в памяти – прекращаем работу.

pNew^.sName:= sName;

pNew^.Salary:= Salary;

pNew^.pNext:= Nil;

if pHead = Nil then

pHead:= pNew; pTail:= pNew;

AloneItem:= True;

AloneItem:= False;

end;

procedure MyList1Class.AppendItem(sName: string; Salary: double);

pNew: pPersonType;

pTail^.pNext:= pNew;

pTail:= pNew;

end;

end;

procedur e MyList1Class.AppendFromFile(sFileName: string);

F: Text;

sName: string[40];

Salary: double;

Assign(F, sFileName);

{$I-}

Reset(F);

{$I+}

if IOResult <> 0 then

WriteLN('File ', sFileName, ' not found');

Halt;

end;

Readln(F, sName);

Readln(F, Salary);

AppendItem(sName, Salary);

end;

end;

procedure MyList1Class.ShowList;

pCurr:= pHead;

Writeln('Name':40, ' ', 'Salary');

Writeln('----':40, ' ', '------');

while pCurr <> Nil do

Writeln(pCurr^.sName:40, ' ', pCurr^.Salary:8:2);

pCurr:= pCurr^.pNext;

end;

end;

end.

Сортировка массивов (продолжение)

Данная сортировка есть улучшенный вариант сортировки методом пузырька.

На первом полу шаге проверяются (справа налево) все пары соседних элементов массива, начиная с последней. Если пара «неправильная» (левый элемент больше правого), производится обмен значениями в паре. Наименьший из всех элементов массива, если только он не стоял на первом месте, «просочится» в результате первого шага на первую позицию, поскольку он будет «неправильно» расположен относительно каждого из своих соседей слева. Вместе с тем, может оказаться и так, что первый элемент изначально был минимальным. Более того, может оказаться так, что первые k элементов изначально занимали подобающие им места, поскольку были наименьшими и стояли в порядке возрастания. Признаком такой ситуации может послужить то, что первые k элементов не участвовали в обмене. Следовательно, последующая сортировка должна затронуть только элементы массива с номерами большими, чем k. Переменная L (после изменения оператором L:=k+1) имеет смысл левой границы неотсортированной пока части массива.

На втором полу шаге проверяются (теперь слева направо) все пары соседних элементов массива, начиная с (L-1)–ой. Если последние k элементов изначально занимали подобающие им места, поскольку были наибольшими и стояли в порядке возрастания, переменная R (после изменения оператором R:=k-1) будет содержать информацию о правой границе неотсортированной пока части массива.

На втором и последующем шагах продолжают сближаться левая и правая границы неотсортированной части массива. Когда они «схлестнутся», сортировка заканчивается.

Шейкерная сортировка, увы, работает несколько хуже сортировки методом прямого выбора.

procedure ShakerSort;

Дата добавления: 2014-01-04