Размещено на http://www.allbest.ru/

Курсовая работа по предмету:

«Структуры и алгоритмы обработки данных»

«Анализ сортировок на двусвязном списке»

Задание

Реализовать сортировки на двусвязном списке в последовательной памяти. Провести сравнительный анализ их работы.

Теоретические сведения

Линейный список (ЛС) -- это конечная последовательность однотипных элементов (узлов). Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться, поэтому ЛС - динамическая структура.

Над СД ЛС определены следующие основные операции:

1. Инициализация.

2. Включение элемента.

3. Исключение элемента.

4. Чтение текущего элемента.

5. Переход в начало списка.

6. Переход в конец списка.

7. Переход к следующему элементу.

7. Переход к i-му элементу.

8. Определение длины списка.

9. Уничтожение списка.

Кардинальное число СД ЛС определяется по формуле

CAR(ЛС)=CAR(BaseType)0 +CAR(BaseType)1+… +CAR(BaseType)max

где CAR(BaseType) - кардинальное число элемента ЛС типа BaseType, max - максимальное количество элементов в ЛС (не всегда определено, т.к. может зависеть от объёма свободной динамической памяти).

На абстрактном уровне ЛС представляет собой линейную структуру - последовательность.

На физическом уровне ЛС может быть реализован последовательной или связной схемой хранения. Располагаться ЛС может в статической или динамической памяти. ЛС, реализованный последовательной схемой хранения, называется последовательным линейным списком (ПЛС). ЛС, реализованный связной схемой хранения, называется связным линейным списком (СЛС). Для реализации ПЛС используется вспомогательная встроенная СД - массив, элементы которого могут быть элементами ПЛС. Доступ к элементам ПЛС - прямой. Для реализации СЛС используется множество связанных элементов типа “запись”, связь между которыми устанавливается с помощью поля-указателя. Элементы СЛС могут располагаться в массиве или в динамической памяти. СЛС подразделяются на односвязные линейные списки (ОЛС) и двусвязные линейные списки (ДЛС). В ОЛС каждый элемент состоит из информационного поля (поле данных) и одного поля-указателя, содержащего адрес следующего элемента. В ДЛС каждый элемент состоит из информационного поля и двух полей-указателей, одно из которых содержащих адрес следующего элемента в списке, а другое - предыдущего. Реализуется ОЛС, как правило, с первым фиктивным элементом, поле данных которого не используется, а ДЛС - с первым и последним фиктивным элементом. Введение фиктивных элементов позволяет упростить реализацию некоторых операций над ЛС.

Рассмотрим некоторые принципы реализации ЛС.

Реализация ПЛС.

Последовательному линейному списку можно поставить в соответствие дескриптор, который состоит из 3-х полей:

1 - массив, на основе которого реализуется ПЛС;

2 - индекс текущего элемента;

3 - длина ПЛС.

Дескриптор располагается в статической памяти в виде переменной соответствующего типа. Массив, на основе которого реализуется ПЛС, также располагается в статической памяти.

Дескриптор ПЛС состоит из 4-х полей:

1 - указатель на массив, на основе которого реализуется ПЛС;

2 - количество элементов массива;

3 - индекс текущего элемента;

4 - длина ПЛС.

Дескриптор располагается в статической памяти в виде переменной соответствующего типа. Массив, на основе которого реализуется ПЛС, располагается в динамической памяти. Память под массив выделяется при инициализации ПЛС и количество элементов этого массива заносится во второе поле.

Элементы ПЛС могут находиться непосредственно в элементах массива, или в динамической памяти, а их адреса - в массиве.

Реализация ДЛС.

В статической памяти находится дескриптор ДЛС, состоящий из 3-х полей:

1 - указатель на первый фиктивный элемент ДЛС;

2 - указатель на последний фиктивный элемент ДЛС;

3 - указатель на текущий элемент;

4 - длина ДЛС.

Адреса фиктивных элементов определяется при инициализации.

Элемент ДЛС может содержать либо поле данных, либо адрес данных и располагаться либо в динамической памяти, либо в массиве аналогично элементам ОЛС.

Временная сложность (ВС) алгоритма - это зависимость времени выполнения алгоритма от количества обрабатываемых входных данных. Здесь представляет интерес среднее и худшее время выполнения алгоритма. ВС можно установить с различной точностью. Наиболее точной оценкой является аналитическое выражение для функции: t=t(N), где t - время, N - количество входных данных (размерность). Данная функция называется функцией временной сложности (ФВС).

Например: t = 5N2 + 32N + 1. Такая оценка может быть сделана только для конкретной реализации алгоритма в конкретной вычислительной системе и не пригодна для оценки алгоритма. Для сравнения алгоритмов достаточно определить лишь порядок функции временной сложности t(N).

Две функции f1(N) и f2(N) -- одного порядка, если

Иначе это записывается в виде: f1(N)=О(f2(N)) (Читается " О большое ").

Порядок функции, заданной многочленом, определяется только тем членом, который растет быстрее других с увеличением N, причём коэффициент при нём не учитывается.

Для определения порядка функции ВС алгоритма достаточно найти зависимость числа выполнения того оператора от количества исходных данных, который выполняется в алгоритме чаще других.

Для оценки алгоритмов можно использовать функцию зависимости числа операций сравнения C=C(N) от количества обрабатываемых данных, т.к. функции t(N) и C(N) - функции одного порядка.

Сортировка - это процесс перестановки элементов данного множества в определенном порядке. Сортировка является идеальным примером огромного разнообразия алгоритмов, выполняющих одну и ту же задачу, многие из которых в некотором смысле являются оптимальными, а большинство имеет какие-либо преимущества по сравнению с остальными. Поэтому на примере сортировки убеждаются в необходимости проведения сравнительного анализа алгоритмов.

Формулировка задачи может быть записана следующим образом.

Если даны элементы а1, а2 ,…, аn, то сортировка означает перестановку этих элементов в массив ак1, ак2,…,акn, где при заданной функции упорядочения f справедливы отношения f(ак1)f(ак2) …f(акn). Обычно функция упорядочения f не вычисляется по какому-то специальному правилу, а является значением элемента.

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми значениями не меняется при сортировке; неустойчивым - в противном случае.

Методы сортировки, в зависимости от лежащего в их основе приема, можно разбить на три базовых класса:

сортировка вставками;

сортировка выбором;

сортировка обменом.

Сортировка выбором

При сортировке выбором из множества не отсортированных элементов выбирают наименьший и присоединяют его к отсортированным ключам.

Алгоритм сортировки выбором

1. Находим наименьший ключ в неупорядоченной части массива.

2. Меняем местами найденный элемент с тем, который соседствует с упорядоченной частью.

3. Пункты 1 и 2 выполняем, пока в неупорядоченной части имеется более одного элемента.

Начальные значения	37	06	71	83	41	03	61
Проход 1	37	06	71	83	41	03	61
Проход 2	03	06	71	83	41	37	61
Проход 3	03	06	71	83	41	37	61
Проход 4	03	06	37	83	41	71	61
Проход 5	03	06	37	41	83	71	61
Проход 6	03	06	37	41	61	71	83
Проход 7	03	06	37	41	61	71	83

Алгоритм сортировки выбором в некотором смысле противоположен алгоритму сортировки вставками. При сортировке вставками на каждом шаге рассматривается только один очередной элемент входной последовательности и все элементы готового массива для нахождения места вставки. При сортировке простым выбором рассматриваются все элементы входного массива, и наименьший из них отправляется в готовую последовательность.

Анализ сортировки простым выбором

При сортировке простым выбором число сравнений ключей не зависит от их начального порядка. На первом просмотре выполняется N-1 сравнение, на втором -- N-2 и т.д. Следовательно, общее число сравнений равно (N-1) + (N-2) + (N-3) + ... + 1=N*(N-1)/2, что составляет O(N2). Порядок функции ВС не зависит от упорядоченности сортируемого массива, однако время сортировки упорядоченного массива будет минимальным, т.к. от упорядоченности массива зависит число перестановок элементов.

Сортировка обменом

Идея обменной сортировки заключается в том, что два элемента, нарушающие требуемый порядок, меняются местами.

Начальные значения	37	06	71	83	41	03	61
Проход 1	03	37	06	71	83	41	61
Проход 2	03	06	37	41	71	83	61
Проход 3	03	06	37	41	61	71	83
Проход 4	03	06	37	41	61	71	83
Проход 5	03	06	37	41	61	71	83
Проход 6	03	06	37	41	61	71	83
Проход 7	03	06	37	41	61	71	83

Алгоритм сортировки обменом

1. Перебираем поочередно все пары соседних элементов, начиная с последнего, и меняем местами элементы в парах, нарушающих порядок.

2. Пункт 1 повторяем n-1 раз.

После первого прохода (п.1) минимальный элемент массива занимает первую позицию и в дальнейшем в сортировке не участвует. После второго прохода образуется упорядоченная последовательность из первых двух элементов массива и т.д., пока все элементы массива не будут отсортированы.

Анализ сортировки обменом

При использовании сортировки обменом число сравнений элементов не зависит от их начального порядка. На первом просмотре выполняется N-1 сравнение, на втором -- N-2 и т.д. Следовательно, общее число сравнений равно (N-1)+(N-2)+(N-3)+...+1=N*(N-1)/2, что составляет O(N2).

Перестановки в упорядоченном массиве не выполняются, а в массиве, упорядоченном в обратном порядке, их число равно числу сравнений элементов. Следовательно время выполнения алгоритма зависит от упорядоченности массива.

Cортировка Хоара

Сортировка Хоара - лучший из известных до сего времени метод сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар окрестил его быстрой сортировкой. Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно разбить массив на под массивы и сортировать под массивы меньшего размера.

30	10	40	20	15	17	45	60
(30	10	17	20	15)	(40	45	60)

Алгоритм быстрой обменной сортировки

1. Выбираем элемент массива в качестве разделителя.

2. Располагаем элементы меньшие разделителя в первой части массива, а большие - во второй.

3. Если число элементов в первой части массива больше 1, то применяем к ней алгоритм в целом.

4. Если число элементов во второй части массива больше 1, то применяем к ней алгоритм в целом. Конец алгоритма.

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

П.2 выполняется следующим образом: просматриваем массив от краев к центру и меняем местами элементы, нарушающие порядок.

Анализ сортировки Хоара

алгоритм сортировка

Пусть m=log2N, где N - количество элементов. Будем считать, что количество элементов, меньших разделителя, равно количеству элементов, больших разделителя, т.е. массив разбивается пополам на две равные части. Определим количество сравнений в этом случае:

N+2*(N/2)+…+m*(N/m)=O(N*m)=O(N*log2N).

Если каждый раз одна из частей массива содержит не более одного элемента, то порядок будет O(N2).

Характер разбиения массива, а, следовательно, и порядок функции ВС, зависит от соотношения разделителя и остальных элементов массива. Для определения “хорошего” разделителя имеются различные алгоритмы.

Текст программы

unit ListUnit;

interface

const

NOE = 200;

type

TDataType = Integer;

TIndex = 0..NOE;

TElement = record

Data: TDataType;

Next, Prev: TIndex;

end;

TOutputArray = array of TDataType;

TSerialList = object

private

NumberOfElements: TIndex;

Buffer: array [TIndex] of TElement;

OccupiedCells: array [TIndex] of Boolean;

Current: TIndex;

Head: TIndex;

Tail: TIndex;

NOC: Integer;

public

constructor Create;

destructor Destroy;

procedure SelectiveSort;

procedure QuickSort;

procedure ExchangeSort;

procedure GarbageCollector;

function Add(A: TDataType): Boolean;

function DeleteFirst(A: TDataType): Boolean;

function DeleteAll(A: TDataType): Boolean;

function Find(A: TDataType): Boolean;

function Read: TOutputArray;

function IsEmpty: Boolean;

function IsFull: Boolean;

function GetNOE: TIndex;

function GetNOC: Integer;

end;

implementation

{ TSerialList }

function TSerialList.Add(A: TDataType): Boolean;

begin

if IsEmpty then

begin

Head := 1;

Tail := 1;

Buffer[1].Data := A;

Buffer[1].Next := 0;

Buffer[1].Prev := 0;

OccupiedCells[1] := True;

Inc(NumberOfElements);

Result := True

end

else begin

if IsFull then

Result := False

else begin

Current := 1;

while OccupiedCells[Current] and (Current <= NOE) do

Inc(Current);

if Current > NOE then

Result := False

else begin

Buffer[Current].Data := A;

Buffer[Current].Prev := Tail;

Buffer[Current].Next := 0;

OccupiedCells[Current] := True;

Buffer[Tail].Next := Current;

Tail := Current;

Inc(NumberOfElements);

Result := True

end

end

end

end;

constructor TSerialList.Create;

begin

Head := 0;

Tail := 0;

NumberOfElements := 0;

Current := 1;

while Current <= NOE do

begin

OccupiedCells[Current] := False;

Inc(Current)

end

end;

function TSerialList.DeleteAll(A: TDataType): Boolean;

begin

Result := DeleteFirst(A);

if Result then

begin

while DeleteFirst(A) do;

Result := True

end

end;

function TSerialList.DeleteFirst(A: TDataType): Boolean;

begin

if IsEmpty then

Result := False

else begin

if Find(A) then

begin

if Current = Head then

begin

Head := Buffer[Head].Next;

Buffer[Head].Prev := 0;

OccupiedCells[Current] := False;

Dec(NumberOfElements)

end

else if Current = Tail then

begin

Tail := Buffer[Tail].Prev;

Buffer[Tail].Next := 0;

OccupiedCells[Current] := False;

Dec(NumberOfElements)

end

else begin

Buffer[Buffer[Current].Next].Prev := Buffer[Buffer[Current].Prev].Next;

Buffer[Buffer[Current].Prev].Next := Buffer[Buffer[Current].Next].Prev;

OccupiedCells[Current] := False;

Dec(NumberOfElements)

end;

Result := True

end

else

Result := False

end

end;

destructor TSerialList.Destroy;

begin

Create

end;

procedure TSerialList.ExchangeSort;

var

I, J: TIndex;

T: TElement;

begin

GarbageCollector;

NOC := 0;

for I := GetNOE downto 1 do

for J := 1 to GetNOE - 1 do

begin

Inc(NOC);

if Buffer[J].Data > Buffer[J + 1].Data then

begin

Inc(NOC);

T := Buffer[J];

Buffer[J] := Buffer[J + 1];

Buffer[J + 1] := T

end

end;

Head := 1;

Tail := GetNOE;

Current := 1;

while Current < GetNOE do

begin

Buffer[Current].Next := Current + 1;

Buffer[Current].Prev := Current - 1;

Inc(Current)

end;

Buffer[GetNOE].Next := 0;

Buffer[GetNOE].Prev := GetNOE - 1

end;

function TSerialList.Find(A: TDataType): Boolean;

begin

Current := Head;

while (Buffer[Current].Data <> A) and (Current <> 0) do

Current := Buffer[Current].Next;

Result := Buffer[Current].Data = A

end;

procedure TSerialList.GarbageCollector;

var

Sorted: TIndex;

Temp: TElement;

begin

Current := 1;

Sorted := NOE;

repeat

while OccupiedCells[Current] do

Inc(Current);

while not OccupiedCells[Sorted] do

Dec(Sorted);

if Current < Sorted then

begin

Buffer[Buffer[Current].Next].Prev := Sorted;

Buffer[Buffer[Current].Prev].Next := Sorted;

Temp := Buffer[Current];

Buffer[Current] := Buffer[Sorted];

Buffer[Sorted] := Temp;

OccupiedCells[Current] := True;

OccupiedCells[Sorted] := False

end

until Current > Sorted;

end;

function TSerialList.GetNOC: Integer;

begin

Result := NOC

end;

function TSerialList.GetNOE: TIndex;

begin

Result := NumberOfElements

end;

function TSerialList.IsEmpty: Boolean;

begin

Result := NumberOfElements = 0

end;

function TSerialList.IsFull: Boolean;

begin

Result := NumberOfElements = NOE

end;

procedure TSerialList.QuickSort;

procedure RQuickSort(iLo, iHi: TIndex);

var

Lo, Hi: TIndex;

T: TElement;

Mid: TDataType;

begin

Lo := iLo;

Hi := iHi;

Mid := Buffer[(Lo + Hi) div 2].Data;

repeat

Inc(NOC);

while Buffer[Lo].Data < Mid do

Inc(Lo);

while Buffer[Hi].Data > Mid do

Dec(Hi);

if Lo <= Hi then

begin

T := Buffer[Lo];

Buffer[Lo] := Buffer[Hi];

Buffer[Hi] := T;

Inc(Lo);

Dec(Hi)

end

until Lo > Hi;

if Hi > iLo then

RQuickSort(iLo, Hi);

if Lo < iHi then

RQuickSort(Lo, iHi)

end;

begin

GarbageCollector;

NOC := 0;

RQuickSort(1, GetNOE);

Head := 1;

Tail := GetNOE;

Current := 1;

while Current < GetNOE do

begin

Buffer[Current].Next := Current + 1;

Buffer[Current].Prev := Current - 1;

Inc(Current)

end;

Buffer[GetNOE].Next := 0;

Buffer[GetNOE].Prev := GetNOE - 1

end;

function TSerialList.Read: TOutputArray;

begin

GarbageCollector;

SetLength(Result, GetNOE + 1);

Current := Head;

while Current <> 0 do

begin

Result[Current - 1] := Buffer[Current].Data;

Current := Buffer[Current].Next

end

end;

procedure TSerialList.SelectiveSort;

var

Sorted: TIndex;

Temp: TElement;

begin

GarbageCollector;

Current := 1;

NOC := 0;

while Current < GetNOE do

begin

Sorted := GetNOE;

Inc(NOC);

while Sorted >= Current + 1 do

begin

if Buffer[Current].Data > Buffer[Sorted].Data then

begin

Inc(NOC);

Temp := Buffer[Current];

Buffer[Current] := Buffer[Sorted];

Buffer[Sorted] := Temp

end;

Dec(Sorted)

end;

Inc(Current)

end;

Head := 1;

Tail := GetNOE;

Current := 1;

while Current < GetNOE do

begin

Buffer[Current].Next := Current + 1;

Buffer[Current].Prev := Current - 1;

Inc(Current)

end;

Buffer[GetNOE].Next := 0;

Buffer[GetNOE].Prev := GetNOE - 1

end;

end.

Анализ результатов

В ходе тестирования были получены следующие результаты:

Список не упорядочен

Количество элементов в списке	5	20	35	50	65	80	95	110
Сортировка выбором	7	63	290	268	413	617	792	1117
Сортировка обменами	27	476	1494	3102	5275	7893	11235	14875
Быстрая сортировка	5	27	59	91	127	162	193	237

Список упорядочен по неубыванию

Количество элементов в списке	5	20	35	50	65	80	95	110
Сортировка выбором	4	19	34	49	64	79	94	109
Сортировка обменами	20	380	1190	2450	4160	6320	8930	11990
Быстрая сортировка	3	12	19	31	33	48	63	63



Список упорядочен по невозрастанию

Количество элементов в списке	5	20	35	50	65	80	95	110
Сортировка выбором	6	29	51	74	96	119	141	164
Сортировка обменами	30	570	1785	3675	6240	9480	13395	17985
Быстрая сортировка	5	22	36	55	65	88	110	117

Выводы

Анализируя результаты исследований, можно сделать вывод о том, что в независимости от того на чём сортировки реализованы, результаты получаются одни и те же: быстрая сортировка (Хоара) -- самая быстрая из сортировок, у которой логарифмическая характеристика, а не линейная, что, кстати, видно из графиков.

Список использованной литературы

1. В. Г. Синюк. Лекции по структурам данных.

2. К. Пачеко, С. Тейксейра. Delphi 5. Руководство разработчика. Т. 1, 2.

Размещено на Allbest.ru