Рубрики

Программа Python для итеративной быстрой сортировки

# Python программа для реализации Quicksort

  
# Эта функция одинакова как в итеративной, так и в рекурсивной

def partition(arr,l,h):

    i = ( l - 1 )

    x = arr[h]

  

    for j in range(l , h):

        if   arr[j] <= x:

  

            # индекс приращения меньшего элемента

            i = i+1

            arr[i],arr[j] = arr[j],arr[i]

  

    arr[i+1],arr[h] = arr[h],arr[i+1]

    return (i+1)

  
# Функция для быстрой сортировки
# arr [] -> Массив для сортировки,
# l -> Начальный индекс,
# h -> Конечный индекс

def quickSortIterative(arr,l,h):

  

    # Создать вспомогательный стек

    size = h - l + 1

    stack = [0] * (size)

  

    # инициализировать вершину стека

    top = -1

  

    # поместите начальные значения l и h в стек

    top = top + 1

    stack[top] = l

    top = top + 1

    stack[top] = h

  

    # Продолжайте выскакивать из стека, пока не пусто

    while top >= 0:

  

        # Поп ч и л

        h = stack[top]

        top = top - 1

        l = stack[top]

        top = top - 1

  

        # Установите элемент поворота в правильное положение в

        # отсортированный массив

        p = partition( arr, l, h )

  

        # Если есть элементы на левой стороне оси,

        # затем нажмите левую сторону, чтобы сложить

        if p-1 > l:

            top = top + 1

            stack[top] = l

            top = top + 1

            stack[top] = p - 1

  

        # Если есть элементы на правой стороне оси,

        # затем нажмите правую сторону, чтобы сложить

        if p+1 < h:

            top = top + 1

            stack[top] = p + 1

            top = top + 1

            stack[top] = h

  
# Код драйвера для проверки выше

arr = [4, 3, 5, 2, 1, 3, 2, 3]

n = len(arr)

quickSortIterative(arr, 0, n-1)

print ("Sorted array is:")

for i in range(n):

    print ("%d" %arr[i]),

  
# Этот код предоставлен Мохитом Кумрой

Выход:

Sorted array is:
1 2 2 3 3 3 4 5

Вышеупомянутые оптимизации для быстрой рекурсивной сортировки также могут быть применены к итерационной версии.

1) Процесс разбиения одинаков как в рекурсивном, так и итеративном. Те же методы для выбора оптимального центра также могут быть применены к итерационной версии.

2) Чтобы уменьшить размер стека, сначала нажмите индексы меньшей половины.

3) Используйте сортировку вставки, когда размер уменьшается ниже экспериментально рассчитанного порога.
Пожалуйста, обратитесь к полной статье об итеративной быстрой сортировке для более подробной информации!

Рекомендуемые посты:

Программа Python для итеративной быстрой сортировки

0.00 (0%) 0 votes