Сравнение рассмотренных методов

 

Метод поиска	Хранение в массиве			Хранение в списке
	Поиск	Добавление	Удаление	Поиск	Добавление	Удаление
Линейный	T(n)	T(1)	T(n)	T(n)	T(1)	T(n)
Быстрый последовательный	T(n)	T(1)	T(n)	T(n)	T(1)	T(n)
Дихотомический	T(log(n))	T(n)	T(n)	Хранение в списке невозможно
Интерполяционный	T(log(log(n)))	T(n)	T(n)	Хранение в списке невозможно

Приведенная табличка поможет сравнить методы друг с другом.

Быстрый последовательный поиск с хранением множества в списке (при списковом хранении удаление будет выполняться в среднем в 2 раза быстрее) лучше применять в случаях, когда операции добавления/удаления будут выполняться чаще операции поиска. В этом случае лучше проиграть на поиске, но выиграть на добавлении и удалении.

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

Лекция 12 Алгоритмы сортировки данных (2 часа)

 

План

12.1 Алгоритм 1. Сортировка вставками.

12.2 Алгоритм 2. Пузырьковая сортировка.

12.3 Алгоритм 3. Сортировка Шейкером.

12.4 Алгоритм 4. Сортировка слиянием.

 

Алгоритм 1. Сортировка вставками.

Это изящный и простой для понимания метод. Его суть состоит в том, что создается новый массив, в который мы последовательно вставляем элементы из исходного массива так, чтобы новый массив был упорядоченным. Вставка происходит следующим образом: в конце нового массива выделяется свободная ячейка, далее анализируется элемент, стоящий перед пустой ячейкой (если, конечно, пустая ячейка не стоит на первом месте), и если этот элемент больше вставляемого, то элемент подвигается в свободную ячейку (при этом на том месте, где он стоял, образуется пустая ячейка) и сравнивается следующий элемент. Так можно прийти к ситуации, когда элемент перед пустой ячейкой меньше вставляемого или пустая ячейка стоит в начале массива. Вставляемый элемент помещается в пустую ячейку. Таким образом, по очереди вставляются все элементы исходного массива. Очевидно, что если до вставки элемента массив был упорядочен, то после вставки перед вставленным элементом расположены все элементы, котрые меньше него, а после - больше. Так как порядок элементов в новом массиве не меняется, то сформированный массив будет упорядоченным после каждой вставки. А значит, после последней вставки получается упорядоченный исходный массив. Вот как такой алгоритм можно реализовать на языке программирования Pascal:

Program InsertionSort;

Var A,B: array[1..1000] of integer;

N,i,j: integer;

Begin

{Определение размера массива A (N) и его заполнение}

…

{ сортировка данных }

for i:=1 to N do

begin

j:=i;

while (j>1) and (B[j-1]>A[i]) do

begin

B[j]:=B[j-1];

j:=j-1;

end;

B[j]:=A[i];

end;

{Вывод массива B }

…

End.

 

Алгоритм 2. Пузырьковая сортировка.

Реализация данного метода не требует дополнительной памяти. Метод очень прост и состоит в следующем: берется пара рядом стоящих элементов, и если элемент с меньшим индексом оказывается больше элемента с большим индексом, то они меняются их местами. Эти действия продолжаются, пока есть такие пары. Легко понять, что когда таких пар не останется, то данные будут отсортированными. Для упрощения поиска таких пар данные просматриваются по порядку от начала до конца. Из этого следует, что за такой просмотр находится максимум, который помещается в конец массива, а потому следующий раз достаточно просматривать уже меньшее количество элементов. Максимальный элемент как бы всплывает вверх, отсюда и название алгоритма. Так как каждый раз на свое место становится по крайней мере один элемент, то не потребуется более N проходов, где N - количество элементов. Вот как это можно реализовать:

Program BubbleSort;

Var A: array[1..1000] of integer;

N,i,j,p: integer;

Begin

{Определение размера массива A (N) и его заполнение}

…

{ сортировка данных }

for i:=1 to n do

for j:=1 to n-i do

if A[j]>A[j+1] then

begin { Обмен элементов }

p:=A[j];

A[j]:=A[j+1];

A[j+1]:=P;

end;

{Вывод отсортированного массива A}

…

End.