C-Programm für Bubble Sorting: Bubble Sort in C
Veröffentlicht: 2020-10-20Inhaltsverzeichnis
Einführung
Das Sortieren eines Arrays nimmt in der Informatik eine immense Bedeutung ein. Seine Nützlichkeit wird bemerkt, wenn Daten in einer bestimmten Reihenfolge angeordnet werden müssen. Es gibt verschiedene Arten von Sortieralgorithmen. Der gebräuchlichste und am weitesten verbreitete Sortieralgorithmus ist der Bubble Sort.
Blasensortierung in C
Die Technik, die zum Sortieren in Bubble Sort verwendet wird, ist einfach und leicht zu verstehen. Es vergleicht lediglich das aktuelle Element mit dem nächsten Element und tauscht es aus, wenn es je nach Bedingung größer oder kleiner ist. Der Algorithmus ist sehr genau. Jedes Mal, wenn ein Element mit anderen Elementen verglichen wird, bis sein Platz gefunden ist, wird dies als Durchgang bezeichnet.
Dieser Algorithmus ist vergleichbar mit Blasen in Wasser, da er die Oberseite der Array-ähnlichen Blasen herausfiltert. Unter allen zum Sortieren verwendeten Algorithmen ist Bubble Sort der einfachste und langsamste mit einer Zeitkomplexität von O(n^2). Der Algorithmus kann jedoch durch die Verwendung einer Flag-Variablen optimiert werden, die die Schleife verlässt, wenn der Austausch abgeschlossen ist. Der beste Fall für Bubblesort kann O(n) sein, wenn das Array sortiert ist.
Nehmen wir zum Beispiel ein unsortiertes Array von fünf Zahlen, wie unten angegeben
13, 32,26, 34,9
Bubble Sort beginnt mit der Betrachtung der ersten beiden Elemente und vergleicht sie, um zu prüfen, welches größer ist. In diesem Fall ist 32 größer als 13. Dieser Teil ist also bereits y-sortiert. Als nächstes vergleichen wir 32 mit 26. Wir stellen also fest, dass 32 größer als 26 ist, also müssen sie ausgetauscht werden. Das neue Array wird wie folgt aussehen
13, 26, 32,34,9
Als nächstes vergleichen wir 32 und 34. Wir wissen, dass sie bereits sortiert sind. Damit kommen wir zu den letzten beiden Variablen 34 und 9. Da 34 größer als 9 ist, müssen sie vertauscht werden.
Wir vertauschen die Werte und kommen nach der ersten Iteration an das Ende des Arrays. Jetzt sieht das Array so aus
13, 26. 32,9,34
Nach der zweiten Iteration sieht das Array so aus
13, 26, 9, 32, 34
Nach der dritten Iteration wird das Array
13,9,26,32,34
Nach der vierten Iteration ist das Array vollständig sortiert
9, 13,26,32,34
Muss gelesen werden: Projektideen in C
Der Algorithmus
Hier gehen wir davon aus, dass das Array n Elemente hat. Außerdem nehmen wir an, dass die Funktion zum Austauschen von Werten alle Werte austauscht, um die Array-Nummern in sortierter Reihenfolge zu erstellen.
BubbleSort starten (Array)
für alle Elemente der Liste
wenn Array[i]> Array[i+1]
Werte austauschen (array[i], array[i+1] )
Ende wenn
Ende für
Rückgabe-Array
Beenden Sie Bubble Sort
Lesen Sie: Sortieren in der Datenstruktur: Kategorien & Typen
Pseudocode
Aus dem obigen Algorithmus geht hervor, dass ein Vergleich zwischen jedem Paar der Array-Elemente stattfindet, bis das gesamte Array in aufsteigender Reihenfolge sortiert ist. Dies kann zu einigen Komplexitätsproblemen führen, z. B. zum Ergebnis des Algorithmus, wenn das Array bereits in aufsteigender Reihenfolge sortiert ist. Um das Problem zu lösen, verwenden wir eine Flag-Variable, mit der wir sehen können, ob es zu einem Austausch gekommen ist. Wenn kein Tauschen mehr nötig ist, kommen wir aus der inneren Schleife heraus.
Der Pseudocode für den BubbleSort-Algorithmus kann wie folgt geschrieben werden
Prozedur BubbleSort (Array: Elemente im Array)
iterieren = array.count;
für k = 0 bis iterate-1 tun:
Flag = falsch
für l=0 bis iterate-1 tun:
if (array[l]> array[l+1]) then
Austauschwerte (Array[l], Array [l+1])
Flagge = wahr
Ende wenn
Ende für
Wenn (nicht getauscht) dann
Brechen
Ende wenn
Ende für
Rückgabearray der Prozedur beenden
Lassen Sie uns ein Beispielprogramm von Bubble Sort in C ausprobieren :
# include<stdio.h>
ungültige Hauptsache
{
int Array [10], i, j, num
für (i=0; i<=9; i++)
{
scanf(“%d”, &array[i])
}
für(i=0;i<=9;i++)
{
for(j=0;j<=9-i;j++)
{
if(Array[j]>Array[j+1])
{
num= array[j];
Array[j]=Array[j+1];
array[j+1]=num;
}
}
}
printf("Das sortierte Array ist /n");
für(i=0;i<=9;i++)
{
printf(“%d ”,&array[i])
}
}
Wie im Beispiel gezeigt, akzeptiert dieser Bubble-Sort-Algorithmus 10 Zahlen vom Benutzer und speichert sie im Array. Im nächsten Teil gibt es zwei for-Schleifen. Die äußere Schleife läuft für den I-Wert, der gleich null bis kleiner als gleich neun ist. Die Funktion der äußeren Schleife besteht darin, sich um alle Elemente des Werts zu kümmern, die mit anderen Elementen verglichen werden müssen.
Innerhalb der äußeren Schleife befindet sich eine weitere Schleife. Es beginnt bei j = 0 und läuft, bis es kleiner oder gleich acht ist. Darin befindet sich eine bedingte if-Anweisung, die vergleicht und überprüft, ob array[j] größer als array[j+1] ist. Ist die Bedingung erfüllt, werden die Werte von array[j] und array [j+1] miteinander vertauscht.
Dazu wird eine Variable namens num verwendet. Zuerst wird Array[j] num zugewiesen, dann Array[j+1] wird Array[j] zugewiesen und schließlich wird num Array[j+1] zugewiesen. Dieser Vorgang wird fortgesetzt, bis alle Elemente im Array in aufsteigender Reihenfolge sortiert sind. Danach wird das sortierte Array gedruckt.
Optimierte Implementierung von Bubble Sort
Wir haben einen optimierten Algorithmus für Bubble Sort zur Verbesserung der Ergebnisse. Die Verwendung einer Flag-Variablen führt die Optimierung durch. Die Flag-Variable hält 1, wenn ein Austausch stattfindet, sonst bricht sie aus der Schleife aus. Unten ist das optimierte Bubble-Sort-Programm in C.
#include<stdio.h>
ungültige Hauptsache
{
int array [10], i, j, num, flag=0;
für (i=0; i<=9; i++)
{
scanf(“%d”, &array[i])
}
für(i=0;i<=9;i++)
{
for(j=0;j<=9-i;j++)
{
if(Array[j]>Array[j+1])
{
num= array[j];
Array[j]=Array[j+1];
array[j+1]=num;
Flagge = 1;
}
wenn (! Flagge)
{
brechen;
}
}
}
printf("Das sortierte Array ist /n");
für(i=0;i<=9;i++)
{
printf(“%d ”,&array[i])
}
}
Das angegebene Programm wird ähnlich wie das normale Bubble-Sort-Programm ausgeführt. Die einzige Änderung ist die Verwendung der Flag-Variablen. Anfangs ist das Flag auf 0 gesetzt. Wenn jedoch ein Austausch stattfindet, wird das Flag zu 1. Dies impliziert, dass das Array noch eine weitere Überprüfung erfordert. Wenn andererseits das Flag nicht 1 ist, was bedeutet, dass kein Austausch stattgefunden hat, verlassen wir die innere Schleife, wobei wir davon ausgehen, dass das Array bereits sortiert ist. Nach der Ausführung erhalten wir das gleiche Ergebnis wie bei der normalen Bubble-Sortierung.
Zeitkomplexität
Die optimale Zeitkomplexität für Bubblesort ist O(n). Es passiert, wenn das Array bereits sortiert ist. Der schlimmste Fall ist O(n*n), wenn das Array nicht sortiert wurde.
Lesen Sie: Top 12 Pattern-Programme in Java, die Sie heute auschecken sollten
Was als nächstes?
Wenn Sie mehr über Java und Full-Stack-Softwareentwicklung erfahren möchten, schauen Sie sich das PG-Diplom in Full-Stack-Softwareentwicklung von upGrad & IIIT-B an, das für Berufstätige konzipiert ist und mehr als 500 Stunden strenge Schulungen und mehr als 9 Projekte bietet und Aufgaben, IIIT-B-Alumni-Status, praktische praktische Schlusssteinprojekte und Arbeitsunterstützung bei Top-Unternehmen.