Как работает разделение Хоара в QuickSort

Question

Я написал код Python алгоритма быстрой сортировки, но не совсем знаю, как он обрабатывает массив или список.

Я знаю, что алгоритм всегда берет крайний левый элемент в качестве точки поворота. К тому же я вручную реализую алгоритм, но что-то запуталось. Вот вопрос:

1. Возвращает j если i >= j, а что если i < j? В таком случае, как мне узнать возвращаемое значение? Это j? Или нужно вернуть другое значение?
2. Как узнать, отсортировано ли?

Любая помощь приветствуется.

Вот код:

def quick_sort(arr, low, high):
if low < high:
    pivot = partition(arr, low, high)
    quick_sort(arr, low, pivot)
    quick_sort(arr, pivot + 1, high)
return arr

def partition(arr, low, high):
    pivot = arr[low]
    i = low - 1
    j = high + 1
    while (True):
        while (True):
            i = i + 1
            if (arr[i] >= pivot):
                break        
        while (True):
            j = j - 1
            if (arr[j] <= pivot):
                break       
        if (i >= j):
            return j

    swap(arr, i, j)




arr = [2, 4, 1, 6]
quick_sort(arr, 0, len(arr) - 1)

Answer 1

Каждый раз, когда функция partition возвращает опорную точку, то есть pivot = arr[low]. Впервые он возвращает первый элемент в качестве точки поворота.

После этого алгоритм разделяет его на две части.

1. Один - quick_sort(arr, low, pivot), левая часть array.
2. Другой - quick_sort(arr, pivot + 1, high), правая часть массива.

Правая часть массива будет отправлена ​​обратно в рекурсию. Выполнение partition снова и на этот раз передайте arr[low] = pivot = 1.

Этот алгоритм завершается, когда он передает последнюю «правую» часть массива, которая является только элементом с правой стороны, запускает if low < high состояние. Когда это условие не выполняется, алгоритм возвращает весь массив.