In diesem Artikel besprechen wir den Auswahlsortierungsalgorithmus. Das Arbeitsverfahren der Auswahlsortierung ist ebenfalls einfach. Dieser Artikel wird für Studierende sehr hilfreich und interessant sein, da sie in ihren Prüfungen möglicherweise mit Auswahlfragen konfrontiert werden. Daher ist es wichtig, das Thema zu diskutieren.

Bei der Auswahlsortierung wird in jedem Durchgang der kleinste Wert unter den unsortierten Elementen des Arrays ausgewählt und an der entsprechenden Position in das Array eingefügt. Es ist auch der einfachste Algorithmus. Es handelt sich um einen In-Place-Vergleichssortierungsalgorithmus. Bei diesem Algorithmus wird das Array in zwei Teile geteilt, der erste ist der sortierte Teil und der andere ist der unsortierte Teil. Zunächst ist der sortierte Teil des Arrays leer und der unsortierte Teil ist das angegebene Array. Der sortierte Teil wird links platziert, während der unsortierte Teil rechts platziert wird.

Bei der Auswahlsortierung wird das erste kleinste Element aus dem unsortierten Array ausgewählt und an der ersten Position platziert. Danach wird das zweitkleinste Element ausgewählt und an der zweiten Position platziert. Der Vorgang wird fortgesetzt, bis das Array vollständig sortiert ist.

Die durchschnittliche und Worst-Case-Komplexität der Auswahlsortierung beträgt An²) , Wo N ist die Anzahl der Artikel. Aus diesem Grund ist es nicht für große Datenmengen geeignet.

Die Auswahlsortierung wird im Allgemeinen verwendet, wenn –

• Ein kleines Array soll sortiert werden
• Die Umtauschkosten spielen keine Rolle
• Es ist obligatorisch, alle Elemente zu überprüfen

Sehen wir uns nun den Algorithmus der Auswahlsortierung an.

Algorithmus

 SELECTION SORT(arr, n) Step 1: Repeat Steps 2 and 3 for i = 0 to n-1 Step 2: CALL SMALLEST(arr, i, n, pos) Step 3: SWAP arr[i] with arr[pos] [END OF LOOP] Step 4: EXIT SMALLEST (arr, i, n, pos) Step 1: [INITIALIZE] SET SMALL = arr[i] Step 2: [INITIALIZE] SET pos = i Step 3: Repeat for j = i+1 to n if (SMALL > arr[j]) SET SMALL = arr[j] SET pos = j [END OF if] [END OF LOOP] Step 4: RETURN pos 

Funktionsweise des Auswahlsortierungsalgorithmus

Sehen wir uns nun die Funktionsweise des Auswahlsortierungsalgorithmus an.

Um die Funktionsweise des Auswahlsortieralgorithmus zu verstehen, nehmen wir ein unsortiertes Array. Anhand eines Beispiels lässt sich die Auswahlsortierung leichter verstehen.

Die Elemente des Arrays seien -

Für die erste Position im sortierten Array soll nun das gesamte Array sequentiell durchsucht werden.

Derzeit, 12 Wird an der ersten Position gespeichert und nach dem Durchsuchen des gesamten Arrays wird dies festgestellt 8 ist der kleinste Wert.

Websites wie coomeet

Tauschen Sie also 12 durch 8 aus. Nach der ersten Iteration erscheint 8 an der ersten Position im sortierten Array.

Für die zweite Position, an der derzeit 29 gespeichert ist, scannen wir erneut nacheinander die restlichen Elemente des unsortierten Arrays. Nach dem Scannen stellen wir fest, dass 12 das zweitniedrigste Element im Array ist, das an zweiter Position erscheinen sollte.

Tauschen Sie nun 29 durch 12 aus. Nach der zweiten Iteration erscheint 12 an der zweiten Position im sortierten Array. Nach zwei Iterationen werden also die beiden kleinsten Werte sortiert am Anfang platziert.

Der gleiche Vorgang wird auf die übrigen Array-Elemente angewendet. Nun zeigen wir eine bildliche Darstellung des gesamten Sortiervorgangs.

Jetzt ist das Array vollständig sortiert.

Komplexität der Auswahlsortierung

Sehen wir uns nun die zeitliche Komplexität der Auswahlsortierung im besten Fall, im Durchschnittsfall und im schlechtesten Fall an. Wir werden auch die räumliche Komplexität der Auswahlsortierung sehen.

1. Zeitkomplexität

Beste Fallkomplexität -Dies geschieht, wenn keine Sortierung erforderlich ist, d. h. das Array bereits sortiert ist. Die Zeitkomplexität der Auswahlsortierung beträgt im besten Fall An²) .Durchschnittliche Fallkomplexität -Es tritt auf, wenn die Array-Elemente in einer durcheinandergebrachten Reihenfolge vorliegen, die nicht richtig aufsteigend und nicht richtig absteigend ist. Die durchschnittliche Fallzeitkomplexität der Auswahlsortierung beträgt An²) .Worst-Case-Komplexität -Es tritt auf, wenn die Array-Elemente in umgekehrter Reihenfolge sortiert werden müssen. Das bedeutet, dass Sie die Array-Elemente in aufsteigender Reihenfolge sortieren müssen, die Elemente jedoch in absteigender Reihenfolge. Die zeitliche Komplexität der Auswahlsortierung im schlimmsten Fall beträgt An²) .

2. Raumkomplexität

• Die räumliche Komplexität der Auswahlsortierung beträgt O(1). Dies liegt daran, dass bei der Auswahlsortierung eine zusätzliche Variable zum Austauschen erforderlich ist.

Implementierung der Auswahlsortierung

Sehen wir uns nun die Auswahlprogramme in verschiedenen Programmiersprachen an.

Programm: Schreiben Sie ein Programm, um die Auswahlsortierung in der Sprache C zu implementieren.

 #include void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 17 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting elements are - 
'); printarr(a, n); selection(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-7.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C++ language.</p> <pre> #include using namespace std; void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 15 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i cout<< a[i] <<' '; main() a[]="{" 80, 10, 29, 11, 8, 30, }; n="sizeof(a)" sizeof(a[0]); 'before sorting elements are - '<<endl; printarr(a, n); selection(a, '
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-8.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C# language.</p> <pre> using System; class Selection { static void selection(int[] arr) { int i, j, small; int n = arr.Length; for (i = 0; i <n-1; i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } static void printarr(int[] a) * function to print i; n="a.Length;" (i="0;" i console.write(a[i] + ' '); main() int[] a="{" 85, 50, 29, 18, 7, 30, 3}; console.write('before sorting elements are - printarr(a); selection(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-9.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in python.</p> <pre> def selection(a): # Function to implement selection sort for i in range(len(a)): # Traverse through all array elements small = i # minimum element in unsorted array for j in range(i+1, len(a)): if a[small] &gt; a[j]: small = j # Swap the found minimum element with # the first element a[i], a[small] = a[small], a[i] def printArr(a): # function to print the array for i in range(len(a)): print (a[i], end = &apos; &apos;) a = [69, 14, 1, 50, 59] print(&apos;Before sorting array elements are - &apos;) printArr(a) selection(a) print(&apos;
After sorting array elements are - &apos;) selection(a) printArr(a) </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-10.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in Java.</p> <pre> public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println('
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo 'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;></pre></n-1;></pre></n-1;></pre></n-1;>

Ausgabe:

Programm: Schreiben Sie ein Programm, um die Auswahlsortierung in Java zu implementieren.

 public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + \' \'); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println(\'
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println(\'
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo \' \'; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo \'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;>

Ausgabe:

Nach der Ausführung des obigen Codes lautet die Ausgabe:

Das ist also alles über den Artikel. Ich hoffe, der Artikel ist hilfreich und informativ für Sie.

Dieser Artikel beschränkte sich nicht nur auf den Algorithmus. Wir haben auch die Komplexität, Funktionsweise und Implementierung der Auswahlsortierung in verschiedenen Programmiersprachen besprochen.