Lernen Sie, wie Sie die Python-Funktion Sortieren zum Sortieren von Listen, Arrays, Wörterbüchern usw. mit verschiedenen Sortiermethoden und Algorithmen in Python verwenden können:
Das Sortieren ist eine Technik, die zum Sortieren der Daten in einer Reihenfolge entweder in aufsteigender oder absteigender Reihenfolge verwendet wird.
Meistens sind die Daten der großen Projekte nicht in der richtigen Reihenfolge angeordnet, was zu Problemen beim effizienten Zugriff und Abrufen der benötigten Daten führt.
Um dieses Problem zu lösen, werden Sortierverfahren eingesetzt. Python bietet verschiedene Sortierverfahren zum Beispiel, Blasensortierung, Einfügesortierung, Mischsortierung, Quicksortierung usw.
In diesem Tutorium werden wir verstehen, wie das Sortieren in Python mit Hilfe verschiedener Algorithmen funktioniert.
Python-Sortierung
Syntax von Python Sort
Zum Sortieren stellt Python die eingebaute Funktion "sort()" zur Verfügung, mit der die Datenelemente einer Liste in aufsteigender oder absteigender Reihenfolge sortiert werden können.
Lassen Sie uns dieses Konzept anhand eines Beispiels erläutern.
Beispiel 1:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( " Liste in aufsteigender Reihenfolge: ", a ) ```
Ausgabe:
In diesem Beispiel wird die gegebene ungeordnete Liste mit Hilfe der Funktion " sort( ) " in aufsteigender Reihenfolge sortiert.
Beispiel 2:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( " Liste in absteigender Reihenfolge: ", a ) ```
Ausgabe
Im obigen Beispiel wird die gegebene ungeordnete Liste mit der Funktion " sort( reverse = True ) " in umgekehrter Reihenfolge sortiert.
Zeitkomplexität von Sortieralgorithmen
Die Zeitkomplexität gibt an, wie viel Zeit der Computer für die Ausführung eines bestimmten Algorithmus benötigt. Es gibt drei Arten von Zeitkomplexität.
- Schlimmster Fall: Maximale Zeit, die der Computer für die Ausführung des Programms benötigt.
- Durchschnittlicher Fall: Zeit, die der Computer zwischen dem Minimum und dem Maximum benötigt, um das Programm auszuführen.
- Bester Fall: Minimale Zeit, die der Computer benötigt, um das Programm auszuführen. Dies ist der beste Fall von Zeitkomplexität.
Komplexität Notationen
Große Oh-Notation, O: Die Big-Oh-Notation ist die offizielle Bezeichnung für die obere Schranke der Laufzeit von Algorithmen. Sie wird verwendet, um die Worst-Case-Zeitkomplexität zu messen, d. h. die Zeit, die ein Algorithmus maximal benötigt, um seine Aufgabe zu erfüllen.
Große Omega-Notation, : Die Big-Omega-Schreibweise ist der offizielle Weg, um die unterste Grenze der Laufzeit von Algorithmen zu beschreiben. Sie wird verwendet, um die Zeitkomplexität im besten Fall zu messen, d. h. die hervorragende Zeit, die ein Algorithmus benötigt.
Theta-Notation, : Die Thetaschreibweise ist die offizielle Methode, um beide Grenzen, d.h. die untere und die obere Grenze der Zeit, die der Algorithmus für die Fertigstellung benötigt, anzugeben.
Sortiermethoden in Python
Blase sortieren
Die Bubble-Sortierung ist die einfachste Art der Datensortierung, bei der die Brute-Force-Technik zum Einsatz kommt. Sie iteriert jedes Datenelement und vergleicht es mit anderen Elementen, um dem Benutzer die sortierten Daten zu liefern.
Nehmen wir ein Beispiel, um diese Technik zu verstehen:
- Wir haben ein Array mit den Elementen "10, 40, 7, 3, 15" und müssen dieses Array mit Hilfe der Bubble-Sortiermethode in Python in aufsteigender Reihenfolge anordnen.
- Der allererste Schritt besteht darin, das Array in der vorgegebenen Reihenfolge anzuordnen.
- In der " Iteration 1 " vergleichen wir das erste Element eines Arrays mit den anderen Elementen, eines nach dem anderen.
- Die roten Pfeile beschreiben den Vergleich der ersten Elemente mit den anderen Elementen eines Arrays.
- Wenn du bemerkst, dass " 10 " kleiner als " 40 " ist, bleibt es an der gleichen Stelle, aber das nächste Element " 7 " ist kleiner als " 10 ". Daher wird es ersetzt und kommt an die erste Stelle.
- Der obige Vorgang wird immer wieder durchgeführt, um die Elemente zu sortieren.
- In der " Iteration 2 " wird das zweite Element mit den anderen Elementen eines Arrays verglichen.
- Wenn das verglichene Element klein ist, wird es ersetzt, ansonsten bleibt es an der gleichen Stelle.
- In " Iteration 3 " wird das dritte Element mit den anderen Elementen eines Arrays verglichen.
- In der letzten " Iteration 4 " wird das vorletzte Element mit den anderen Elementen eines Arrays verglichen.
- In diesem Schritt wird das Array in aufsteigender Reihenfolge sortiert.
Programm für Blasensortierung
``` def Bubble_Sort(unsorted_list): for i in range(0,len(unsorted_list)-1): for j in range(len(unsorted_list)-1): if(unsorted_list[j]>unsorted_list[j+1]): temp_storage = unsorted_list[j] unsorted_list[j] = unsorted_list[j+1] unsorted_list[j+1] = temp_storage return unsorted_list unsorted_list = [5, 3, 8, 6, 7, 2] print("Unsorted List: ", unsorted_list) print("Sorted List using Bubble SortTechnik: ", Bubble_Sort(unsorted_list)) ```
Ausgabe
Zeitliche Komplexität der Bubble-Sortierung
- Schlimmster Fall: Die schlechteste Zeitkomplexität für Bubble Sort ist O( n 2).
- Durchschnittlicher Fall: Die durchschnittliche Zeitkomplexität für Bubble Sort beträgt O( n 2).
- Bester Fall: Die beste Zeitkomplexität für Bubble Sort ist O(n).
Vorteile
- Sie wird am häufigsten verwendet und ist einfach zu implementieren.
- Wir können die Datenelemente ohne Verbrauch von Kurzzeitspeicher austauschen.
- Es benötigt weniger Platz.
Benachteiligungen
- Bei einer großen Anzahl von großen Datenelementen war sie nicht sehr leistungsfähig.
- Es braucht n 2 Schritte für jede "n"-Anzahl von Datenelementen, die sortiert werden sollen.
- Sie ist für reale Anwendungen nicht wirklich geeignet.
Einfügen Sortieren
Die Einfügesortierung ist eine einfache Sortierungstechnik, die ähnlich wie das Sortieren von Spielkarten funktioniert. Die Einfügesortierung sortiert die Elemente, indem jedes Element einzeln mit dem anderen verglichen wird. Die Elemente werden ausgewählt und mit dem anderen Element vertauscht, wenn das Element größer oder kleiner als das andere ist.
Nehmen wir ein Beispiel
- Wir haben ein Array mit den Elementen "100, 50, 30, 40, 10".
- Zunächst ordnen wir das Array an und beginnen mit dem Vergleich.
- Im ersten Schritt wird " 100 " mit dem zweiten Element " 50 " verglichen. " 50 " wird mit " 100 " vertauscht, da es größer ist.
- Im zweiten Schritt wird wiederum das zweite Element " 100 " mit dem dritten Element " 30 " verglichen und vertauscht.
- Wenn Sie nun feststellen, dass "30" an erster Stelle steht, weil es wiederum kleiner ist als "50".
- Der Vergleich erfolgt bis zum letzten Element eines Arrays und am Ende erhalten wir die sortierten Daten.
Programm für Einlegesortierung
``` def InsertionSort(array): for i in range(1, len(array)): key_value = array[i] j = i-1 while j>= 0 and key_value <array[j] : array[j + 1] = array[j] j -= 1 array[j + 1] = key_value array = [11, 10, 12, 4, 5] print("Das unsortierte Array: ", array) InsertionSort(array) print ("Das sortierte Array mit Hilfe des Insertion Sort: ") for i in range(len(array)): print (array[i]) ```
Ausgabe
Zeitliche Komplexität der Einfügesortierung
- Schlimmster Fall: Die schlechteste Zeitkomplexität für Insertion sort ist O( n 2).
- Durchschnittlicher Fall: Die durchschnittliche Zeitkomplexität für Insertion sort ist O( n 2).
- Bester Fall: Die beste Zeitkomplexität für Insertion sort ist O(n).
Vorteile
- Sie ist einfach und leicht zu implementieren.
- Sie ist auch bei einer geringen Anzahl von Datenelementen sehr leistungsfähig.
- Sie benötigt keinen weiteren Platz für ihre Umsetzung.
Benachteiligungen
- Es ist nicht hilfreich, eine große Anzahl von Datenelementen zu sortieren.
- Im Vergleich zu anderen Sortierverfahren schneidet sie nicht gut ab.
Sortierung zusammenführen
Bei dieser Sortiermethode werden die Elemente nach dem Prinzip "Teile und herrsche" in einer bestimmten Reihenfolge sortiert. Bei der Sortierung mit Hilfe der Mischsortierung werden die Elemente in Hälften geteilt und dann sortiert. Nachdem alle Hälften sortiert wurden, werden die Elemente wieder zusammengefügt, um eine perfekte Reihenfolge zu bilden.
Nehmen wir ein Beispiel, um diese Technik zu verstehen
- Wir haben ein Array " 7, 3, 40, 10, 20, 15, 6, 5 ". Das Array enthält 7 Elemente. Wenn wir es in die Hälfte teilen ( 0 + 7 / 2 = 3 ).
- Im zweiten Schritt sehen Sie, dass die Elemente in zwei Teile geteilt sind, die jeweils 4 Elemente enthalten.
- Außerdem werden die Elemente nochmals geteilt und haben jeweils 2 Elemente.
- Dieser Vorgang wird so lange fortgesetzt, bis nur noch ein Element in einem Array vorhanden ist (siehe Schritt Nr. 4 in der Abbildung).
- Jetzt werden wir die Elemente sortieren und so zusammenfügen, wie wir sie aufgeteilt haben.
- In Schritt Nr. 5 haben wir festgestellt, dass 7 größer als 3 ist, also tauschen wir sie aus und verbinden sie im nächsten Schritt und umgekehrt.
- Am Ende werden Sie feststellen, dass unser Array in aufsteigender Reihenfolge sortiert wird.
Programm für Mischsortierung
``` def MergeSort(arr): if len(arr)> 1: middle = len(arr)//2 L = arr[:middle] R = arr[middle:] MergeSort(L) MergeSort(R) i = j = k = 0 while i <len(L) and j <len(R): if L[i] <R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i <len(L): arr[k] = L[i] i += 1 k += 1 while j <len(R): arr[k] = R[j] j += 1 k += 1 def PrintSortedList(arr): for i inrange(len(arr)): print(arr[i],) print() arr = [12, 11, 13, 5, 6, 7] print("Gegebenes Array ist", end="\n") PrintSortedList(arr) MergeSort(arr) print("Sortiertes Array ist: ", end="\n") PrintSortedList(arr) ```
Ausgabe
Zeitliche Komplexität der Mischsortierung
- Schlimmster Fall: Die schlechteste Zeitkomplexität für Merge Sort ist O( n log( n )).
- Durchschnittlicher Fall: Die durchschnittliche Zeitkomplexität für Merge Sort beträgt O( n log( n )).
- Bester Fall: Die beste Zeitkomplexität für Merge Sort ist O( n log( n )).
Vorteile
- Die Dateigröße spielt bei dieser Sortiermethode keine Rolle.
- Diese Technik eignet sich für Daten, auf die im Allgemeinen in einer bestimmten Reihenfolge zugegriffen wird. Zum Beispiel, verknüpfte Listen, Bandlaufwerk, usw.
Benachteiligungen
- Im Vergleich zu anderen Sortierverfahren benötigt es mehr Platz.
- Es ist vergleichsweise weniger effizient als andere.
Schnelles Sortieren
Bei der Schnellsortierung werden die Elemente einer Liste oder eines Arrays nach der Methode "Teile und herrsche" sortiert, wobei die Pivotelemente ausgewählt und die Elemente nach dem ausgewählten Pivotelement sortiert werden.
Zum Beispiel
- Wir erhalten ein Array mit den Elementen " 1,8,3,9,4,5,7 ".
- Nehmen wir an, dass " 7 " ein Pilotelement ist.
- Nun teilen wir das Feld so auf, dass die linke Seite die Elemente enthält, die kleiner als das Pivotelement " 7 " sind, und die rechte Seite die Elemente, die größer als das Pivotelement " 7 " sind.
- Wir haben jetzt zwei Arrays "1,3,4,5" und "8, 9".
- Auch hier müssen wir die beiden Arrays genauso aufteilen wie oben, mit dem Unterschied, dass die Pivot-Elemente geändert werden.
- Wir müssen die Arrays so lange teilen, bis wir ein einzelnes Element im Array haben.
- Sammeln Sie am Ende alle Pivot-Elemente in einer Reihenfolge von links nach rechts und Sie erhalten das sortierte Array.
Programm für Schnellsortierung
``` def Array_Partition( arr, niedrigste, höchste ): i = ( niedrigste-1 ) pivot_element = arr[ höchste ] for j in range( niedrigste, höchste ): if arr[ j ] <= pivot_element: i = i+1 arr[ i ], arr[ j ] = arr[ j ], arr[ i ] arr[ i+1 ], arr[ höchste ] = arr[ höchste ], arr[ i+1 ] return ( i+1 ) def QuickSort( arr, niedrigste, höchste ): if len( arr ) == 1: return arr if niedrigste <höchste: pi = Array_Partition(arr, niedrigste, höchste ) QuickSort( arr, niedrigste, pi-1 ) QuickSort( arr, pi+1, höchste ) arr = [ 9, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Unsortiertes Array: ", arr ) QuickSort( arr, 0, n-1 ) print( " Sortiertes Array mit Quick Sort: " ) for i in range( n ): print( " %d " % arr[ i ] ) ```
Ausgabe
Zeitliche Komplexität von Quick sort
- Schlimmster Fall: Die schlechteste Zeitkomplexität für Quick sort ist O( n 2).
- Durchschnittlicher Fall: Die durchschnittliche Zeitkomplexität für Quick sort beträgt O( n log( n )).
- Bester Fall: Die beste Zeitkomplexität für Quick sort ist O( n log( n )).
Vorteile
- Er ist als der beste Sortieralgorithmus in Python bekannt.
- Sie ist nützlich bei der Verarbeitung großer Datenmengen.
- Es wird kein zusätzlicher Platz benötigt.
Benachteiligungen
- Seine Worst-Case-Komplexität ist vergleichbar mit der Komplexität von Bubble Sort und Insertion Sort.
- Diese Sortiermethode ist nicht sinnvoll, wenn wir die Liste bereits sortiert haben.
Haufensortierung
Bei der Haufensortierung wird das größte Element eines Arrays immer auf die Wurzel des Baums gelegt und dann mit der Wurzel mit den Blattknoten verglichen.
Zum Beispiel:
- Wir haben ein Array mit den Elementen "40, 100, 30, 50, 10".
- Unter " Schritt 1 " haben wir einen Baum nach dem Vorhandensein der Elemente im Array erstellt.
- In " Schritt 2 " Wir machen einen maximalen Haufen, d.h. wir ordnen die Elemente in absteigender Reihenfolge an. Das größte Element befindet sich oben (Wurzel) und das kleinste Element unten (Blattknoten). Das gegebene Array wird " 100, 50, 30, 40, 10 ".
- Unter " Schritt 3 " Mit der Methode "Minimum Heap" können wir die minimalen Elemente eines Arrays ermitteln und erhalten so das Maximum und das Minimum der Elemente.
- Unter " Schritt 4 " Durch die gleichen Schritte erhalten wir das sortierte Array.
Programm für Heap-Sortierung
``` def HeapSortify( arr, n, i ): größeres_Element = i left = 2 * i + 1 right = 2 * i + 2 if left <n und arr[ größeres_Element ] <arr[ left ]: größeres_Element = left if right <n und arr[ größeres_Element ] <arr[ right ]: größeres_Element = right if größeres_Element != i: arr[ i ], arr[ größeres_Element ] = arr[ größeres_Element ], arr[ i ] HeapSortify( arr, n, größeres_Element ) def HeapSortify( arr, n, größeres_Element )): n = len( arr ) for i in range( n//2 - 1, -1, -1 ): HeapSortify( arr, n, i ) for i in range( n-1, 0, -1 ): arr[ i ], arr[ 0 ] = arr[ 0 ], arr[ i ] HeapSortify( arr, i, 0 ) arr = [ 11, 10, 12, 4, 5, 6 ] print( " Das unsortierte Array ist: ", arr ) HeapSort( arr ) n = len( arr ) print( " Das sortierte Array sortiert durch Heap Sort: " ) for i in range( n ): print( arr[ i ] ) ```
Ausgabe
Zeitkomplexität der Heap-Sortierung
- Schlimmster Fall: Die schlechteste Zeitkomplexität für Heap-Sortierung ist O( n log( n )).
- Durchschnittlicher Fall: Die durchschnittliche Zeitkomplexität für Heap-Sort ist O( n log( n )).
- Bester Fall: Die beste Zeitkomplexität für Heap-Sortierung istO( n log( n )).
Vorteile
- Er wird vor allem wegen seiner Produktivität eingesetzt.
- Er kann als In-Place-Algorithmus implementiert werden.
- Es erfordert keine große Lagerung.
Benachteiligungen
- Benötigt Platz für die Sortierung der Elemente.
- Er bildet den Baum zum Sortieren der Elemente.
Vergleich zwischen den Sortiertechniken
Sortierverfahren | Komplexität der Zeit im besten Fall | Durchschnittliche Komplexität der Fallzeit | Zeitliche Komplexität im schlimmsten Fall | Raumkomplexität | Stabilität | In - Ort |
---|---|---|---|---|---|---|
Blase sortieren | O(n) | O(n2) | O(n2) | O(1) | Ja | Ja |
Einfügen sortieren | O(n) | O(n2) | O(n2) | O(1) | Ja | Ja |
Schnelles Sortieren | O(n log(n)) | O(n log(n)) | O(n2) | O(N) | Nein | Ja |
Sortierung zusammenführen | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(N) | Ja | Nein |
Haufensortierung | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) | Nein | Ja |
In der obigen Vergleichstabelle steht "O" für die oben erläuterte Big-Oh-Notation, während "n" und "N" die Größe der Eingabe bedeuten.
Häufig gestellte Fragen
F #1) Was ist sort () in Python?
Antwort: In Python ist sort() eine Funktion, die verwendet wird, um die Listen oder Arrays in einer bestimmten Reihenfolge zu sortieren. Diese Funktion erleichtert den Prozess der Sortierung während der Arbeit an den großen Projekten. Es ist sehr hilfreich für die Entwickler.
F #2) Wie kann man in Python sortieren?
Antwort: Python bietet verschiedene Sortierverfahren, die zum Sortieren der Elemente verwendet werden. Zum Beispiel, Schnellsortierung, Mischsortierung, Blasensortierung, Einfügesortierung usw. Alle Sortierverfahren sind effizient und leicht verständlich.
F #3) Wie funktioniert Python sort ()?
Antwort: Die sort()-Funktion nimmt das gegebene Array als Eingabe vom Benutzer und sortiert es in einer bestimmten Reihenfolge unter Verwendung des Sortieralgorithmus. Die Auswahl des Algorithmus hängt von der Wahl des Benutzers ab. Benutzer können Schnellsortierung, Mischsortierung, Blasensortierung, Einfügesortierung usw. je nach den Bedürfnissen des Benutzers verwenden.
Schlussfolgerung
Im obigen Tutorial haben wir die Sortiertechnik in Python zusammen mit den allgemeinen Sortiertechniken besprochen.
- Blase sortieren
- Einfügen Sortieren
- Schnelles Sortieren
Wir haben uns über ihre zeitliche Komplexität und ihre Vor- und Nachteile informiert und alle oben genannten Techniken miteinander verglichen.