Сортування по частинах

Сортування по частинах (Stooge sort) – рекурсивний алгоритм сортування масиву.

Опис алгоритму сортування по частинах

Алгоритм сортування stooge sort полягає в наступному:

  • Якщо значення останнього елемента масиву менше, ніж значення першого елемента, то міняємо їх місцями;
  • Якщо в масиві міститься три та більше елементи то:
    • Рекурсивно викликаємо метод для перших 2⁄3 елементів;
    • Рекурсивно викликаємо метод для останніх 2⁄3 елементів;
    • Знову рекурсивно викликаємо метод для перших 2⁄3 елементів.

Реалізація сортування по частинах

def stooge_sort(array, l, h): 
    if l >= h:
        return
 
    if array[l] > array[h]:
        array[l],array[h] = array[h],array[l]
  
    if h - l + 1 > 2:
        t = (int)((h - l + 1) / 3)
        # рекурсивний виклик для перших 2/3
        stooge_sort(array, l, h - t)
        # рекурсивний виклик для останніх 2/3
        stooge_sort(array, l + t, h)
        # рекурсивний виклик для перших 2/3
        stooge_sort(array, l, h - t)

print("Сортування по частинах")
array = []
length = int(input("Введіть довжину масиву: ")) 
for i in range(0, length): 
    element = int(input("arr[" + str(i + 1) + "] = "))   
    array.append(element)
stooge_sort(array, 0, len(array) - 1) 
print("Впорядкований масив: ") 
print(array)

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

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