Почему моя попытка быстрой сортировки не выполняется должным образом?

Question

Я усердно работал над созданием «простого» алгоритма быстрой сортировки, так как многие онлайн-примеры написаны более сложно, чем, возможно, требуется для демонстрации механики алгоритма.

У меня естьдобрался до точки, где я не могу понять, почему окончательный список не сортируется должным образом. Я был бы признателен за набор свежих глаз и указатель в правильном направлении, чтобы закончить код.

Вот мой текущий код:

def qsort(dataset):

    if len(dataset) < 2:
        return (dataset)
    else:
        point1 = 0
        point2 = len(dataset) - 1
        pivot = (len(dataset) - 1 ) // 2

        while point1 != pivot and point2 != pivot:

            while dataset[point1] <= dataset[pivot] and point1 != pivot:
                point1 = point1 + 1
            while dataset[point2] >= dataset[pivot] and point2 != pivot:
                point2 = point2 - 1
            x = dataset[point1]
            dataset[point1] = dataset[point2]
            dataset[point2] = x


        left = qsort(dataset[0:pivot])
        right = qsort(dataset[(pivot+1):len(dataset)])

        return left + [dataset[pivot]] + right

dataset = [45, 29, 56, 23, 55, 27, 43, 46]

print(qsort(dataset))

Любая помощь будет принята с благодарностью.

**** РЕДАКТИРОВАТЬ **** новый код после предложения @Marko Mahnič, но по-прежнему неправильно сортировать. Я был бы очень благодарен за любую дополнительную помощь, которая может быть предложена.

def qsort(dataset):

    if len(dataset) < 2:
        return (dataset)
    else:
        point1 = 0
        point2 = len(dataset) - 1
        pivot = (len(dataset) - 1 ) // 2

        while point1 < point2:

            while dataset[point1] <= dataset[pivot] and point1 < point2:
                point1 = point1 + 1
            while dataset[point2] >= dataset[pivot] and point2 > point1:
                point2 = point2 - 1
            x = dataset[point1]
            dataset[point1] = dataset[point2]
            dataset[point2] = x


        left = qsort(dataset[0:pivot])
        right = qsort(dataset[(pivot+1):len(dataset)])

        return left + [dataset[pivot]] + right

dataset = [45, 29, 56, 23, 55, 27, 43, 46]

print(qsort(dataset))

Answer 1

Быстрая сортировка

обычно является сортировкой на месте, она сортирует исходный массив, а не возвращает отсортированную копию исходного массива. Пример кода вопроса - это разновидность быстрой сортировки раздела Hoare. Раздел Hoare разбивает раздел на элементы <= pivot и elements> = pivot. Элементы == для поворота и / или поворота могут закончиться где угодно, но это не проблема, и нет необходимости отслеживать, где заканчивается разворот. Время выполнения, как правило, будет меньше, если есть дубликаты.

Пример стандартной быстрой сортировки с методом разбиения Хоара

def qsort(a, lo, hi):
    if(lo >= hi):
        return
    p = a[(lo + hi) / 2]        # pivot, any a[] except a[hi]
    i = lo - 1
    j = hi + 1
    while(1):
        while(1):               # while(a[++i] < p)
            i += 1
            if(a[i] >= p):
                break
        while(1):               # while(a[--j] < p)
            j -= 1
            if(a[j] <= p):
                break
        if(i >= j):
            break
        a[i],a[j] = a[j],a[i]
    qsort(a, lo, j)
    qsort(a, j+1, hi)

dataset = [45, 29, 56, 23, 55, 27, 43, 46]
qsort(dataset, 0, len(dataset)-1)   # last param is len-1
print(dataset)

Answer 2

Вот итерационная версия вашего алгоритма. Он использует стек для устранения необходимости рекурсивных вызовов. Использование последнего элемента в качестве сводного элемента также упрощает его:

def qsort(dataset):
    low = 0
    high = len(dataset) - 1

    # stack tio use instead of the stack of recursive function calls
    stack = [0] * len(dataset)
    top = -1

    # stack initial values
    top += 1
    stack[top] = low
    top += 1
    stack[top] = high

    # while the stack is not empty
    while top >= 0:

        # pop high and low
        high = stack[top]
        top -= 1
        low = stack[top]
        top -= 1

        # partition by the pivot
        i = low - 1
        x = dataset[high]   # using the last element as pivot
        for j in range(low, high):
            if dataset[j] <= x:
                # increment index of smaller element
                i += 1
                dataset[i], dataset[j] = dataset[j], dataset[i]
        dataset[i + 1], dataset[high] = dataset[high], dataset[i + 1]
        p = i + 1   # updates the pivot position

        # If there are elements on left side of pivot,
        # then push left side to stack
        if p - 1 > low:
            top += 1
            stack[top] = low
            top += 1
            stack[top] = p - 1

        # If there are elements on right side of pivot,
        # then push right side to stack
        if p + 1 < high:
            top += 1
            stack[top] = p + 1
            top += 1
            stack[top] = high

    return dataset

dataset = [45, 29, 56, 23, 55, 27, 43, 46]

print(qsort(dataset))

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

Answer 3

Условия должны быть point1 < point2, а не pointX != pivot. Разделение на левый и правый должно быть в том месте, где встречаются точки 1 и 2.

Обратите внимание, что в qsort важная часть сводки - это ее значение, а не индекс. Вы можете выбрать значение любого элемента из dataset в качестве оси. Когда разделение будет выполнено, элементы слева от pivot2 будут меньше или равны значению сводки, а элементы справа от pivot1 будут выше или равны значению сводки.

Вы можете настроить pivot1 и pivot2 перед рекурсивным вызовом, чтобы массив left содержал только элементы, меньшие, чем сводка, массив middle содержал элементы со значением сводки иМассив right содержит элементы, превышающие значение пивота. Это небольшая оптимизация. В результате получается left + middle + right. Это особенно полезно, когда dataset имеет дублированные элементы.

Эти изменения сделают ваш алгоритм правильным, но не оптимальным. Проблема заключается в том, что алгоритм создает копии частей исходного списка, который требует O(n^2) дополнительного пространства, что составляет (n-1)*(n-2)/2 в худшем случае, когда он выбирает самое высокое или самое низкое значение в качестве сводной. Таким образом, вместо сортировки полных списков, алгоритм должен быть изменен для сортировки части списка на месте. Его интерфейс должен быть изменен на:

def qsort( a, left, right ):

, а рекурсивные вызовы должны быть:

qsort( a, left, pivot2 )
qsort( a, pivot1, right )

Другая оптимизация заключается в сокращении количества рекурсивных вызовов, поскольку они недешевы. Когда размер входного списка падает ниже определенного небольшого значения (например, 8), список можно отсортировать с помощью более простого алгоритма сортировки O(n^2), такого как Простая вставка, Простой выбор, Пузырьковая сортировка или аналогичного.

Answer 4

ОК, поэтому я решил проблему.

Все было хорошо, за исключением того факта, что я не обновлял местоположение стержня, если это было действительно значение в стержне, которое было изменено во время итерации. Поэтому я добавил пару флагов в случае перестановки сводки и обновил расположение сводки после перестановки до того, как произошло следующее разделение.

Вот код, если кому-то это интересно. Конечно, хотелось бы, чтобы флаги и т. Д. Были бы более аккуратными, если у кого-нибудь из вас есть идеи?

def qsort(dataset):

    pivotatp1 = False
    pivotatp2 = False

    if len(dataset) < 2:
        return (dataset)
    else:
        point1 = 0
        point2 = len(dataset) - 1
        pivot = (len(dataset) - 1 ) // 2
        while point1 != pivot and point2 != pivot:

            while dataset[point1] <= dataset[pivot] and point1 != pivot:
                point1 = point1 + 1
            while dataset[point2] >= dataset[pivot] and point2 != pivot:
                point2 = point2 - 1

            if pivot == point1:
                pivotatp1 = True
            if pivot == point2:
                pivotatp2 = True

            x = dataset[point1]
            dataset[point1] = dataset[point2]
            dataset[point2] = x

            if pivotatp1 == True:
                pivot = point2
            if pivotatp2 == True:
                pivot = point1

        left = qsort(dataset[0:pivot])
        right = qsort(dataset[(pivot+1):len(dataset)])

        return left + [dataset[pivot]] + right

dataset = [45, 29, 56, 23, 55, 27, 43, 46]

print(qsort(dataset))