Сортування змішуванням (cocktail sort, shaker sort), або шейкерне сортування – це вдосконалений різновид сортування бульбашкою, при якому сортування проводиться у двох напрямках, змінюючи напрям при кожному проході.
Опис алгоритму шейкерного сортування
Аналізуючи алгоритм сортування бульбашкою, можна помітити:
- якщо при обході частини масиву не відбувається обмін елементів, то цю область можна виключити, так як вона вже відсортована;
- при проходженні від кінця масиву до початку, мінімальне значення переміщається на першу позицію, при цьому максимальний елемент зміщується тільки на один індекс вправо.
Виходячи з наведених ідей, модифікуємо сортування бульбашкою наступним чином:
- на кожній ітерації, фіксуємо межі області масиву в якій відбувається обмін;
- пробігаємо масив по черзі від початку до кінця, та від кінця до початку.
Таким чином, ми переміщуємо мінімальний елемент на початок масиву, а максимальний - в кінець, після чого, зменшуємо робочу область масиву.
Реалізація сортування змішуванням
def shaker_sort(array):
length = len(array)
swapped = True
start_index = 0
end_index = length - 1
while (swapped == True):
swapped = False
# прохід зліва направо
for i in range(start_index, end_index):
if (array[i] > array[i + 1]) :
# обмін елементів
array[i], array[i + 1] = array[i + 1], array[i]
swapped = True
# якщо обміну не було, перериваемо цикл
if (not(swapped)):
break
swapped = False
end_index = end_index - 1
# прохід справа на ліво
for i in range(end_index - 1, start_index - 1, -1):
if (array[i] > array[i + 1]):
# обмін елементів
array[i], array[i + 1] = array[i + 1], array[i]
swapped = True
start_index = start_index + 1
print("Сортування змішуванням")
arr = []
length = int(input("Введіть довжину масиву: "))
for i in range(0, length):
element = int(input("arr[" + str(i + 1) + "] = "))
arr.append(element)
shaker_sort(arr)
print("Відсортований масив: ")
print(arr)
Результат роботи програми: