Шейкерная сортировка.
Теоретические основы информатики
Шейкерная сортировка (англ, cocktail sort) является модификацией пузырьковой. Улучшить работу последней можно исходя из следующих соображений: Пример 11.6. Применяя алгоритм шейкерной сортировки, упорядочить множество чи сел, А = {9,3,12,1,8,5} по возрастанию. Рассмотренный алгоритм имеет альтернативные названия: сортировка перемешиванием, челночная сортировка. Пузырьковая сортировка. Шейкерная… Читать ещё >
Шейкерная сортировка. Теоретические основы информатики (реферат, курсовая, диплом, контрольная)
Шейкерная сортировка (англ, cocktail sort) является модификацией пузырьковой. Улучшить работу последней можно исходя из следующих соображений:
- 1. Если при некотором проходе не было выполнено ни одной перестановки, то множество А является упорядоченным. Это условие также называют условием Айверсона. При его выполнении алгоритм завершает работу. В примере предыдущего параграфа такая ситуация наступает после четвертого прохода, в течение которого не было сделано ни одной перестановки.
- 2. Пусть на г-м проходе последняя перестановка выполнялась для элементов ai и ai+1, где L + 1 < п — г 4−1. Тогда, начиная с (L-hl)-ro элемента, элементы можно не сравнивать. Другими словами, если на текущем проходе последняя перестановка была выполнена для а^ и йд+ь то на следующем проходе сравнение выполняется для первых L элементов.
- 3. Для проходов с нечетными номерами множество А можно просматривать слева направо, а для четных — справа налево. При этом наименьший элемент окажется в начале и будет уже отсортированным. Если запомнить номер элемента Я последней перестановки ап и а а- для четного прохода, то на следующем нечетном просматриваются элементы не с первого, а начиная с номера Я.
Пузырьковая сортировка
Состояние | Номер прохода | Сравнение | Действие |
?So = {9,3,12,1,8,5} | 9 и 3 | Перестановка 9 и 3 | |
Si = {3,9,12,1,8,5} | 9 и 12 | ||
s2 = {3,9,12,1,8,5} | 12 и 1 | Перестановка 12 и 1 | |
s3 = {3,9,1.12.8,5} | 12 и 8 | Перестановка 12 и 8 | |
s4 = {3,9,1,8,12,5} | 12 и 5 | Перестановка 12 и 5 | |
s5 = {3,9,1,8,5,12} | 3 и 9 | ||
s6 = {3,9,1,8,5,12} | 9 и 1 | Перестановка 9 и 1 | |
s7 = {3,1,9,8,5,12} | 9 и 8 | Перестановка 9 и 8 | |
s8 = {3,1,8,9,5,12} | 9 и 5 | Перестановка 9 и 5 | |
•s9 = {3,1,8,9,5,12} | 5 и 12 | ||
sio = {3,1,8,5,9712} | 3 и 1 | Перестановка 3 и 1 | |
sn = {1,3,8,5,9712} | 3 и 8 | ||
S12 = {1,3.8,5,9712} | 8 и 5 | Перестановка 8 и 5 | |
si3 = {1,3,8,5,9712} | 5 и 9 | ||
su = {1,3,8,5,9712} | 9 и 12 | ||
s15 = {1,3,5,8,9,12} | 1 и 3 | ||
Si6 = {1,3,5,8,9,12} | 3 и 5 | ||
Si7 = {1,3,5,8,9,12} | 5 и 8 | ||
sis = {1,3,5,8,9.12} | 8 и 9 | ||
s, 9 = {1,3,5,8,9,12} | 9 и 12 | ||
s20 = {1,3,5,8,9,12} | 1 и 3 | ||
S21 = {1,3,5,8,9.12} | 3 и 5 | ||
s22 = {1,3.5,8,9.12} | 5 и 8 | ||
s23 = {1,3.5,8,9.12} | 8 и 9 | ||
s24 = {1,3,5,8,9,12} | 9 и 12 |
Таким образом, при использовании чередующихся проходов слева направо и справа налево формируются левая и правая границы сравниваемых элементов L и R соответственно.
Пример 11.6. Применяя алгоритм шейкерной сортировки, упорядочить множество чи сел А = {9,3,12,1,8,5} по возрастанию.
Решение. В табл. 11.5 приведены состояния множества А при шейкерной сортировке. Величины L и R изменяются после выполнения действий в соответствующей строке (например, значение L будет изменено на 2 после перестановки 12 и 5). Вертикальной чертой сверху помечены элементы, находящиеся на своих местах в упорядоченной части множества.
Шейкерная сортировка
Таблица 11.5
Состояние. | Номер прохода. | Сравнение. | Действие. | L | R |
So = {9,3,12,1.8,5}. | 9 и 3. | Перестановка 9 и 3. | |||
sj = {3,9,12,1.8,5}. | 9 и 12. | —. | |||
s2 = {3,9,12,1.8,5}. | 12 и 1. | Перестановка 12 и 1. | |||
s3 = {3,9,1.12.8,5}. | 12 и 8. | Перестановка 12 и 8. | |||
s4 = {3,9,1,8,12,5}. | 12 и 5. | Перестановка 12 и 5. | |||
s5 = {3,9,1,8,5,12}. | 5 и 8. | Перестановка 5 и 8. | |||
s6 = {3,9,1,5,8,12}. | 5 и 1. | ||||
s7 = {3,9,1,5,8,12}. | 1 и 9. | Перестановка 1 и 9. | |||
s" = {3,1,9,5,8,12}. | 1 и 3. | Перестановка 1 и 3. | |||
s9 = {1,3,9,5,8,12}. | 3 и 9. | —. | |||
s10 = {1,3.9,5,8,12}. | 9 и 5. | Перестановка 9 и 5. | |||
sn = {1,3,5,9,8,12}. | 9 и 8. | Перестановка 9 и 8. | |||
s12 = {1,3,5,8,9,12}. | 8 и 5. | —. | |||
*u = {1,3,5,8,9,12}. | 5 и 3. | —. |
На последнем проходе справа налево выполнилось условие Айверсона, поэтому множество считается упорядоченным и алгоритм прекращает свою работу. ?
Шейкерная сортировка имеет, в общем случае, сложность порядка 0(п2), хотя количество сравнений на практике оказывается все же меньше, чем для пузырьковой.
Рассмотренный алгоритм имеет альтернативные названия: сортировка перемешиванием, челночная сортировка.