In diesem Tutorial erfahren Sie, wie die Auswahlsortierung funktioniert. Außerdem finden Sie Arbeitsbeispiele für die Auswahlsortierung in C, C ++, Java und Python.
Die Auswahlsortierung ist ein Algorithmus, der das kleinste Element aus einer unsortierten Liste in jeder Iteration auswählt und dieses Element am Anfang der unsortierten Liste platziert.
Wie funktioniert die Auswahlsortierung?
- Stellen Sie das erste Element als ein
minimum.
Wählen Sie mindestens das erste Element aus - Vergleiche
minimummit dem zweiten Element. Wenn das zweite Element kleiner als istminimum, weisen Sie das zweite Element als zuminimum.
Vergleicheminimummit dem dritten Element. Wenn das dritte Element kleiner ist, weisen Sieminimumdem dritten Element zu, andernfalls tun Sie nichts. Der Vorgang wird bis zum letzten Element fortgesetzt.
Vergleichen Sie das Minimum mit den übrigen Elementen - Wird nach jeder Iteration
minimuman die Spitze der unsortierten Liste gesetzt.
Tauschen Sie die erste mit Minimum aus - Für jede Iteration beginnt die Indizierung mit dem ersten unsortierten Element. Die Schritte 1 bis 3 werden wiederholt, bis alle Elemente an den richtigen Positionen platziert sind.
Die erste Iteration 
Die zweite Iteration 
Die dritte Iteration 
Die vierte Iteration
Auswahl-Sortier-Algorithmus
selectionSort (Array, Größe) wiederholt (Größe - 1) und setzt das erste unsortierte Element als Minimum für jedes der unsortierten Elemente, wenn element <currentMinimum das Element als neues Minimum für den Swap-Minimum mit der ersten unsortierten Position setzt. endSort
Beispiele für Python, Java und C / C ++
Python Java C C ++ # Selection sort in Python def selectionSort(array, size): for step in range(size): min_idx = step for i in range(step + 1, size): # to sort in descending order, change> to < in this line # select the minimum element in each loop if array(i) < array(min_idx): min_idx = i # put min at the correct position (array(step), array(min_idx)) = (array(min_idx), array(step)) data = (-2, 45, 0, 11, -9) size = len(data) selectionSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Selection sort in Java import java.util.Arrays; class SelectionSort ( void selectionSort(int array()) ( int size = array.length; for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) ( min_idx = i; ) ) // put min at the correct position int temp = array(step); array(step) = array(min_idx); array(min_idx) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( 20, 12, 10, 15, 2 ); SelectionSort ss = new SelectionSort(); ss.selectionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Selection sort in C #include // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); printf("Sorted array in Acsending Order:"); printArray(data, size); )
// Selection sort in C++ #include using namespace std; // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); cout << "Sorted array in Acsending Order:"; printArray(data, size); )
Komplexität
| Zyklus | Anzahl der Vergleiche |
|---|---|
| 1 | (n-1) |
| 2 .. | (n-2) |
| 3 .. | (n-3) |
| … | … |
| letzte | 1 |
Anzahl der Vergleiche: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2fast gleich .n2
Komplexität =O(n2)
Wir können die Komplexität auch analysieren, indem wir einfach die Anzahl der Schleifen beobachten. Es gibt 2 Schleifen, also ist die Komplexität .n*n = n2
Zeitkomplexität:
- Worst-Case-Komplexität: Wenn wir in aufsteigender Reihenfolge sortieren möchten und das Array in absteigender Reihenfolge ist, tritt der Worst-Case auf.
O(n2) - Best-Case-Komplexität: Tritt auf, wenn das Array bereits sortiert ist
O(n2) - Durchschnittliche Fallkomplexität: Sie tritt auf, wenn die Elemente des Arrays in einer durcheinandergebrachten Reihenfolge sind (weder aufsteigend noch absteigend).
O(n2)
Die zeitliche Komplexität der Auswahlsortierung ist in allen Fällen gleich. Bei jedem Schritt müssen Sie das minimale Element finden und an der richtigen Stelle platzieren. Das minimale Element ist erst bekannt, wenn das Ende des Arrays nicht erreicht ist.
Raumkomplexität:
Die Raumkomplexität ist darauf zurückzuführen, O(1)dass eine zusätzliche Variable tempverwendet wird.
Auswahl Sortieranwendungen
Die Auswahlsortierung wird verwendet, wenn:
- Eine kleine Liste ist zu sortieren
- Die Kosten für den Austausch spielen keine Rolle
- Die Überprüfung aller Elemente ist obligatorisch
- Die Kosten für das Schreiben in einen Speicher sind wie im Flash-Speicher (die Anzahl der Schreibvorgänge / Swaps ist
O(n)im Vergleich zur Blasensortierung).O(n2)
