J'ai mesuré certaines sortes avec Python.
Bubble sort C'est le moyen le plus simple et le plus simple de trier, et le montant du calcul est d'environ $ O (n ^ 2) $ pour la taille d'entrée n. L'algorithme est très simple, il trie dans l'ordre pour un tableau donné.
Ce qui suit est un programme qui génère au hasard 1000 éléments et les trie avec le tri à bulles.
bubble.py
import time
import numpy as np
def BUBBLE_SORT(A):
n = np.size(A)
m = n-1
while m > 1:
k = 0
while k < m :
if A[k] > A[k+1]:
A[k],A[k+1] = A[k],A[k+1]
k += 1
m -= 1
return A
# mesure time from here
start = time.time()
# set the range for random
Min = 1
Max = 1000
N = Max
# get a list consisted by N random integers in [min,max]
LIST = np.random.randint(Min,Max,N)
# sorting by bubble
BUBBLE_SORT(LIST)
print LIST
print str(time.time()-start) + 'sec'
Après avoir mesuré environ 10 fois, le temps d'exécution moyen était d'environ 0,87 s. C'est la première fois que vous mesurez le temps d'exécution, est-ce que tout va bien?
Quick sort Comme le nom de Quick l'indique, c'est rapide. Le montant (moyen) du calcul est $ O (n \ log {n}) $, qui est une méthode de tri très rapide par rapport au tri à bulles. À partir de la première séquence donnée, prenez un élément approprié (appelé pivot) et divisez-le en éléments plus grands et plus petits. Et la méthode pour donner la même opération aux divisés. (Voir Wiki pour plus de détails)
Vous trouverez ci-dessous un programme qui génère au hasard 1000 éléments et les trie avec le tri rapide.
quick.py
import time
import numpy as np
#ignore exception
def QUICK_SORT(A,L,R):
if L < R:
p = L
k = L+1
while k <= R:
if A[k] < A[L]:
A[p+1], A[k] = A[k], A[p+1]
p += 1
k += 1
A[L], A[p] = A[p], A[L]
A = QUICK_SORT(A,L,p-1)
A = QUICK_SORT(A,p+1,R)
return A
# measure time from here
start = time.time()
# set the range for random
Min = 1
Max = 1000
N = Max
# get a list consisted by N random integers in [min,max]
LIST = np.random.randint(Min,Max,N)
N -= 1
# sort by quick
LIST = QUICK_SORT(LIST,0,N)
print LIST
print str(time.time()-start) + 'sec'
Après avoir mesuré 10 fois, le temps d'exécution était de 0,21 s en moyenne. Cependant, en réalité, ce tri est instable, et si vous continuez à sélectionner des pivots qui s'écartent considérablement de la valeur médiane, le résultat sera aussi long que le tri à bulles (le pire montant de calcul est $ O (n ^ 2) $).
… Hmm, est-ce que ça va comme ça… Le tri rapide peut-il être parallélisé? S'il y a autre chose qui semble intéressant, je l'écrirai à nouveau! Puis
J'ai reçu une demande de "Bogo Sort" dans les commentaires, donc je la posterai pour le moment. .. .. (Lol) Voici un programme qui génère au hasard 10 éléments et les trie avec le tri Bogo.
bogo.py
import numpy as np
import time
start = time.time()
def BOGO_SORT(A):
set_range = range(0,A.size -1)
# if A is ssorted, ignore while
while not isSorted(A,set_range):
np.random.shuffle(A)
def isSorted(B,Range):
for i in Range:
# if there exist some illegal in the given array, return false
if B[i] > B[i+1]:
return False
return True
# measure time from here
start = time.time()
# set the range for random
Min = 1
Max = 10
N = Max
# get a list consisted by N random integers in [min,max]
LIST = np.random.randint(Min,Max,N)
# sorting by bubble
BOGO_SORT(LIST)
print LIST
print str(time.time()-start) + 'sec'
Les tris Bubble et Quick ont donné un bon temps d'exécution moyen (car l'écart type était petit), mais pas pour les tris Bogo. Le temps d'exécution était compris entre environ 3,79 secondes et 47,25 secondes.
Le tri Bogo est un tri instable et le montant (moyen) du calcul est $ O (nn!) $. … Ce n'est pas très pratique (; ´ ･ ω ･)