Le moyen le plus rapide de trier en Python

Si vous êtes intéressé par temps asymptotiquepuis comptage, de tri ou tri radix fournir de bonnes performances.

Toutefois, si vous êtes intéressé par temps horloge murale vous aurez besoin de comparer la performance entre les différents algorithmes à l'aide de vos ensembles de donnéesque les différents algorithmes fonctionnent différemment avec différents ensembles de données. Dans ce cas, il est toujours intéressant d'essayer de quicksort:

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

Source: http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python

Tri Radix théoriquement s'exécute en temps linéaire (temps de tri pousse à peu près en proportion directe de la taille de la matrice ), mais dans la pratique Quicksort est probablement plus adapté, sauf si vous êtes le tri absolument massive des tableaux.

Si vous voulez faire de quicksort un peu plus vite, vous pouvez utiliser le tri par insertion] lorsque la taille du tableau devient petit.

Il serait probablement utile de comprendre les notions de complexité algorithmique et Big-O notation trop.

Nous pouvons utiliser le comte de tri à l'aide d'un dictionnaire afin de réduire l'augmentation d'utilisation de l'espace, et de garder le temps d'exécution faible. Le comte de tri est beaucoup plus lente pour les petites tailles de tableau d'entrée en raison de l'python vs C mise en œuvre de surcharge. Le comte de tri commence à dépasser l'ordinaire de tri lorsque la taille du tableau (NOMBRE) est d'environ 1 million de dollars.

Si vous voulez vraiment énormes accélérations pour les plus petits de la taille des entrées, de mettre en œuvre le comte de tri en C et l'appeler à partir de Python.

(Correction d'un bug qui Aaron (+1) ont aidé à capturer ...)
Le python seulement la mise en œuvre ci-dessous compare les 2 approches...

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

Les fonctions intégrées sont les meilleurs, mais puisque vous ne pouvez pas les utiliser avoir un coup d'oeil à ceci:

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

@fmark
Certains d'analyse comparative d'un python de fusion-tri de mise en œuvre que j'ai écrit contre python quicksorts de http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python
et à partir du haut de réponse.

1. La taille de la liste et de la taille des numéros dans la liste de pertinence

de fusion trier les remporte, cependant il utilise builtin int() pour le plancher

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