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 piezas diferentes de datos:

• x = número de números para ordenar
• y = gama los números están en (todos los enteros generados al azar)
• z = tiempo total tomado para especie

Cuando:
x = 100.000 y
y = (0,100000), entonces
z = 0,94182094911 sec

Cuando:
x = 100.000 y
y = (0100) a continuación,
z = 12.4218382537 sec

Cuando:
x = 100.000 y
y = (0, 10) luego
z = 110.267447809 seg

¿Alguna idea?

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) 

------------------- revisó nuevo código --------------- -------------

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

Creo que esto tiene que ver con la elección de un pivote. Dependiendo de cómo funciona su paso de partición, si tiene muchos valores duplicados, su algoritmo puede degenerar en comportamiento cuadrático cuando se enfrenta a muchos duplicados. Por ejemplo, supongamos que está tratando de QuickSort esta corriente:

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

Si no se tiene cuidado con la forma en que lo hace el paso de particionado, esto puede degenerar rápidamente. Por ejemplo, suponga que selecciona su pivote como el primer 0, dejándolo con el arreglo

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

para la partición. 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 clasificación rápida degenere a O (n), ya que cada llamada recursiva solo está reduciendo el tamaño de la entrada en uno (es decir, quitando el elemento de pivote).

me di cuenta de que en su código, el paso de particionado en efecto, hacer esto:

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

Dada una corriente que es un montón de copias de un mismo elemento, esto pondrá a todos en una matriz a recursivamente ordenar.

Por supuesto, esto parece un caso ridículo: ¿cómo está esto conectado a la reducción de la cantidad de valores en la matriz? - pero en realidad aparece cuando estás ordenando muchos elementos que no son distintos. En particular, después de unos pocos 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 by Bob Sedgewick and Jon Bentley acerca de cómo modificar el paso de la partición para que funcione rápidamente cuando hay elementos duplicados. Está conectado a Dijkstra's Dutch national flag problem, y sus soluciones son realmente ingeniosas.

Una opción que funciona es dividir la entrada en tres grupos: menos, igual y mayor. Una vez que haya dividido la entrada de esta manera, solo necesita ordenar los grupos cada vez menos; los grupos iguales ya están ordenados El enlace de arriba a la charla muestra cómo hacer esto más o menos en el lugar, pero como ya está usando un quicksort fuera de lugar, la solución debería ser fácil. Aquí está mi intento de que:

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 la sintaxis totalmente ilegal. ¡Pero espero que la idea sea clara! :-)

Answer 2

cosas que sabemos: la complejidad

1. Tiempo de ordenación rápida de la matriz no ordenada es O(n*logn).
2. Si la matriz ya está ordenada, se degrada a O(n^2).
3. primeras dos declaraciones no son discretos, es decir, cuanto más cerca está de ser ordenadas según una matriz, la más cercana es la complejidad de tiempo de ordenación rápida a O(n^2), y en sentido inverso a medida que barájalo la complejidad enfoques O(n*logn)

Ahora, vamos a mira tu experimento:

• En los tres casos, utilizaste la misma cantidad de elementos. Entonces, nuestro n que usted llamó x es siempre 100000.
• En su primer experimento, utilizó números entre 0 y 100000, por lo que idealmente con un generador de números aleatorios perfecto obtendría números mayormente diferentes en una lista relativamente desordenada, por lo tanto ajustando el caso de complejidad O(n*logn).
• En su tercer experimento, utilizó números entre 0 y 10 en una lista grande de 100000 elementos. Significa que hubo muchos duplicados en su lista, por lo que es mucho más parecido a una lista ordenada que en el primer experimento. Entonces, en ese caso, la complejidad del tiempo estaba mucho más cerca de O(n^2).

Y con la misma lo suficientemente grande n se puede decir que n*logn > n^2, que en realidad se confirma por su experimento.

Answer 3

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