algorithms - quicksort recursivo python

¿Quicksort ordena números más grandes más rápido?

Question

Estaba jugando con Python tratando de practicar mis algoritmos de clasificación y descubrí algo interesante.

Tengo tres datos diferentes:

• x = número de números para ordenar
• y = rango en el que están los números (todas las entradas aleatorias)
• z = tiempo total tomado para ordenar

Cuando:
x = 100000 y
y = (0,100000) entonces
z = 0.94182094911 seg

Cuando:
x = 100000 y
y = (0,100) entonces
z = 12.4218382537 seg.

Cuando:
x = 100000 y
y = (0,10) entonces
z = 110.267447809 seg.

¿Algunas ideas?

Código:

import time
import random
import sys

#-----Function definitions

def quickSort(array): #random pivot location quicksort. uses extra memory.
    smaller = []
    greater = []
    if len(array) <= 1:
        return array
    pivotVal = array[random.randint(0, len(array)-1)]
    array.remove(pivotVal)
    for items in array:
        if items <= pivotVal:
            smaller.append(items)
        else:
            greater.append(items)
    return concat(quickSort(smaller), pivotVal, quickSort(greater))

def concat(before, pivot, after):
    new = []
    for items in before:
        new.append(items)
    new.append(pivot)
    for things in after:
        new.append(things)
    return new

#-----Variable definitions
list = []
iter = 0
sys.setrecursionlimit(20000)
start = time.clock() #start the clock

#-----Generate the list of numbers to sort
while(iter < 100000):
    list.append(random.randint(0,10))  #modify this to change sorting speed
    iter = iter + 1
timetogenerate = time.clock() - start #current timer - last timer snapshot

#-----Sort the list of numbers
list = quickSort(list)
timetosort = time.clock() - timetogenerate #current timer - last timer snapshot

#-----Write the list of numbers
file = open("C:/output.txt", ''w'')
for items in list:
    file.write(str(items))
    file.write("/n")
file.close()
timetowrite = time.clock() - timetosort #current timer - last timer snapshot

#-----Print info
print "time to start: " + str(start)
print "time to generate: " + str(timetogenerate)
print "time to sort: " + str(timetosort)
print "time to write: " + str(timetowrite)
totaltime = timetogenerate + timetosort + start
print "total time: " + str(totaltime)

------------------- código NUEVO revisado ----------------------------

def quickSort(array): #random pivot location quicksort. uses extra memory.
    smaller = []
    greater = []
    equal = []
    if len(array) <= 1:
        return array
    pivotVal = array[random.randint(0, len(array)-1)]
    array.remove(pivotVal)
    equal.append(pivotVal)
    for items in array:
        if items < pivotVal:
            smaller.append(items)
        elif items > pivotVal:
            greater.append(items)
        else:
            equal.append(items)
    return concat(quickSort(smaller), equal, quickSort(greater))

def concat(before, equal, after):
    new = []
    for items in before:
        new.append(items)
    for items in equal:
        new.append(items)
    for items in after:
        new.append(items)
    return new

Answer 1

Cosas que sabemos:

1. La complejidad del tiempo para el tipo rápido de matriz desordenada es O(n*logn) .
2. Si la matriz ya está ordenada, se degrada a O(n^2) .
3. Las dos primeras afirmaciones no son discretas, es decir, cuanto más cerca esté de estar ordenada una matriz, más cerca estará la complejidad del tiempo de clasificación rápida a O(n^2) , y de forma inversa a medida que la mezclamos, la complejidad se aproxima a O(n*logn)

Ahora, veamos tu experimento:

• En los tres casos usaste el mismo número de elementos. Entonces, nuestro n que llamaste x es siempre 100000.
• En su primer experimento, utilizó números entre 0 y 100000, así que lo ideal sería que con un generador de números aleatorios perfectos obtuviera la mayoría de los números diferentes en una lista relativamente desordenada, por lo que se O(n*logn) caso de complejidad O(n*logn) .
• En su tercer experimento, usó números entre 0 y 10 en una lista grande de 100000 elementos. Significa que había bastantes duplicados en tu lista, lo que la acerca mucho más a una lista ordenada que en el primer experimento. Entonces, en ese caso, la complejidad del tiempo era mucho más cercana a O(n^2) .

Y con el mismo número suficientemente grande n puede decir que n*logn > n^2 , lo que en realidad confirmó con su experimento.

Answer 2

Creo que esto tiene que ver con la elección de un pivote. Dependiendo de cómo funcione su paso de partición, si tiene muchos valores duplicados, su algoritmo puede degenerar a un comportamiento cuadrático cuando se enfrenta a muchos duplicados. Por ejemplo, supongamos que está intentando ordenar rápidamente esta secuencia:

 [0 0 0 0 0 0 0 0 0 0 0 0 0]

Si no tiene cuidado con cómo realiza el paso de partición, esto puede degenerar rápidamente. Por ejemplo, supongamos que elige su pivote como el primer 0, dejándolo con la matriz

 [0 0 0 0 0 0 0 0 0 0 0 0]

particionar. Su algoritmo podría decir que los valores más pequeños son la matriz

 [0 0 0 0 0 0 0 0 0 0 0 0]

Y los valores más grandes son la matriz.

 []

Este es el caso que hace que la ordenación rápida degenere a O (n ² ), ya que cada llamada recursiva solo reduce el tamaño de la entrada en uno (es decir, al extraer el elemento de pivote).

Noté que en su código, su paso de partición efectivamente hace esto:

for items in array:
    if items <= pivotVal:
        smaller.append(items)
    else:
        greater.append(items)

Dado un flujo que es un montón de copias del mismo elemento, esto los pondrá a todos en una matriz para ordenar de forma recursiva.

Por supuesto, esto parece un caso ridículo: ¿cómo se relaciona esto con la reducción del número de valores en la matriz? - pero en realidad aparece cuando clasificas muchos elementos que no son distintos. En particular, después de algunos pasos de la partición, es probable que agrupe todos los elementos iguales, lo que lo llevará a este caso.

Para una discusión sobre cómo evitar que esto suceda, hay una gran charla de Bob Sedgewick y Jon Bentley sobre cómo modificar el paso de la partición para que funcione rápidamente cuando esté en presencia de elementos duplicados. Está conectado con el problema de la bandera nacional holandesa de Dijkstra, y sus soluciones son realmente inteligentes.

Una opción que funciona es dividir la entrada en tres grupos: menos, igual y mayor. Una vez que haya roto la entrada de esta manera, solo necesita clasificar los grupos menores y mayores; Los grupos iguales ya están ordenados. El enlace anterior a la charla muestra cómo hacer esto más o menos en el lugar, pero como ya está utilizando una ordenación rápida fuera de lugar, la solución debería ser fácil. Aquí está mi intento de hacerlo:

for items in array:
    if items < pivotVal:
        smaller.append(items)
    elif items == pivotVal:
        equal.append(items)
    else:
        greater.append(items)

Nunca he escrito una línea de Python en mi vida, por cierto, por lo que esta puede ser una sintaxis totalmente ilegal. ¡Pero espero que la idea sea clara! :-)

Answer 3

El algoritmo de ordenación rápida tiene una debilidad conocida: es más lento cuando los datos están ordenados en su mayoría. Cuando tenga 100000 entre 0 y 10, estarán más cerca de ser "ordenados en su mayoría" que de 100000 números en el rango de 0 a 100000.