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

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

Например: Дан массив, состоящий из элементов:

44 55 12 42 94 18 06 67

После четверной сортировки получаем:

44 18 06 42 94 55 12 67

Т. е. элементы, отстоящие на 4 позиции друг от друга сравниваются и меняются местами в случае необходимости (44<94, 55>18 значит меняем местами, 12>06 тоже меняем местами, 42<67).

После двойной сортировки получаем:

06 18 12 42 44 55 94 67

Теперь сравниваем элементы, отстоящие на 2 позиции (44>06 - меняем, 94>12 - меняем, 44>12 - меняем и т. д.)

После одинарной сортировки получаем:

06 12 18 42 44 55 67 94

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

Ясно, что такой метод в результате дает упорядоченный массив, и, конечно же, сразу видно, что каждый проход от предыдущих только выигрывает (так как каждая i-сортировка объединяет две группы, уже отсортированные 2i-сортировкой). Так же очевидно, что расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу. Все t расстояния обозначаются соответственно h1,h2,...,ht, для них выполняются условия

ht=1, hi+1<hi

Каждая h-сортировка программируется как сортировка с помощью прямого включения. Причем простота условия окончания поиска места для включения обеспечивается методом барьеров. Ясно, что каждая из сортировок нуждается в постановке своего собственного барьера и программу для определения его местоположения необходимо делать насколько возможно простой. Поэтому приходится расширять массив не только на одну-единственную компоненту a0, а на h1 компонент. 

h[1..4] – переменные, которые определяют расстояния между элементами, которые будут сравниваться и меняться местами, если это требуется,  при М проходе. S – индекс массива буфера элементов. Внутренний цикл является сортировкой простых вставок

начало h[1] := 9; h[2] := 5; h[3] := 3; h[4] := 1; Для m от 1 до T делать начало k := h[m]; s := - k;        Для i от k + 1 до n делать        начало        x := a[i];        j := i - k;        Если  s = 0 то s := - k;        s := s + 1;        a[s] := x;        Пока x < a[j] делать        начало                a[j+k] := a[j];                j:= j - k;        конец ;        a[j+k] := x;        конец; конец; конец

Оценки эффективности алгоритмов сортировки

Алгоритм	Количество сравнений С	Количество пересылок
min	avg	max	min	avg	max
Прямые вставки	n-1	(N2+N-4)/4	(N2+N-4)/4	3*(N-1)	(N2+N-3)/4	(N2+3*N-4)/2
N=10	9	26.5	26.75	27	47.5
Анализ метода прямого включения. Число сравнений (С) при i-м просеивании самое большее равно i-1, самое меньшее - 1. Число присваиваний элементов (М) равно Ci+2 (включая барьер). Поэтому общее число сравнений и число присваиваний: Cmin=n-1                        Mmin=3(n-1) Cmax=(n2+n-4)/4                Mmax=(n2+3n-4)/2 А число передвижений М продолжает оставаться порядка n2.
Алгоритм	Количество сравнений С	Количество пересылок M
min	avg	max	min	avg	Max
Простой выбор	Ѕ(N2 –N)	Ѕ(N2 –N)	Ѕ(N2 –N)	3*(N-1)	N*(Ln(N)+0.557)	n2/4 +3(n-1)
N=10	45	45	45	27	28.6	52
Анализ прямого выбора. Недостаток сортировки выбором заключается в том, что время ее выполнения в малой степени зависит от того, насколько упорядочен исходный файл. Процесс нахождения минимального элемента за один проход массива дает очень мало сведений о том, где может находиться минимальный элемент на следующем проходе этого массива. Пользователь будет немало удивлен, когда узнает, что на сортировку Число сравнений ключей (С), очевидно, не зависит от начального порядка ключей. Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения. Для С имеем с = (n2 - n)/2 Число перестановок минимально Mmin=3*(n-l) в случае изначально упорядоченных ключей Число перестановок максимальноMmax = n2/4 +3(n-1), если первоначально ключи располагались в обратном порядке. Приблизительное значение Mavg = n(ln (n) + g) Отсюда можно сделать заключение, что, как правило, алгоритм с прямым выбором предпочтительнее строгого включения. Однако, если ключи в начале упорядочены или почти упорядочены, прямое включение будет оставаться несколько более быстрым
Алгоритм	Количество сравнений С	Количество пересылок
min	avg	max	min	avg	Max
Метод Шелла	N1.5
N=10	31.5
Анализ сортировки Шелла Анализ этого алгоритма поставил несколько проблем. Не известно, какие расстояния дают наилучшие результаты. Д. Кнут в работе "Искусство программирования для ЭВМ" показывает, что имеет смысл использовать такую последовательность ( записана в обратном порядке): 1, 4, 13, 40, 121, ... или 1, 3, 7, 15, 31, ... Математический анализ показывает, что в последнем случае для сортировки n элементов методом Шелла затраты пропорциональны n1.2.
Алгоритм	Количество сравнений С	Количество пересылок M
Метод Хоара	Общее число N*Lg(N)	Общее число 1/6*N*Lg(N)
N=10	33	5.5
Анализ Quicksort. Для исследования производительности Quicksort сначала необходимо разобраться, как идет процесс разделения. Выбрав некоторое граничное значение x, мы затем проходим целиком по всему массиву. Следовательно, при этом выполняется точно n сравнений. Число же обменов можно определить из следующих вероятностных соображений. При заданной границе значений x ожидаемое число операций обмена равно числу элементов в левой части разделяемой последовательности, т. е. n-1, умноженному на вероятность того, что при обмене каждый такой элемент попадает на свое место. Обмен происходит, если этот элемент перед этим находился в правой части. Вероятность этого равна (n-(x-1))/n. Поэтому ожидаемое число обменов есть среднее этих ожидаемых значений для всех возможных границ x. m = [Sx:1 <= x <= n:(x-1)*(n-(x-1))/n]/n = [Su: 1<= x <= n-1:u*(n-u)]/n2 = [n*(n-1)/2n-(2n2-3n+1)/6n = (n-1/n)/6 Представим себе, что нам всегда удается выбрать в качестве границы медиану, в этом случае каждый процесс разделения расщепляет массив на две половины и для сортировки требуется всего log2nпроходов. В результате общее число сравнений равно n*log2n, а общее число обменов - n*log2(n)/6. Средняя производительность Quicksort при случайном выборе границы отличается от упомянутого оптимального варианта лишь коэффициентом 2*ln(2). Как бы то ни было, но Quicksort присущи и некоторые недостатки. Главный из них - недостаточно высокая производительность при небольших n.

Поиск

Алгоритм поиска методом последовательного перебора

Последовательный поиск: проверяет, находится ли искомое число среди элементов массива а[1..n] путем последовательного сравнения с каждым элементом, начиная сначала.

Лемма. Последовательный поиск исследует N чисел при каждом неуспешном поиске и в среднем N/2 чисел при каждом успешном поиске.

Лемма. Алгоритм последовательного поиска в упорядоченной таблице проверяет N чисел для каждого поиска в худшем случае и порядка N/2 чисел в среднем.

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

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