Сортировка с помощью включений с уменьшающимися расстояниями (Сортировка Шелла)

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

Его суть: сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на n/2 (n – количество элементов массива). Каждая группа состоит из 2 элементов. Если n/2=4, такой процесс называется четвертной сортировкой. После первого прохода элементы перегруппировываются – теперь каждый элемент группы отстоит от другого на n/4 позиции – и вновь сортируются. Если n/4=2 то этот процесс называется двойной сортировкой. Процесс завершается проходом, во время которого сортируются все n записей.

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

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

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

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

Дата добавления: 2015-07-16