Ich habe einige Sorten mit Python gemessen.
Bubble sort Dies ist die einfachste und einfachste Art zu sortieren, und der Rechenaufwand für die Eingabegröße n beträgt ungefähr $ O (n ^ 2) $. Der Algorithmus ist sehr einfach und sortiert nach einem bestimmten Array.
Das folgende Programm generiert zufällig 1000 Elemente und sortiert sie mit der Blasensortierung.
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'
Als Ergebnis einer etwa 10-fachen Messung betrug die durchschnittliche Ausführungszeit etwa 0,87 Sekunden. Dies ist das erste Mal, dass die Ausführungszeit gemessen wird. Ist das in Ordnung?
Quick sort Wie der Name Quick schon sagt, ist es schnell. Die (durchschnittliche) Berechnungsmenge beträgt $ O (n \ log {n}) $, was im Vergleich zur Blasensortierung eine sehr schnelle Sortiermethode ist. Nehmen Sie aus der ersten angegebenen Sequenz ein geeignetes Element (als Pivot bezeichnet) und teilen Sie es in größere und kleinere auf. Und die Methode, den geteilten die gleiche Operation zu geben. (Siehe Wiki für Details)
Unten finden Sie ein Programm, das zufällig 1000 Elemente generiert und diese mit der Schnellsortierung sortiert.
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'
Nach 10-maliger Messung betrug die Ausführungszeit durchschnittlich 0,21 Sekunden. In der Realität ist diese Sortierung jedoch instabil. Wenn Sie weiterhin Drehpunkte auswählen, die erheblich vom Medianwert abweichen, ist das Ergebnis so lang wie die Blasensortierung (der schlechteste Berechnungsbetrag ist $ O (n ^ 2) $).
… Hmm, ist das in Ordnung? Kann die schnelle Sortierung parallelisiert werden? Wenn es noch etwas gibt, das interessant aussieht, werde ich es noch einmal schreiben! Dann
Ich habe in den Kommentaren eine Anfrage für "Bogo Sort" erhalten, daher werde ich sie vorerst veröffentlichen. .. .. (Lol) Unten finden Sie ein Programm, das zufällig 10 Elemente generiert und diese mit der Bogo-Sortierung sortiert.
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'
Bubble- und Quick-Sortierungen ergaben eine schöne durchschnittliche Laufzeit (da die Standardabweichung gering war), jedoch nicht für Bogo-Sortierungen. Die Ausführungszeit lag im Bereich von etwa 3,79 Sekunden bis 47,25 Sekunden.
Die Bogo-Sortierung ist eine instabile Sortierung und der (durchschnittliche) Rechenaufwand beträgt $ O (nn!) $. … Es ist nicht sehr praktisch (; ´ ･ ω ･)