Menü

Auswahl In C ++ mit Beispielen sortieren

selection sort c with examples

Versuchen Sie Unser Instrument, Um Probleme Zu Beseitigen

Ein detaillierter Blick auf die Auswahlsortierung in C ++ mit Beispielen.

Wie der Name selbst schon sagt, wählt die Auswahlsortiertechnik zuerst das kleinste Element im Array aus und tauscht es gegen das erste Element im Array aus.

Als nächstes wird das zweitkleinste Element im Array gegen das zweite Element ausgetauscht. Somit wird für jeden Durchgang das kleinste Element im Array ausgewählt und an die richtige Position gebracht, bis das gesamte Array sortiert ist.

=> Lesen Sie hier den perfekten C ++ - Schulungsleitfaden.

Auswahl Sortieren

Was du lernen wirst:

Einführung

Die Auswahlsortierung ist eine recht einfache Sortiertechnik, da bei dieser Technik nur das kleinste Element in jedem Durchgang gefunden und an der richtigen Position platziert wird.

Die Auswahlsortierung funktioniert effizient, wenn die zu sortierende Liste klein ist, ihre Leistung jedoch stark beeinträchtigt wird, da die zu sortierende Liste größer wird.

Daher können wir sagen, dass eine Auswahlsortierung für größere Datenlisten nicht ratsam ist.

Allgemeiner Algorithmus

Der allgemeine Algorithmus für die Auswahlsortierung ist unten angegeben:

Wo finden Sie den Netzwerksicherheitsschlüssel?

Auswahlsortierung (A, N)

Schritt 1 : Wiederholen Sie die Schritte 2 und 3 für K = 1 bis N-1
Schritt 2 : Routine kleinste aufrufen (A, K, N, POS)
Schritt 3 : Tauschen Sie A (K) mit A (POS)
(Ende der Schleife)
Schritt 4 : AUSFAHRT

Routine kleinste (A, K, N, POS)

  • Schritt 1 : (initialisieren) setze kleinstesElem = A (K)
  • Schritt 2 : (initialisieren) setze POS = K.
  • Schritt 3 : für J = K + 1 bis N -1 wiederholen
    wenn kleinstesElem> A (J)
    setze kleinstesElem = A (J)
    setze POS = J.
    (wenn Ende)
    (Ende der Schleife)
  • Schritt 4 : POS zurückgeben

Pseudocode für Auswahlsortierung

Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j)

Ein Beispiel zur Veranschaulichung dieses Auswahlsortieralgorithmus ist unten gezeigt.

Illustration

Auswahl Sortierung Abbildung

Pass2

Pass3

Pass4

Die tabellarische Darstellung für diese Abbildung ist unten dargestellt:

Unsortierte ListeKleinstes ElementSortierte Liste
{18,10,7,20,2}zwei{}
{18,10,7,20}7{zwei}
{18,10,20}10{2.7}
{18.20}18{2,7,10)
{zwanzig}zwanzig{2,7,10,18}
{}{2,7,10,18,20}

Aus der Abbildung geht hervor, dass bei jedem Durchgang das nächstkleinere Element im sortierten Array an die richtige Position gebracht wird. Aus der obigen Abbildung geht hervor, dass zum Sortieren eines Arrays von 5 Elementen vier Durchgänge erforderlich waren. Dies bedeutet im Allgemeinen, dass zum Sortieren eines Arrays von N Elementen insgesamt N-1 Durchgänge erforderlich sind.

Im Folgenden wird die Implementierung des Auswahlsortieralgorithmus in C ++ angegeben.

C ++ Beispiel

#include using namespace std; int findSmallest (int(),int); int main () { int myarray(10) = {11,5,2,20,42,53,23,34,101,22}; int pos,temp,pass=0; cout<<' Input list of elements to be Sorted '; for(int i=0;i<10;i++) { cout<

Ausgabe:

Geben Sie eine Liste der zu sortierenden Elemente ein

11 5 2 20 42 53 23 34 101 22

Sortierte Liste von Elementen ist

2 5 11 20 22 23 34 42 53 101

Anzahl der zum Sortieren des Arrays erforderlichen Durchgänge: 10

Wie im obigen Programm gezeigt, beginnen wir mit der Auswahlsortierung, indem wir das erste Element im Array mit allen anderen Elementen im Array vergleichen. Am Ende dieses Vergleichs wird das kleinste Element im Array an der ersten Position platziert.

Im nächsten Durchgang wird mit demselben Ansatz das nächstkleinere Element im Array an der richtigen Position platziert. Dies wird fortgesetzt, bis N Elemente oder bis das gesamte Array sortiert ist.

Java-Beispiel

Als nächstes implementieren wir die Auswahlsortiertechnik in der Java-Sprache.

class Main { public static void main(String() args) { int() a = {11,5,2,20,42,53,23,34,101,22}; int pos,temp; System.out.println(' Input list to be sorted... '); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { pos = findSmallest(a,i); temp = a(i); a(i)=a(pos); a(pos) = temp; } System.out.println(' printing sorted elements... '); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } } public static int findSmallest(int a(),int i) { int smallest,position,j; smallest = a(i); position = i; for(j=i+1;j<10;j++) { if(a(j)

Ausgabe:

Eingabeliste zum Sortieren…

11 5 2 20 42 53 23 34 101 22

Drucken sortierter Elemente…

2 5 11 20 22 23 34 42 53 101

Auch im obigen Java-Beispiel wenden wir dieselbe Logik an. Wir finden wiederholt das kleinste Element im Array und fügen es in das sortierte Array ein, bis das gesamte Array vollständig sortiert ist.

Daher ist die Auswahlsortierung der am einfachsten zu implementierende Algorithmus, da wir nur wiederholt das nächstkleinere Element im Array finden und es mit dem Element an der entsprechenden Position austauschen müssen.

Komplexitätsanalyse der Auswahlsortierung

Wie im obigen Pseudocode für die Auswahlsortierung zu sehen ist, wissen wir, dass für die Auswahlsortierung zwei für miteinander verschachtelte Schleifen erforderlich sind, um sich selbst zu vervollständigen. Eine for-Schleife durchläuft alle Elemente im Array, und wir ermitteln den minimalen Elementindex mithilfe einer anderen for-Schleife, die in der äußeren for-Schleife verschachtelt ist.

Daher hat der Auswahlsortieralgorithmus bei einer Größe N des Eingabearrays die folgenden Zeit- und Komplexitätswerte.

Zeitkomplexität im schlimmsten FallO (n 2); O (n) Swaps
Best-Case-ZeitkomplexitätO (n 2); O (n) Swaps
Durchschnittliche ZeitkomplexitätO (n 2); O (n) Swaps
RaumkomplexitätO (1)

Die zeitliche Komplexität von O ( n zwei) ist hauptsächlich auf die Verwendung von zwei for-Schleifen zurückzuführen. Es ist zu beachten, dass die Auswahlsortiertechnik niemals mehr als O (n) Swaps benötigt und vorteilhaft ist, wenn sich die Speicherschreiboperation als kostspielig erweist.

Fazit

Die Auswahlsortierung ist eine weitere einfachste Sortiertechnik, die einfach implementiert werden kann. Die Auswahlsortierung funktioniert am besten, wenn der Bereich der zu sortierenden Werte bekannt ist. Was das Sortieren von Datenstrukturen unter Verwendung der Auswahlsortierung betrifft, können wir nur Datenstrukturen sortieren, die linear und von endlicher Größe sind.

Dies bedeutet, dass wir Datenstrukturen wie Arrays mithilfe der Auswahlsortierung effizient sortieren können.

In diesem Tutorial haben wir die Auswahlsortierung ausführlich erläutert, einschließlich der Implementierung der Auswahlsortierung in C ++ und Java. Die Logik hinter der Auswahlsortierung besteht darin, das kleinste Element in der Liste wiederholt zu finden und an der richtigen Position zu platzieren.

Im nächsten Tutorial werden wir detailliert über die Einfügungssortierung lernen, die als effizientere Technik bezeichnet wird als die beiden anderen Techniken, die wir bisher besprochen haben, d. H. Blasensortierung und Auswahlsortierung.

=> Hier finden Sie A-Z der C ++ - Schulungsanleitungen.

Literatur-Empfehlungen

^