Bubble Sort ist der einfachste Sortieralgorithmus, der durch wiederholtes Vertauschen benachbarter Elemente funktioniert, wenn sie in der falschen Reihenfolge sind.
Python-Programm für Blasensortierung
Die zur Verfügung gestellt Python Code implementiert den Bubble-Sort-Algorithmus, der ein Array sortiert, indem er benachbarte Elemente wiederholt vergleicht und sie vertauscht, wenn sie in der falschen Reihenfolge sind. Der Algorithmus durchläuft das Array mehrmals, wobei jeder Durchgang das größte unsortierte Element an die richtige Position am Ende verschiebt. Der Code beinhaltet eine Optimierung: Wenn während eines Durchlaufs keine Swaps durchgeführt werden, ist das Array bereits sortiert und der Sortiervorgang stoppt. Das Beispiel initialisiert ein Array, wendet die Funktion „bubbleSort“ an, um es zu sortieren, und gibt das sortierte Array aus. Nach der Sortierung lautet die Ausgabe: [11, 12, 22, 25, 34, 64, 90], was aufsteigende Reihenfolge angibt.
Python3
# Python program for implementation of Bubble Sort def bubbleSort(arr): n = len(arr) # optimize code, so if the array is already sorted, it doesn't need # to go through the entire process # Traverse through all array elements for i in range(n-1): # range(n) also work but outer loop will # repeat one time more than needed. # Last i elements are already in place swapped = False for j in range(0, n-i-1): # traverse the array from 0 to n-i-1 # Swap if the element found is greater # than the next element if arr[j]>arr[j + 1]: swapped = True arr[j], arr[j + 1] = arr[j + 1], arr[j] if not swapped: # wenn wir keinen einzigen Tausch durchführen mussten , # können wir einfach die Hauptschleife verlassen. return # Treibercode zum Testen oben arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print('Sorted array is:') for i in range(len(arr)): print('% d' % arr[i], end=' ')> Ausgabe
Sorted array is: 11 12 22 25 34 64 90>
Zeitkomplexität : An2).
Hilfsraum : O(1).
Den vollständigen Artikel finden Sie unter Blasensortierung für mehr Details!
Python3 def bubblesort(elements): # Looping from size of array from last index[-1] to index [0] for n in range(len(elements)-1, 0, -1): swapped = False for i in range(n): if elements[i]>elements[i + 1]: swapped = True # Datenaustausch, wenn das Element kleiner als das nächste Element im Array ist. Elemente[i], Elemente[i + 1] = Elemente[i + 1], Elemente[i], wenn nicht ausgetauscht : # Beenden der Funktion, wenn wir keinen einzigen Austausch vorgenommen haben # was bedeutet, dass das Array bereits sortiert ist. return elements = [39, 12, 18, 85, 72, 10, 2, 18] print('Unsorted list is,') print(elements) bubblesort(elements) print('Sorted Array is, ') print(elemente)> Ausgabe
Unsorted list is, [39, 12, 18, 85, 72, 10, 2, 18] Sorted Array is, [2, 10, 12, 18, 18, 39, 72, 85]>
Zeitkomplexität : An2). In der Praxis könnte diese optimierte Version jedoch weniger Zeit in Anspruch nehmen, da die Funktion beim Sortieren des Arrays zurückkehren würde.
Hilfsraum : O(1).