Сортировка по частям

Сортировка по частям (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)

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

Смотрите также: