Wie implementiert man Selection Sort in C?

Die Auswahlsortierung ist ein weiterer Algorithmus, der arbeitet, indem er die niedrigste ganze Zahl des Arrays findet und sie dann der obersten Position zuweist. Der Index neben der Position der kleinsten Ganzzahl wird verwendet, um das folgende zu scannende Array zu beginnen.

Beispiel für Auswahlsortierung in C

Wenn wir ein Array mit den Zahlen [10,2,8,4,6] nehmen, in denen die kleinste Zahl 2 ist, platzieren wir die kleinste Zahl, die 2 ist, an der ersten Position, nach der das Array suchen wird wie [2,10,8,4,6]. Als nächstes nehmen wir die nächstkleinere Zahl, denn die 2 steht jetzt schon an der richtigen Stelle. Die nächstkleinere Zahl ist 4, die an die zweite Position gesetzt wird, danach wird das Array ähnlich durchsucht, bis es endgültig sortiert ist.

Die Auswahl sort in C sortiert Zahlen in aufsteigender Reihenfolge. Durch Modifikation des Algorithmus können Zahlen absteigend angeordnet werden. Selection Sort kann auch in anderen Sprachen als C durchgeführt werden, wie Selection Sort C++ oder Selection Sort Python.

Lernen Sie Softwareentwicklungskurse online von den besten Universitäten der Welt. Verdienen Sie Executive PG-Programme, Advanced Certificate-Programme oder Master-Programme, um Ihre Karriere zu beschleunigen.

Auswahlsortieralgorithmus

• Zuerst setzen wir das Anfangselement in der Auswahlsortierung auf das Minimum und suchen nach dem kleinsten Element im Array für die korrekte Prozedur des Auswahlsortieralgorithmus .
• Das minimale Element wird nun mit der zweiten Komponente verglichen. Wenn das zweite Element das Minimum unterschreitet, tauschen wir sie aus und weisen dann dem dritten Element einen Mindestwert zu.
• Andernfalls fahren wir mit dem dritten Element fort und vergleichen es mit dem Minimum. Wenn das zweite Element unser erstes Element übersteigt, tauschen wir es aus. Wiederholen Sie diesen Vorgang bis zum letzten Bauteil.
• Nach jeder Iteration sehen wir, dass unser Minimum am Anfang der unsortierten Liste angekommen ist.
• Wir beginnen mit der Indizierung ab dem ersten Eintrag der unsortierten Liste für jede Iteration. Bis die Liste sortiert ist oder alle Komponenten passend positioniert sind, wiederholen wir die Schritte 1 bis 4 mehrmals.

Beliebte Kurse und Artikel zum Thema Softwareentwicklung

Das folgende Beispiel mit jeder Iteration hilft dabei, den Prozess der Auswahlsortierung in C im Detail zu verstehen.

Iteration Nr. 1

Ich [ ] = 8,5,2,6,4

Legen Sie ein Minimum fest – 8

Vergleiche i 0 und i 1

Da i 0 > i 1 , setze Minimum = 5.

• Vergleiche i 1 und i 2

Da i 1 > i 2 , setze Minimum = 2.

• Vergleiche i2 und i3

Da i 2 < i 3 , setze minimum= 2.

• Vergleiche i 2 und i 4

Da i 2 < i 4 , setze Minimum = 2.

2 die kleinste Zahl aller Elemente ist, müssen wir i 0 und i 2 vertauschen

­ Iteration Nr. 2

Ich [] = 2,5,8,6,4

Stellen Sie mindestens 5 ein

• Vergleiche i 1 und i 2

Da i 1 < i 2 , setze Minimum = 5.

• Vergleiche i 1 und i 3

Da i 1 < i 3, setze Minimum = 5

• Vergleiche i 1 und i 4

Wieder gilt i 1 < i 4 , setze Minimum = 4.

4 ist das kleinste Element im Array, daher müssen wir i 1 und i 4 vertauschen .

Iteration Nr. 3

Ich [] = 2,4,8,6,5

Stellen Sie mindestens 8 ein

• Vergleiche i2 und i3

Da i 2 > i 3 , setze Minimum = 6.

• Vergleiche i3 und i4

Da i 3 > i 4 , setze Minimum = 5.

5 das kleinste Element im Array ist, müssen Sie i 2 und i 4 vertauschen .

Iteration Nr. 4

Ich [ ] = 2,4,5,6,8

Stellen Sie mindestens 6 ein

• Vergleiche i3 und i4

Da i 3 < i 4 , setze Minimum = 6.

Das Minimum wird an der richtigen Stelle platziert; somit findet kein Austausch statt.

Beispiel für Auswahlsortierung in C

// Auswahlsortierung in C

#include <stdio.h>

// Funktion zum Vertauschen der Position zweier Elemente

void swap(int *a, int *b) {

int temp = *a;

*a = *b;

*b = Temperatur;

}

void selectionSort(int array[], int size) {

for (int step = 0; step < size – 1; step++) {

int min_idx = Schritt;

for (int i = Schritt + 1; i < Größe; i++) {

// Um ​​in absteigender Reihenfolge zu sortieren, ändern Sie in dieser Zeile > in <.

// Wählen Sie das kleinste Element in jeder Schleife aus.

if (array[i] < array[min_idx])

min_idx = ich;

}

// setze min an die richtige Position

swap(&array[min_idx], &array[schritt]);

}

}

// Funktion zum Drucken eines Arrays

void printArray(int array[], int size) {

for (int i = 0; i < Größe; ++i) {

printf(“%d“, array[i]);

}

printf(“\n”);

}

// Treibercode

int Haupt() {

int data[] = {20, 12, 10, 15, 2};

int size = sizeof(data) / sizeof(data[0]);

selectionSort(Daten, Größe);

printf("Sortiertes Array in aufsteigender Reihenfolge:\n");

printArray(Daten, Größe);

}

Komplexitätsanalyse von Selection Sort

Eingabe – Es werden n Eingabeelemente angegeben.

Ausgabe – Die Anzahl der Schritte, die zum Sortieren der Liste erforderlich sind.

Logik – Wenn uns n Elemente gegeben werden, werden im ersten Durchgang n-1 Vergleiche durchgeführt, im zweiten Durchgang n-2 Vergleiche, im dritten Durchgang n-3 Vergleiche und so weiter. Folglich kann die Gesamtzahl der Vergleiche unter Verwendung von berechnet werden;

Ausgabe -

(n+1) + (n+2) + (n+3) + (n+4) + …. +1

Summe = n(n-1)/2 dh O(n²)

Da das Auswahlsortierverfahren etwas zusätzlichen Speicherplatz für temporäre Variablen zum Austauschen benötigt, hat es eine Zeitkomplexität von O(n2) und eine Platzkomplexität von O(1).

Selektion Sortierzeit Komplexitätsanalyse

Best Case: Für das zuvor sortierte Array hat das Selection-Sort-Verfahren eine Best-Case-Zeitkomplexität von O(n²).

Average Case: Der Selection-Sort-Algorithmus hat eine Average-Case-Zeitkomplexität von O(n²), wenn die Elemente durcheinander angeordnet sind, d. h. weder in aufsteigender noch in absteigender Reihenfolge.

Worst Case: Wenn wir die absteigende Reihenfolge eines Arrays in seine aufsteigende Reihenfolge umkehren, beträgt die Zeitkomplexität im ungünstigsten Fall O(n²).

Die zeitliche Komplexität des Auswahlsortierverfahrens ist in jedem der drei Szenarien O(n²). Dies liegt daran, dass wir für jede Phase das Nötigste identifizieren müssen, um sie richtig zu arrangieren. Nachdem wir das gesamte Array verfolgt haben, haben wir unser minimales Element gefunden.

Fazit

Damit endet der Blogbeitrag zu „Selection Sort In C“. Sie müssen verstehen, dass es auch in anderen Sprachen ausgeführt werden kann, wie Selection Sort C++ und Selection Sort Python. Wir hoffen, dass dieser Artikel Ihnen hilft zu verstehen, wie Elemente in C sortiert werden.

Das Sortieren der Auswahl ist nicht der einzige Abschnitt auf dem Weg zum Programmierer. Wenn Sie hoffen, Ihrer Karriere als Softwareentwickler mit einem professionellen Abschluss einen deutlichen Schub zu verleihen, ist upGrad genau das Richtige für Sie! Frontend-Entwicklung (JavaScript, HTML, CSS), Backend (NoSQL-MongoDB) und Microservices von upGrad, dann können Sie UpGrads Master of Science in Computer Science studieren. Dieser Kurs wird von IIIT Bangalore & LJMU Alumni Status angeboten und hilft Ihnen, Ihre Karriere als Softwareingenieur/Full-Stack-Entwickler bei den Technologiegiganten auf der ganzen Welt zu starten.

Dieser Kurs deckt die Grundkenntnisse von Tools wie Java, Spring und Hibernate ab und stärkt unsere Full-Stack-Entwicklungsfähigkeiten, um den Arbeitsmarkt mit bemerkenswerten Möglichkeiten zu erkunden.

Melden Sie sich an, um mehr zu erfahren!