Метод шейкерной сортировки (ShakerSort)
На этих наблюдениях основан метод шейкерной сортировки (ShakerSort). При его применении на каждом следующем шаге меняется направление последовательного просмотра. В результате на одном шаге "всплывает" очередной наиболее легкий элемент, а на другом "тонет" очередной самый тяжелый.
| Начальное состояние массива | 8 23 5 65 44 33 1 6 |
| Шаг 1 | 8 23 5 65 44 33 1 68 23 5 65 44 1 33 68 23 5 65 1 44 33 68 23 5 1 65 44 33 68 23 1 5 65 44 33 68 1 23 5 65 44 33 61 8 23 5 65 44 33 6 |
| Шаг 2 | 1 8 23 5 65 44 33 61 8 5 23 65 44 33 61 8 5 23 65 44 33 61 8 5 23 44 65 33 61 8 5 23 44 33 65 61 8 5 23 44 33 6 65 |
| Шаг 3 | 1 8 5 23 44 6 33 651 8 5 23 6 44 33 651 8 5 6 23 44 33 651 8 5 6 23 44 33 651 5 8 6 23 44 33 65 |
| Шаг 4 | 1 5 6 8 23 44 33 651 5 6 8 23 44 33 651 5 6 8 23 44 33 651 5 6 8 23 33 44 65 |
| Шаг 5 | 1 5 6 8 23 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 65 |
Шейкерная сортировка позволяет сократить число сравнений, хотя порядком оценки по-прежнему остается n2. Число же пересылок, вообще говоря, не меняется. Шейкерную сортировку рекомендуется использовать в тех случаях, когда известно, что массив "почти упорядочен".
ЛЕКЦИЯ 2. СОРТИРОВКА ВКЛЮЧЕНИЕМ
Цель лекции: изучить методы сортировки включением, сортировку методом Шелла, методы сортировки выбором.
Рассматриваемые вопросы: сортировка включением, сортировка методом Шелла, методы сортировкивыбором
Сортировка включением
Пусть имеется массив ключей a[1], a[2], ..., a[n]. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент a[i] последовательно сравнивается с элементами a[i-1], a[i-2] ...) и до тех пор, пока для очередного элемента a[j] выполняется соотношение a[j] > a[i], a[i] и a[j] меняются местами. Если удается встретить такой элемент a[j], что a[j] <= a[i], или если достигнута нижняя граница массива, производится переход к обработке элемента a[i+1] (пока не будет достигнута верхняя граница массива).
|
|
|
Легко видеть, что в лучшем случае (когда массив уже упорядочен) для выполнения алгоритма с массивом из n элементов потребуется n-1 сравнение и 0 пересылок. В худшем случае (когда массив упорядочен в обратном порядке) потребуется n(n-1)/2 сравнений и столько же пересылок. Таким образом, можно оценивать сложность метода простых включений как O(n2).
Можно сократить число сравнений, применяемых в методе простых включений, если воспользоваться тем фактом, что при обработке элемента a[i] массива элементы a[1], a[2], ..., a[i-1] уже упорядочены, и воспользоваться для поиска элемента, с которым должна быть произведена перестановка, методом двоичного деления. В этом случае оценка числа требуемых сравнений становится O(nlog n). Заметим, что поскольку при выполнении перестановки требуется сдвижка на один элемент нескольких элементов, то оценка числа пересылок остается O(n2).
|
|
|
| Таблица 2.1 Пример сортировки методом простого включения | |
| Начальное состояние массива | 8 23 5 65 44 33 1 6 |
| Шаг 1 | 8 23 5 65 44 33 1 6 |
| Шаг 2 | 8 5 23 65 44 33 1 65 8 23 65 44 33 1 6 |
| Шаг 3 | 5 8 23 65 44 33 1 6 |
| Шаг 4 | 5 8 23 44 65 33 1 6 |
| Шаг 5 | 5 8 23 44 33 65 1 65 8 23 33 44 65 1 6 |
| Шаг 6 | 5 8 23 33 44 1 65 65 8 23 33 1 44 65 65 8 23 1 33 44 65 65 8 1 23 33 44 65 65 1 8 23 33 44 65 61 5 8 23 33 44 65 6 |
| Шаг 7 | 1 5 8 23 33 44 6 651 5 8 23 33 6 44 651 5 8 23 6 33 44 651 5 8 6 23 33 44 651 5 6 8 23 33 44 65 |
Cортировка методом Шелла
Дальнейшим развитием метода сортировки с включениями является сортировка методом Шелла, называемая по-другому сортировкой включениями с уменьшающимся расстоянием. Мы не будем описывать алгоритм в общем виде, а ограничимся случаем, когда число элементов в сортируемом массиве является степенью числа 2. Для массива с 2n элементами алгоритм работает следующим образом. На первой фазе производится сортировка включением всех пар элементов массива, расстояние между которыми есть 2(n-1). На второй фазе производится сортировка включением элементов полученного массива, расстояние между которыми есть 2(n-2). И так далее, пока не дойдем до фазы с расстоянием между элементами, равным единице, и не выполним завершающую сортировку с включениями.
| Начальное состояние массива | 8 23 5 65 44 33 1 6 |
| Фаза 1 (сортируются элементы, расстояние между которыми четыре) | 8 23 5 65 44 33 1 68 23 5 65 44 33 1 68 23 1 65 44 33 5 68 23 1 6 44 33 5 65 |
| Фаза 2 (сортируются элементы, расстояние между которыми два) | 1 23 8 6 44 33 5 651 23 8 6 44 33 5 651 23 8 6 5 33 44 651 23 5 6 8 33 44 651 6 5 23 8 33 44 651 6 5 23 8 33 44 651 6 5 23 8 33 44 65 |
| Фаза 3 (сортируются элементы, расстояние между которыми один) | 1 6 5 23 8 33 44 651 5 6 23 8 33 44 651 5 6 23 8 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 65 |
В общем случае алгоритм Шелла естественно переформулируется для заданной последовательности из t расстояний между элементами h1, h2, ..., ht, для которых выполняются условия h1 = 1 и h(i+1) < hi. При правильно подобранных t и h сложность алгоритма Шелла является O(n(1.2)), что существенно меньше сложности простых алгоритмов сортировки.
|
|
|
Сортировка выбором
При сортировке массива a[1], a[2], ..., a[n] методом простого выбора среди всех элементов находится элемент с наименьшим значением a[i], и a[1] и a[i] обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a[2], a[3], ..., a[n], ... a[j], a[j+1], ..., a[n] до тех пор, пока мы не дойдем до подмассива a[n], содержащего к этому моменту наибольшее значение.
| Начальное состояние массива | 8 23 5 65 44 33 1 6 |
| Шаг 1 | 1 23 5 65 44 33 8 6 |
| Шаг 2 | 1 5 23 65 44 33 8 6 |
| Шаг 3 | 1 5 6 65 44 33 8 23 |
| Шаг 4 | 1 5 6 8 44 33 65 23 |
| Шаг 5 | 1 5 6 8 33 44 65 23 |
| Шаг 6 | 1 5 6 8 23 44 65 33 |
| Шаг 7 | 1 5 6 8 23 33 65 44 |
| Шаг 8 | 1 5 6 8 23 33 44 65 |
Для метода сортировки простым выбором требуемое число сравнений - n(n-1)/2. Порядок требуемого числа пересылок (включая те, которые требуются для выбора минимального элемента) в худшем случае составляет O(n2). Однако порядок среднего числа пересылок есть O(nln n), что в ряде случаев делает этот метод предпочтительным.
|
|
|
Улучшенный выбор заключается в том, что за один проход отыскивается минимальный и максимальный элемент, которые соответственно меняются с первым и последним элементом массива, затем границы массива сдвигаются влево и вправо на один элемент, и т.д.
| Начальное состояние массива | 8 23 5 65 44 33 1 6 |
| Шаг 1 | 1 23 5 6 44 33 8 65 |
| Шаг 2 | 1 5 23 6 8 33 44 65 |
| Шаг 3 | 1 5 6 23 8 33 44 65 |
| Шаг 4 | 1 5 6 8 23 33 44 65 |
Дата добавления: 2018-05-02; просмотров: 898; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!