¿Por qué mi intento de una 'Clasificación rápida' no se ordena correctamente?

Aquí hay una versión iterativa de su algoritmo. Utiliza una pila para eliminar la necesidad de las llamadas recursivas. Usar el último elemento como pivote también lo hace más simple:

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))

Y podría hacerlo más legible extrayendo la manipulación de la pila y la partición para separar las funciones.

Bien, entonces he resuelto el problema.

Todo estaba bien, excepto por el hecho de que no estaba actualizando la ubicación del pivote si realmente era el valor en el pivote que se intercambió durante una iteración. Por lo tanto, agregué un par de banderas en caso de que se intercambie el pivote y actualicé la ubicación del pivote después del intercambio antes de que ocurriera la siguiente división.

Aquí está el código si alguien está interesado. Por supuesto, me encantaría que las banderas, etc., sean más ordenadas si alguno de ustedes tiene alguna idea.

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))

Las condiciones deben ser point1 < point2, no pointX != pivot. La división a izquierda y derecha debe ser donde se encuentran el punto 1 y el punto 2.

Tenga en cuenta que en qsort la parte importante del pivote es su valor, no su índice. Puede elegir el valor de cualquier elemento de dataset como pivote. Cuando se realiza la partición, los elementos a la izquierda de pivot2 serán más bajos o iguales al valor del pivote y los elementos a la derecha de pivot1 serán más altos o iguales al valor del pivote.

Puede ajustar pivot1 y pivot2 antes de la llamada recursiva para que la matriz left contenga solo los elementos inferiores al pivote, la matriz middle contiene los elementos con el valor del pivote y la matriz right contiene los elementos más altos que el valor del pivote. Esta es una ligera optimización. El resultado es entonces left + middle + right. Esto es especialmente útil cuando dataset tiene elementos duplicados.

Estos cambios harán que su algoritmo sea correcto pero no óptimo. El problema es que el algoritmo está haciendo copias de partes de la lista original que requiere O(n^2) espacio adicional que es (n-1)*(n-2)/2 en el peor de los casos cuando selecciona el valor más alto o más bajo como pivote. Entonces, en lugar de ordenar listas completas, el algoritmo debe cambiarse para ordenar parte de la lista en el lugar. Su interfaz debe cambiarse a:

def qsort( a, left, right ):

Y las llamadas recursivas deben ser:

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

Otra optimización es reducir la cantidad de llamadas recursivas ya que no son baratas. Cuando el tamaño de la lista de entrada cae por debajo de un cierto valor pequeño (8, por ejemplo), la lista se puede ordenar con un algoritmo de ordenación más simple O(n^2) como inserción simple, selección simple, clasificación de burbujas o similar.