Sortieralgorithmen effizienter als Blasensortierung

Question

Ich habe diesen Algorithmus geschrieben, um eine Liste mit Blasensortierung zu sortieren. Ist dies der effizienteste Weg, eine Liste zu sortieren?
Wenn nicht, warum?
Was macht es weniger effizient und welche Alternativen gibt es?

def BubbleSort(List): 
    for i in range(len(List)-1): 
      for Number in range(len(List)-1): 
       if List[Number] > List[Number+1]: 
        List[Number], List[Number+1] = List[Number+1], List[Number] 

print(BubbleSort([5,2,1,4,3]) 

Vielen Dank!

Answer 1

In Ihrem obigen Algorithmus, wenn die length Ihres Arrays 5 ist, wird es die inneren if statement25 mal auszuführen. Im Allgemeinen, wenn Sie eine Liste von n Größe haben, wird es sicherlich n^2 Operationen mit Ausnahme der for loop und swapping.

Für eine Liste der Größe 10^6 wird es 10^12 Operationen atleast sein. C oder C++ tun um 10^9 Operationen pro Sekunde. Also dieser Code von dir wird 10^3 Sekunden dauern, was mehr als eine halbe Stunde ist. Das ist also sehr ineffizient.

Es gibt bessere Sortieralgorithmen, die Sie anstelle von bubble sort verwenden können, da sie schneller sind.

• Merge Sort
• Quick Sort
• Heap Sort

Viele andere Techniken gibt es auch, aber diese sind am häufigsten verwendet.

Abgesehen davon müssen Sie diese Algorithmen nicht implementieren, da eine der effizientesten bereits in der Standardbibliothek der meisten Sprachen von C bis Rust implementiert ist. Sie können diese Implementierung einfach verwenden und sogar Ihre eigene comparator Funktion weitergeben, wenn Sie möchten.