La forma más rápida de ordenar en Python

Question

¿Cuál es la forma más rápida de ordenar una matriz de enteros enteros mayor que 0 y menos de 100000 en Python? Pero no usa las funciones integradas como ordenar.

Estoy viendo la posibilidad de combinar 2 funciones deportivas dependiendo del tamaño de entrada.

Answer 1

Si usted está interesado en tiempo asintótica, a continuación, contando tipo o especie radix proporcionar un buen rendimiento.

Sin embargo, si usted está interesado en pared del tiempo del reloj tendrá que comparar el rendimiento entre los diferentes algoritmos usando sus datos particular, establece, ya que diferentes algoritmos actúan de forma diferente con diferentes conjuntos de datos. En ese caso, su siempre vale la pena la clasificación rápida tratando:

def qsort(inlist): 
    if inlist == []: 
     return [] 
    else: 
     pivot = inlist[0] 
     lesser = qsort([x for x in inlist[1:] if x < pivot]) 
     greater = qsort([x for x in inlist[1:] if x >= pivot]) 
     return lesser + [pivot] + greater 

Fuente: http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python versiones

Answer 2

Dado que conoce el rango de números, puede usar Counting Sort, que será lineal en el tiempo.

Answer 3

El construido en funciones son las mejores, pero ya que no se pueden utilizar echar un vistazo a esto:

http://en.wikipedia.org/wiki/Quicksort

Answer 4

tempranos de Python utilizan un híbrido de samplesort (una variante de la clasificación rápida con el tamaño de la muestra) y binarios ordenación por inserción como el construido -in algoritmo de clasificación. Esto resultó ser algo inestable. S0, desde Python 2.3 en adelante usa el algoritmo adaptive mergesort.

Orden de mergesort (promedio) = O(nlogn). Orden de mergesort (peor) = O(nlogn). Pero Orden de ordenación rápida (el peor) = n * 2

si utiliza list=[ .............. ]

list.sort() utiliza mergesort algorithm.

Para la comparación entre el algoritmo de ordenación puede leer wiki

Para la comparación detalle comp

Answer 5

Podemos usar la clasificación de recuento usando un diccionario para minimizar el uso de espacio adicional, y kee p el tiempo de funcionamiento bajo también. El tipo de recuento es mucho más lento para los tamaños pequeños de la matriz de entrada debido a la sobrecarga de implementación python vs C. El tipo de recuento comienza a superar el tipo normal cuando el tamaño de la matriz (COUNT) es aproximadamente 1 millón.

Si realmente desea grandes aceleraciones para entradas de menor tamaño, implemente la clasificación de conteo en C y llámelo de Python.

(Se ha corregido un error que Aaron (1) ayudó a la captura ...) La pitón única aplicación que sigue compara los enfoques 2 ...

import random 
import time 

COUNT = 3000000 

array = [random.randint(1,100000) for i in range(COUNT)] 
random.shuffle(array) 

array1 = array[:] 

start = time.time() 
array1.sort() 
end = time.time() 
time1 = (end-start) 
print 'Time to sort = ', time1*1000, 'ms' 

array2 = array[:] 

start = time.time() 
ardict = {} 
for a in array2: 
    try: 
     ardict[a] += 1 
    except: 
     ardict[a] = 1 

indx = 0 
for a in sorted(ardict.keys()): 
    b = ardict[a] 
    array2[indx:indx+b] = [a for i in xrange(b)] 
    indx += b 

end = time.time() 
time2 = (end-start) 
print 'Time to count sort = ', time2*1000, 'ms' 

print 'Ratio =', time2/time1 

Answer 6

Radix ordenaciones teóricamente en el tiempo lineal (tiempo de clase crece aproximadamente en proporción directa al tamaño de la matriz), pero en la práctica Quicksort es probablemente más adecuado, a menos que esté ordenando matrices absolutamente masivas.

Si desea hacer quicksort un poco más rápido, puede usar inserción sort] cuando el tamaño de la matriz se vuelve pequeño.

Probablemente sería útil comprender también los conceptos de complejidad algorítmica y notación Big-O.

Answer 7

def sort(l): 
    p = 0 
    while(p<len(l)-1): 
     if(l[p]>l[p+1]): 
      l[p],l[p+1] = l[p+1],l[p] 
      if(not(p==0)): 
       p = p-1 
     else: 
      p += 1 
    return l 

este es un algoritmo que he creado pero que es muy rápido. simplemente haga una ordenación (l) siendo la lista que desea ordenar.

Answer 8

@fmark Algunos evaluación comparativa de una implementación de Python fusión-tipo que escribí contra quicksorts pitón de http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python y de respuesta superior.

1. tamaño de la lista y el tamaño de los números en la lista irrelevante

ordenamiento por mezcla gana, sin embargo, utiliza int orden interna() a baja

import numpy as np 
x = list(np.random.rand(100)) 


# TEST 1, merge_sort 
def merge(l, p, q, r): 
    n1 = q - p + 1 
    n2 = r - q 
    left = l[p : p + n1] 
    right = l[q + 1 : q + 1 + n2] 

    i = 0 
    j = 0 
    k = p 
    while k < r + 1: 
     if i == n1: 
      l[k] = right[j] 
      j += 1 
     elif j == n2: 
      l[k] = left[i] 
      i += 1 
     elif left[i] <= right[j]: 
      l[k] = left[i] 
      i += 1 
     else: 
      l[k] = right[j] 
      j += 1 
     k += 1 

def _merge_sort(l, p, r): 
    if p < r: 
     q = int((p + r)/2) 
     _merge_sort(l, p, q) 
     _merge_sort(l, q+1, r) 
     merge(l, p, q, r) 

def merge_sort(l): 
    _merge_sort(l, 0, len(l)-1) 

# TEST 2 
def quicksort(array): 
    _quicksort(array, 0, len(array) - 1) 

def _quicksort(array, start, stop): 
    if stop - start > 0: 
     pivot, left, right = array[start], start, stop 
     while left <= right: 
      while array[left] < pivot: 
       left += 1 
      while array[right] > pivot: 
       right -= 1 
      if left <= right: 
       array[left], array[right] = array[right], array[left] 
       left += 1 
       right -= 1 
     _quicksort(array, start, right) 
     _quicksort(array, left, stop) 

# TEST 3 
def qsort(inlist): 
    if inlist == []: 
     return [] 
    else: 
     pivot = inlist[0] 
     lesser = qsort([x for x in inlist[1:] if x < pivot]) 
     greater = qsort([x for x in inlist[1:] if x >= pivot]) 
     return lesser + [pivot] + greater 

def test1(): 
    merge_sort(x) 

def test2(): 
    quicksort(x) 

def test3(): 
    qsort(x) 

if __name__ == '__main__': 
    import timeit 
    print('merge_sort:', timeit.timeit("test1()", setup="from __main__ import test1, x;", number=10000)) 
    print('quicksort:', timeit.timeit("test2()", setup="from __main__ import test2, x;", number=10000)) 
    print('qsort:', timeit.timeit("test3()", setup="from __main__ import test3, x;", number=10000)) 

Answer 9

que podría ser un poco tarde para el programa, pero hay un artículo interesante que compara diferentes géneros en https://www.linkedin.com/pulse/sorting-efficiently-python-lakshmi-prakash

Uno de los principales puntos a tener en cuenta es que, aunque el tipo predeterminado Es genial que podemos hacerlo un poco mejor con una versión compilada de quicksort. Esto requiere el paquete Numba.

Aquí hay un enlace al repositorio de Github: https://github.com/lprakash/Sorting-Algorithms/blob/master/sorts.ipynb