Python: Wie kann ich meine Implementierung der Bubble-Sortierung zeiteffizienter machen?

Question

Hier ist mein Code - eine Blase Sortieralgorithmus für Listenelemente in asc Reihenfolge Sortierung:

foo = [7, 0, 3, 4, -1] 
cnt = 0 
for i in foo: 
    for i in range(len(foo)-1): 
     if foo[cnt] > foo[cnt + 1]: 
      temp = foo[cnt] 
      c[cnt] = c[cnt + 1] 
      c[cnt + 1] = temp 
     cnt = cnt + 1 
    cnt = 0 

Ich habe meinen Code wurde überarbeitet, aber es ist noch zu ineffizient für einen Online-Richter. Einige Hilfe würde sehr geschätzt werden!

Answer 1

vorzeitiges Ausscheiden BubbleSort

1. Die erste Schleife hat keinen Einfluss auf das, was passiert, im Inneren
2. Die zweite Schleife macht die ganze schwere Arbeit. Sie können count mit enumerate
3. loswerden, um Elemente auszutauschen, verwenden Sie den Pythonic Swap - a, b = b, a.
4. Verwenden Sie gemäß this comment einen frühen Ausgang. Wenn an keiner Stelle innerhalb der inneren Schleife Swaps gemacht werden, bedeutet dies, dass die Liste sortiert ist und keine weitere Iteration notwendig ist. Dies ist die Intuition hinter changed.
5. Per Definition, nach der Iteration der äußeren Schleife, die letzten i Elemente wurden sortiert, so dass Sie den konstanten Faktor mit dem Algorithmus verbunden weiter reduzieren können.

foo = [7, 0, 3, 4, -1] 
for i in range(len(foo)): 
    changed = False 
    for j, x in enumerate(foo[:-i-1]): 
     if x > foo[j + 1]: 
      foo[j], foo[j + 1] = foo[j + 1], foo[j] 
      changed = True 

    if not changed: 
     break 

print(foo) 
[-1, 0, 3, 4, 7] 

Beachten Sie, dass keines dieser Optimierungen die asymptotische (Big-O) Komplexität der BubbleSort ändern (die O(N ** 2) bleibt), sondern reduziert nur die konstanten Faktoren verbunden.

Answer 2

Eine einfache Optimierung von i + 1 Index zweite Schleife zu starten:

for i in range(0, len(foo)): 
    for j in range(i+1, len(foo)): 
     if (foo[i] > foo[j]): 
      temp = foo[i] 
      foo[i] = foo[j] 
      foo[j] = temp 

Da Sie bereits alles sortiert bis zu Index i gibt es keine Notwendigkeit wieder darüber iterieren ist. Dies kann Ihnen mehr als 50% der Vergleiche ersparen - in diesem Fall sind es 10 gegenüber 25 in Ihrem ursprünglichen Algorithmus.

Answer 3

Sie müssen die Big-Oh-Notation verstehen, um zu verstehen, wie effizient Ihr Algorithmus in Bezug auf die Verwendung von Computerressourcen unabhängig von Computerarchitektur oder Taktrate ist. Es hilft Ihnen im Grunde, die Worst-Case-Laufzeit oder die Speichernutzung Ihres Algorithmus zu analysieren, wenn die Größe der Eingabe zunimmt. Zusammenfassend wird die Laufzeit Ihres Algorithmus in eine dieser Kategorien fallen (vom schnellsten zum langsamsten);

O (1): Konstante Zeit. Ausgeprägt (Oh von 1). Die schnellste Zeit.

O (lg n): Logarithmische Zeit. Ausgeprägt (Oh, log n). Schneller als lineare Zeit. Traditionell ist es die schnellste Zeit für die Suche.

O (n): lineare Zeit. Ausgedrückt (Oh von n, n ist die Größe Ihres Eingangs, z. B. Größe von ein Array). Normalerweise etwas, wenn Sie jedes einzelne Bit von Ihre Eingabe untersuchen müssen.

O (nlgn): Die schnellste Zeit, die wir derzeit erreichen können, wenn eine Sortierung auf einer Liste von Elementen durchgeführt wird.

O (n ** 2): Oh n Quadrat. Quadratische Zeit. Oft ist dies die Grenze, wenn wir verschachtelte Schleifen haben.

O (2 ** n): Wirklich, wirklich groß! Eine Zahl, die auf n erhöht wird, ist langsamer als .

In Ihrem Fall verwenden Sie verschachtelte Schleifen, die O (n 2) ist. Der Code, den ich geschrieben habe, verwendet eine einzelne while-Schleife und hat eine Wachstumskomplexität von O (n), die schneller ist als O (n 2). Ich habe es nicht wirklich auf einer sehr großen array versucht, aber in Ihrem Fall scheint es zu funktionieren. Probieren Sie es aus und lassen Sie mich wissen, ob es wie erwartet funktioniert.

k = [7, 0, 3, 4, -1] 
n = len(k) 
i = 0 
count = 0 
while count < n**2: # assuming we wouldn't go through the loop more than n squared times 
    if i == n - 1: 
     i = 0 
     count += 1 
     swapped = False 
    elif k[i] > k[i+1]: 
     temp = k[i] 
     k[i] = k[i+1] 
     k[i+1] = temp 
     i+=1 
     swapped = True 
    elif swapped == False: 
     i += 1 
    elif swapped == True and i < n - 1: 
     i += 1 

Hinweis: In der Beispielliste (k), brauchen wir nur in einer Schleife durch die Liste dreimal, um sie in aufsteigender Reihenfolge sortiert werden. Wenn Sie also die while-Schleife zu dieser Codezeile while count < 4: ändern, würde es immer noch funktionieren.