Алгоритмы сортировки массивов: метод выбора, метод вставки, метод быстрой сортировки Хоара, метод Шелла. Поиск в массиве (стр. 1 )

Алгоритмы сортировки массивов: метод выбора, метод вставки, метод быстрой сортировки Хоара, метод Шелла. Поиск в массиве

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

Под сортировкой обычно понимают процесс перестановки объектов данного множества в определенном порядке.

Цель сортировки – облегчение последующего поиска элементов в отсортированном множестве.

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

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

Существует  большое разнообразие алгоритмов сортировки, но в зависимости от ПЗ выбирается тот или иной алгоритм. Эффективность сортировок рассматривается по критериям

по использованию памяти;

по быстродействию.

Хорошей мерой эффективности может быть:

С – число необходимых сравнений; М – число пересылок (перестановок) элементов. Оно зависит от числа элементов массива.

Хорошие алгоритмы сортировок требуют порядка n*Log(n) сравнений.

Элементы массива можно сортировать:

• по возрастанию - каждый следующий элемент больше предыдущего - А[1] <А[2] < ... < A[N];

• по неубыванию - каждый следующий элемент не меньше предыдущего - А[1] <= А[2] <= ...<= A[N];

• по убыванию - каждый следующий элемент меньше предыдущего - А[1] > А [2] > ... > A[N];

• по невозрастанию - каждый следующий элемент не больше предыдущего А[1]>= А[2] >=...>=A[N].

Наиболее часто используются следующие алгоритмы: метод пузырька, метод прямого выбора, метод простых вставок (включений),  метод Шелла, метод Хоара. Большинство остальных алгоритмов являются различными модификациями вышеперечисленных алгоритмов.

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

Методы сортировки "на том же месте" можно разбить на три основные категории:

сортировки с помощью включения; сортировки с помощью выделения; сортировки с помощью обменов.

Метод простых вставок

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

Алгоритм: элементы массива мысленно делятся на уже "готовую" и исходную последовательности. При каждом шаге, начиная с i=2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.

В процессе поиска подходящего места для элемента х удобно, чередуя сравнения и движения по последовательности, как бы просеивать х, т. е. х сравнивается с очередным элементом aj, а затем либо х вставляется на свободное место, либо aj сдвигается вправо и процесс "уходит" влево.

Процесс просеивания может закончиться при выполнении одного из двух условий:

- найден элемент aj с ключом, меньшим чем ключ у х; - достигнут левый конец готовой последовательности.

Повторяющийся процесс с двумя условиями окончания позволяет воспользоваться приемом "барьера", поставив барьер a0 со значением х.

Итак, алгоритм сортировки:

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

-Найти место вставки

-Сдвинуть часть данных

a0 - ячейка-барьер. Используется для того, чтобы остановить поиск

Имеется числовой массив а[0..N]

i-порядковый n элемента, который будет вставляться, будет меняться от 2 до n

j - граница упорядоченной части, будет меняться от (i-1) до 0 с шагом (-1)}

Реализация алгоритма

Для i от 2 до N Нц запоминаем вставляемый элемент вставляем его в барьер. Барьер  - лишняя ячейка памяти, которая позволяет ускорить сортировку Пока x<a[j] не найдено место для вставки, ищем его Вставляем элемент	Для i от 2 до N Нц        x:=a[i];        a[0]:=x;        j:=i-1;        Пока x<a[j]        Нц                a[j+1]:=a[j];                j:=j-1;        Кц        a[j+1]:=x; Кц;	For i:= 2 to N начало        x:=a[i];        a[0]:=x;        j:=i-1;        While x<a[j]        начало                a[j+1]:=a[j];                j:=j-1;        конец;        a[j+1]:=x; Конец;

Ручное тестирование сортировки массива методом простых вставок

54321	I	x=a[I]	a0]=x	J=I-1	x<a[j]	A[j+1]=a[j]	J:=j-1	A[j+1]=x
2	4	4	1	4<5 +	A[2]=5	0
4<4 -	-	-	A[1]=4	45321
45321	3	3	3	2	3<5+	A[3]=5	J=1
3<4+	A[2]=4	J=0
3<3 -	-	-	A[1]=3	34521
34521	4	2	2	3	2<5+	A[4]=5	J=2
2<4+	A[3]=4	J=1
2<3 +	A[2]=3	J=0	A[1]=2	23451
23451	5	1	1	4	1<5+	A[5]=5	J=3
1<4+	A[4]=4	J=2
1<3+	A[3]=2	J=1
1<2+	A[2]=1	J=0
1<1-	-	-	A[1]=1	12345

Метод прямого выбора

Один из самых простых алгоритмов сортировки работает следующим образом.

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

Далее находится второй наименьший элемент и меняется местами с элементом, стоящим вторым в исходном массиве.

Этот процесс продолжается до тех пор, пока весь массив не будет отсортирован.

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

Данный метод основан на следующих принципах:

1. Выбирается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом a[i].

3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т. д. до тех пор, пока не останется один, самый большой элемент.

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

Псевдокод
Внешний цикл: Для выбираем текущий элемент x и запоминаем его порядковый номер k; Внутренний цикл: В части массива ищем минимальный элемент x и запоминаем его порядковый номер k; Внешний цикл: Меняем местами текущий элемент а[i] с минимальным элементом х.	Начало Для I от 1 до n-1 делать нц k:= i; x := a[i]; Для j от  (i+1) до n делать нц Если a[j]<x  то начало k:=j; X:= a[k];                все кц; а[k] := а[i]; a[i] ; = x; кц; Конец

Быстрая сортировка (метод Хоара).  Рекурсивный алгоритм быстрой сортировки.

Метод Хoаpа - метод, называемый также быстрой сортировкой(QuickSort), был Разработан в1962 г. Его разработал Charles Antony Richard Hoare. Суть метода заключается в том, чтобы найти такой элемент множества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его. В общем случае его эффективность достаточно высока, поэтому автор назвал его "быстрой сортировкой". Число перестановок в ней - m = lg(N).