He estado trabajando duro para producir un algoritmo de clasificación rápida 'simple', ya que muchos de los ejemplos en línea parecen estar escritos de manera más compleja de lo que quizás sea necesario para demostrar la mecánica del algoritmo.

Llegué a un punto en el que no puedo ver por qué la lista final no se ordena correctamente. Estaría agradecido por un conjunto de ojos nuevos y un puntero en la dirección correcta para terminar el código.

Aquí está mi código actual:

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

Cualquier ayuda sería muy apreciada.

**** EDITAR **** nuevo código después de la sugerencia de @Marko Mahnič pero todavía no se ordena correctamente. Estaría muy agradecido por cualquier otra ayuda que se pueda ofrecer.

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))
-1
sw123456 7 oct. 2019 a las 17:42

4 respuestas

La mejor respuesta

Quicksort normalmente es una ordenación in situ, ordena la matriz original en lugar de devolver una copia ordenada de la matriz original. El código de ejemplo de la pregunta es una variación de la versión de partición rápida de Hoare. La partición Hoare divide una partición en elementos <= pivote y elementos> = pivote. Elementos == para pivotar y / o el pivote puede terminar en cualquier lugar, pero esto no es un problema, y no hay necesidad de rastrear dónde termina el pivote. El tiempo de ejecución generalmente será menor si hay duplicados.

Ejemplo de clasificación rápida estándar con el método de partición Hoare

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)
1
rcgldr 9 oct. 2019 a las 04:28

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.

1
Fábio Roberto Teodoro 7 oct. 2019 a las 20:18

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))
0
sw123456 7 oct. 2019 a las 17:59

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.

1
Marko Mahnič 10 oct. 2019 a las 05:17
58271900