Алгоритмы сортировки данных

Алгоритмы

сортировки

данных

ОПРЕДЕЛЕНИЯ

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

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

Сортировка нужна для того, чтобы:

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

распределения данных.

ОПРЕДЕЛЕНИЯ

Критерии оценки различных методов сортировки:

• количество сравнений и пересылок записей;
• время сортировки заданного объема данных;
• требуемый объем ОП для сортировки;
• сложность алгоритмов и программ сортировки.

Практически каждый  алгоритм  сортировки можно разбить на 3 части:

• сравнение, определяющее упорядоченность пары элементов;
• перестановку , меняющую местами пару элементов;
• собственно сортирующий алгоритм, который осуществляет сравнение и  перестановку  элементов

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

КЛАССИФИКАЦИЯ

Классификация алгоритмов сортировки по сфере применения:

• Внутренняя сортировка  – это алгоритм сортировки, который в процессе  упорядочивания данных  использует только  оперативную память ( ОЗУ ) компьютера.
• Внешняя сортировка  – это алгоритм сортировки, который при проведении  упорядочивания данных  использует  внешнюю память (ж есткие диски).  Внешняя сортировка  разработана для обработки больших списков данных, которые не помещаются в  оперативную память .

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

Внутренняя  сортировка  значительно эффективней внешней, так как на обращение к оперативной памяти затрачивается намного меньше времени, чем к носителям.

МЕТОДЫ ВНУТРЕННЕЙ СОРТИРОВКИ

Методы внутренней сортировки можно разделить на следующие группы:

• сортировка вставкой (включением);
• сортировка выбором (выделением);
• сортировка обменом (“пузырьковая сортировка”);
• сортировка распределением;
• сортировка подсчетом;
• сортировка слиянием.

Сортировка вставкой(включением)

Принцип:

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

Таким образом, новое число сравнивается и при необходимости

меняется местами не со всеми числами в массиве,

а только до тех пор, пока в уже отсортированной части

массива не найдется меньшее его число.

my_ar[j]) do j:=j+1; {После окончания цикла индекс j фиксирует позицию вставки}   {Цикл сдвига элементов для освобождения позиции вставки} for k:=i-1 downto j do my_ar[k+1]:= my_ar[k]; {Вставка взятого элемента на найденную позицию} my_ar[j]:=b; end; " width="640"

Сортировка вставкой(включением)

for i:=2 to n do

begin

b:= my_ar[i]; {Взятие неотсортированного элемента}

  {Цикл поиска позиции вставки}

j:=1;

While (b my_ar[j]) do

j:=j+1; {После окончания цикла индекс j фиксирует позицию вставки}

{Цикл сдвига элементов для освобождения позиции вставки}

for k:=i-1 downto j do

my_ar[k+1]:= my_ar[k];

{Вставка взятого элемента на найденную позицию}

my_ar[j]:=b;

end;

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

Принцип:

• Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го до n-го (последнего) элемента и меняем его местами с первым элементом.
• На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом.
• И так далее для всех элементов до (n-1)-го.

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

for i:=1 to n-1 do

begin

{Поиск минимального элемента в диапазоне от i-го до n-го}

Min:= my_ar[i];

Imin:=i;

for j:=i+1 to n do

If my_ar[j]

begin

Min:=my_ar[j];

Imin:=j;

end;

{Обмен местами минимального и i-го элементов}

My_ar[IMin]:=my_ar[i];

my_ar[i]:=Min;

end;

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

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

Т. е. если два элемента расположены неупорядоченно, то они меняются местами.

К обменным сортировкам относятся:

• метод пузырькового всплытия;
• быстрая сортировка (обменная сортировка с разделением);
• обменная сортировка со слиянием;
• поразрядная обменная сортировка.

Сортировка обменом («пузырек»)

Принцип:

Слева направо поочередно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами.

Далее берутся два следующих соседних элемента и так далее до конца массива.

После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент (“всплыл” первый “пузырек”).

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

И так далее.

Всего требуется (n-1) проход.

my_ar [i+1] then begin B:=my_ar [i]; my_ar [i]:=my_ar [i+1]; my_ar [i+1]:=B; end; " width="640"

Сортировка обменом («пузырек»)

for k:=1 to n downto 2 do

{“Всплывание” очередного максимального элемента на k-ю позицию }

for i:=1 to k-1 do

If my_ar[i]my_ar [i+1] then

begin

B:=my_ar [i];

my_ar [i]:=my_ar [i+1];

my_ar [i+1]:=B;

end;

Двоичный поиск

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

Принцип двоичного поиска:

• Исходный массив делится пополам и для сравнения выбирается средний элемент.
• Если он совпадает с искомым, то поиск заканчивается.
• Если же средний элемент меньше искомого, то все элементы левее его также будут меньше искомого. Следовательно, их можно исключить из зоны дальнейшего поиска, оставив только правую часть массива.
• Аналогично, если средний элемент больше искомого, то отбрасывается правая часть, а левая остается.
• На втором этапе выполняются аналогичные действия над оставшейся половиной массива. В результате после второго этапа остается ¼ часть массива.
• И так далее, пока или элемент будет

найден, или длина зоны поиска станет

равной нулю. В последнем случае

искомый элемент найден не будет.

 

Двоичный поиск

L:=1;

R:=n;

T:=false;

While (L

begin

i:= (L+R) div 2;

if my_ar[i]=X then

begin

T:=true; {элемент найден}

k:=i;

end {then}

else

if my_ar [i]

L:=i+1

else

R:=i-1;

end; { While }

if T=true then

Writeln(‘Искомый элемент найден на позиции ‘,k:3)

else

Writeln(‘Искомый элемент не найден ‘);

Домашнее задание

• § 1.7.7 – читать, № 2 стр. 163