Auswahlsortierung ist ein einfacher und effizienter Sortieralgorithmus, der wiederholt das kleinste (oder größte) Element aus dem unsortierten Teil der Liste auswählt und es in den sortierten Teil der Liste verschiebt.

Der Algorithmus wählt wiederholt das kleinste (oder größte) Element aus dem unsortierten Teil der Liste aus und vertauscht es mit dem ersten Element des unsortierten Teils. Dieser Vorgang wird für den verbleibenden unsortierten Teil wiederholt, bis die gesamte Liste sortiert ist.

Wie funktioniert der Auswahlsortierungsalgorithmus?

Betrachten wir als Beispiel das folgende Array: arr[] = {64, 25, 12, 22, 11}

Erster Pass:

• Für die erste Position im sortierten Array wird das gesamte Array sequentiell vom Index 0 bis 4 durchlaufen. Die erste Position wo 64 wird derzeit gespeichert, nach dem Durchlaufen des gesamten Arrays ist das klar elf ist der niedrigste Wert.
• Ersetzen Sie also 64 durch 11. Nach einer Iteration elf , der zufällig der kleinste Wert im Array ist, erscheint in der Regel an der ersten Position der sortierten Liste.

Auswahlsortieralgorithmus | Tauschen Sie das erste Element mit dem Minimum im Array aus

Zweiter Durchgang:

• Für die zweite Position, an der 25 vorhanden ist, durchlaufen Sie den Rest des Arrays erneut nacheinander.
• Nach der Durchquerung fanden wir das 12 ist der zweitniedrigste Wert im Array und sollte an zweiter Stelle im Array erscheinen, also diese Werte vertauschen.

Auswahlsortieralgorithmus | Austausch von i=1 mit dem nächsten minimalen Element

Dritter Durchgang:

• Nun zum dritten Platz, wo 25 erneut vorhanden ist, durchquere den Rest des Arrays und finde den drittkleinsten im Array vorhandenen Wert.
• Beim Überqueren 22 stellte sich als drittkleinster Wert heraus und sollte an dritter Stelle im Array erscheinen, also vertauschen 22 mit Element an dritter Position.

Auswahlsortieralgorithmus | Vertauschen von i=2 mit dem nächsten minimalen Element

Vierter Durchgang:

• In ähnlicher Weise durchqueren Sie für die vierte Position den Rest des Arrays und finden das viertkleinste Element im Array
• Als 25 ist der viertniedrigste Wert und wird daher an vierter Stelle platziert.

Auswahlsortieralgorithmus | i=3 mit dem nächsten minimalen Element austauschen

Fünfter Durchgang:

• Zuletzt wird der größte im Array vorhandene Wert automatisch an der letzten Position im Array platziert
• Das resultierende Array ist das sortierte Array.

Auswahlsortieralgorithmus | Erforderliches sortiertes Array

Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:

// C++ program for implementation of // selection sort #include  using namespace std; // Function for Selection sort void selectionSort(int arr[], int n) {  int i, j, min_idx;  // One by one move boundary of  // unsorted subarray  for (i = 0; i < n - 1; i++) {  // Find the minimum element in  // unsorted array  min_idx = i;  for (j = i + 1; j < n; j++) {  if (arr[j] < arr[min_idx])  min_idx = j;  }  // Swap the found minimum element  // with the first element  if (min_idx != i)  swap(arr[min_idx], arr[i]);  } } // Function to print an array void printArray(int arr[], int size) {  int i;  for (i = 0; i < size; i++) {  cout << arr[i] << ' ';  cout << endl;  } } // Driver program int main() {  int arr[] = { 64, 25, 12, 22, 11 };  int n = sizeof(arr) / sizeof(arr[0]);  // Function Call  selectionSort(arr, n);  cout << 'Sorted array: 
';  printArray(arr, n);  return 0; } // This is code is contributed by rathbhupendra>

// C program for implementation of selection sort #include  void swap(int *xp, int *yp) {  int temp = *xp;  *xp = *yp;  *yp = temp; } void selectionSort(int arr[], int n) {  int i, j, min_idx;  // One by one move boundary of unsorted subarray  for (i = 0; i < n-1; i++)  {  // Find the minimum element in unsorted array  min_idx = i;  for (j = i+1; j < n; j++)  if (arr[j] < arr[min_idx])  min_idx = j;  // Swap the found minimum element with the first element  if(min_idx != i)  swap(&arr[min_idx], &arr[i]);  } } /* Function to print an array */ void printArray(int arr[], int size) {  int i;  for (i=0; i < size; i++)  printf('%d ', arr[i]);  printf('
'); } // Driver program to test above functions int main() {  int arr[] = {64, 25, 12, 22, 11};  int n = sizeof(arr)/sizeof(arr[0]);  selectionSort(arr, n);  printf('Sorted array: 
');  printArray(arr, n);  return 0; }>

// Java program for implementation of Selection Sort import java.io.*; public class SelectionSort {  void sort(int arr[])  {  int n = arr.length;  // One by one move boundary of unsorted subarray  for (int i = 0; i < n-1; i++)  {  // Find the minimum element in unsorted array  int min_idx = i;  for (int j = i+1; j < n; j++)  if (arr[j] < arr[min_idx])  min_idx = j;  // Swap the found minimum element with the first  // element  int temp = arr[min_idx];  arr[min_idx] = arr[i];  arr[i] = temp;  }  }  // Prints the array  void printArray(int arr[])  {  int n = arr.length;  for (int i=0; i

# Python program for implementation of Selection # Sort A = [64, 25, 12, 22, 11] # Traverse through all array elements for i in range(len(A)-1): # Find the minimum element in remaining  # unsorted array min_idx = i for j in range(i+1, len(A)): if A[min_idx]>A[j]: min_idx = j # Tauschen Sie das gefundene minimale Element mit # dem ersten Element aus A[i], A[min_idx] = A[min_idx], A[i] # Treibercode zum Testen oben print ('Sorted array ') für i in range(len(A)): print(A[i],end=' ')>

// C# program for implementation  // of Selection Sort using System; class GFG {   static void sort(int []arr)  {  int n = arr.Length;  // One by one move boundary of unsorted subarray  for (int i = 0; i < n - 1; i++)  {  // Find the minimum element in unsorted array  int min_idx = i;  for (int j = i + 1; j < n; j++)  if (arr[j] < arr[min_idx])  min_idx = j;  // Swap the found minimum element with the first  // element  int temp = arr[min_idx];  arr[min_idx] = arr[i];  arr[i] = temp;  }  }  // Prints the array  static void printArray(int []arr)  {  int n = arr.Length;  for (int i=0; i

>

 // PHP program for implementation  // of selection sort  function selection_sort(&$arr, $n) { for($i = 0; $i < $n ; $i++) { $low = $i; for($j = $i + 1; $j < $n ; $j++) { if ($arr[$j] < $arr[$low]) { $low = $j; } } // swap the minimum value to $ith node if ($arr[$i]>$arr[$low]) { $tmp = $arr[$i]; $arr[$i] = $arr[$low]; $arr[$low] = $tmp; } } } // Treibercode $arr = array(64, 25, 12, 22, 11); $len = count($arr); Selection_sort($arr, $len); echo 'Sortiertes Array: 
'; für ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed  // by Deepika Gupta.  ?>>

Sorted array: 11 12 22 25 64>

Komplexitätsanalyse der Auswahlsortierung

Zeitkomplexität: Die zeitliche Komplexität von Selection Sort beträgt AN ² ) da es zwei verschachtelte Schleifen gibt:

• Eine Schleife, um ein Element des Arrays einzeln auszuwählen = O(N)
• Eine weitere Schleife zum Vergleich dieses Elements mit jedem anderen Array-Element = O(N)
• Daher Gesamtkomplexität = O(N) * O(N) = O(N*N) = O(N²)

Hilfsraum: O(1), da der einzige zusätzliche Speicher für temporäre Variablen beim Austauschen zweier Werte im Array verwendet wird. Die Auswahlsortierung führt nie mehr als O(N) Swaps durch und kann nützlich sein, wenn das Schreiben in den Speicher kostspielig ist.

Javascript-Dropdown

Vorteile des Auswahlsortierungsalgorithmus

• Einfach und leicht verständlich.
• Funktioniert gut mit kleinen Datensätzen.

Nachteile des Auswahlsortierungsalgorithmus

• Die Auswahlsortierung hat im schlechtesten und durchschnittlichen Fall eine zeitliche Komplexität von O(n^2).
• Funktioniert bei großen Datensätzen nicht gut.
• Behält die relative Reihenfolge von Elementen mit gleichen Schlüsseln nicht bei, was bedeutet, dass es nicht stabil ist.

Häufig gestellte Fragen zur Auswahlsortierung

Q1. Ist der Auswahlsortierungsalgorithmus stabil?

Die Standardimplementierung des Auswahlsortierungsalgorithmus ist nicht stabil . Es kann jedoch stabil gemacht werden. Bitte sehen Sie sich ... an stabile Auswahlsortierung für Details.

Q2. Ist der Auswahlsortierungsalgorithmus vorhanden?

Ja, der Auswahlsortierungsalgorithmus ist ein In-Place-Algorithmus, da er keinen zusätzlichen Speicherplatz benötigt.