So verwenden Sie die Auswahlsortierung
Die Auswahlsortierung ist eine Sortiertechnik, die ein Listenelement auswählt und dann seinen Platz mit einem anderen vertauscht. Es wählt das größte Element aus und tauscht es dann mit einem Element im höchsten Index der Liste aus.
Der Algorithmus macht dies wiederholt, bis die Liste sortiert ist. Wenn Sie sich nicht ganz sicher sind, wie die Auswahlsortierung funktioniert, sind Sie hier richtig. Wir werden es im Folgenden genauer erklären und Ihnen ein Beispiel zeigen.
Auswahl sortieren: Ein genauerer Blick
Angenommen, Sie haben die Liste: [39, 82, 2, 51, 30, 42, 7]. Um die Liste mit Auswahlsortierung zu sortieren, müssten Sie zuerst die höchste Zahl darin finden.
In der gegebenen Liste ist diese Zahl 82. Tausche 82 mit der Zahl im höchsten Index (dh 7) aus.
Nach dem ersten Durchlauf lautet die neue Listenreihenfolge: [39, 7, 2, 51, 30, 42, 82]. Jedes Mal, wenn der Algorithmus die gesamte Liste durchläuft, wird das als "Pass" bezeichnet.
Beachten Sie, dass die Liste während des Sortiervorgangs eine sortierte Unterliste und eine unsortierte Unterliste verwaltet.
Die ursprüngliche Liste beginnt mit einer sortierten Liste von null Elementen und einer unsortierten Liste aller Elemente. Dann hat es nach dem ersten Durchgang eine sortierte Liste mit nur der Nummer 82.
Beim zweiten Durchlauf ist die höchste Nummer in der unsortierten Unterliste 51. Diese Nummer wird mit 42 ausgetauscht, um die neue Listenreihenfolge unten anzugeben:
[39, 7, 2, 42, 30, 51, 82].
Der Vorgang wird wiederholt, bis die gesamte Liste sortiert ist. Die folgende Abbildung fasst den gesamten Prozess zusammen:
Die Zahlen in fettem Schwarz zeigen den höchsten Listenwert zu diesem Zeitpunkt. Diejenigen in Grün zeigen die sortierte Unterliste an.
Algorithmusanalyse
Um die Komplexität (mit Big-O-Notation) dieses Algorithmus zu ermitteln, gehen Sie wie folgt vor:
Beim ersten Durchlauf werden (n-1) Vergleiche durchgeführt. Beim zweiten Durchgang (n-2). Beim dritten Durchlauf (n-3) und so weiter bis zum (n-1)ten Durchlauf, der nur einen Vergleich macht.
Die folgenden Vergleiche zusammenfassend ergibt:
(n-1)+ (n-1)+ (n-1)+…+1 = ((n-1)n)/2.
Daher ist die Auswahlsortierung O(n 2 ).
Codeimplementierung
Der Code zeigt Funktionen, die Sie zum Durchführen einer Auswahlsortierung mit Python und Java verwenden können.
Python:
def selectionSort(mylist):
for x in range(len(mylist) - 1, 0, -1):
max_idx = 0
for posn in range(1, x + 1):
if mylist[posn] > mylist[max_idx]:
max_idx = posn
temp = mylist[x]
mylist[x] = mylist[max_idx]
mylist[max_idx] = tempJava:
void selectionSort(int my_array[]){
for (int x = 0; x < my_array.length - 1; x++)
{
int index = x;
for (int y = x + 1; y < my_array.length; y++){
if (my_array[y] < my_array[index]){
index = y; // find lowest index
}
}
int temp = my_array[index]; // temp is a temporary storage
my_array[index] = my_array[x];
my_array[x] = temp;
}}Wechseln von Auswahlsortierung zu Zusammenführungssortierung
Wie die obige Algorithmusanalyse gezeigt hat, ist der Auswahlsortierungsalgorithmus O(n 2 ). Es hat eine exponentielle Komplexität und ist daher für sehr große Datensätze ineffizient.
Ein viel besser zu verwendender Algorithmus wäre Merge-Sort mit einer Komplexität von O(nlogn). Und jetzt wissen Sie, wie die Auswahlsortierung funktioniert. Als nächstes sollte auf Ihrer Studienliste für Sortieralgorithmen die Zusammenführungssortierung stehen.