Blasensortierung in C

Sortieren ist ein notwendiges Konzept, das wir in jeder Programmiersprache lernen müssen. Meistens wird das Sortieren auf Arrays mit Zahlen durchgeführt und ist ein Sprungbrett zur Beherrschung der Techniken zum Durchlaufen und Zugreifen auf Daten aus Arrays.
Die Art der Sortiertechnik, über die wir im heutigen Artikel sprechen werden, ist die Blasensortierung.

Blasensortierung

Blasensortierung ist ein einfacher Sortieralgorithmus, der durch wiederholtes Vertauschen benachbarter Elemente funktioniert, wenn sie in der falschen Reihenfolge sind. Diese Methode zum Sortieren eines Arrays eignet sich nicht für große Datensätze, da die zeitliche Komplexität für Durchschnitts- und Worst-Case-Szenarien sehr hoch ist.

Algorithmus der Blasensortierung:

1. Bubble Sort organisiert ein Array, indem es in mehreren Durchgängen sortiert wird.
2. Erster Durchgang: Das größte Element bewegt sich an die letzte Position, seinen richtigen Platz.
3. Zweiter Durchgang: Das zweitgrößte Element bewegt sich an die vorletzte Position, und dies wird für die folgenden Durchgänge fortgesetzt.
4. Bei jedem Durchgang wird nur der unsortierte Teil des Arrays verarbeitet.
5. Nach k Durchgängen befinden sich die größten k Elemente an ihren korrekten Positionen in den letzten k Slots.
6. Bei jedem Durchgang:
   • Vergleichen Sie benachbarte Elemente im unsortierten Abschnitt.
   • Tauschen Sie die Elemente, wenn das größere vor dem kleineren erscheint.
   • Am Ende des Durchgangs bewegt sich das größte unsortierte Element an seine richtige Position. Dieser Vorgang wiederholt sich, bis das gesamte Array sortiert ist.

Wie funktioniert die Blasensortierung?

Unten finden Sie die Implementierung der Blasensortierung. Es kann optimiert werden, indem der Algorithmus gestoppt wird, wenn die innere Schleife keinen Austausch verursacht hat.

// Easy implementation of Bubble sort
#include <stdio.h>
int main(){
    int i, j, size, temp, count=0, a[100];
    //Asking the user for size of array
    printf("Enter the size of array you want to enter = \t");
    scanf("%d", &size);
    //taking the input array through loop
    for (i=0;i<size;i++){
        printf("Enter the %dth element",i);
        scanf("%d",&a[i]);
    }
    //printing the unsorted list
    printf("The list you entered is : \n");
    for (i=0;i<size;i++){
        printf("%d,\t",a[i]);
    }
    //sorting the list
    for (i = 0; i < size - 1; i++) {
        count = 1;
        for (j = 0; j < size - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                //swapping elements
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
                count = 1;
            }
        }

        // If no two elements were swapped by inner loop,
        // then break
        if (count == 1)
            break;
    }
    // printing the sorted list
    printf("\nThe sorted list is : \n");
    for (i=0;i<size;i++){
        printf("%d,\t",a[i]);
    }
    return 0;

}

Ausgabe :

**

Komplexitätsanalyse der Blasensortierung:

Zeitkomplexität: O(n2)
Hilfsraum: O(1)

Vorteile der Blasensortierung:

• Bubble Sort ist leicht zu verstehen und umzusetzen.
• Es ist kein zusätzlicher Speicherplatz erforderlich.
• Es handelt sich um einen stabilen Sortieralgorithmus, was bedeutet, dass Elemente mit demselben Schlüsselwert ihre relative Reihenfolge in der sortierten Ausgabe beibehalten.

Nachteile der Blasensortierung:

• Blasensortierung hat eine zeitliche Komplexität von O(n2), was sie für große Datensätze sehr langsam macht.
• Bubble Sort ist ein vergleichsbasierter Sortieralgorithmus, was bedeutet, dass ein Vergleichsoperator erforderlich ist, um die relative Reihenfolge der Elemente im Eingabedatensatz zu bestimmen. Dies kann in bestimmten Fällen die Effizienz des Algorithmus einschränken.

Kommentieren Sie, wenn Sie Fragen haben!!
Und alle Diskussionen werden geschätzt :)

Das obige ist der detaillierte Inhalt vonBlasensortierung in C. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!