Сортування змішуванням

Сортування змішуванням (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)

Результат роботи програми:

Дивіться також: