Zuallererst bin ich Anfänger in C, also tut es mir leid, wenn meine Frage dumm erscheint. Ich habe gelernt, wie man den Blasensortierungsalgorithmus in C verwendet, und bin durch diesen Code gekommen:

#include <stdio.h>

int main() {
    int ctr, inner, outer, didSwap, temp;
    int nums[10] = {
        78,
        16,
        21,
        7,
        13,
        9,
        22,
        52,
        67,
        19
    };

    //Listing the array before sorting

    for (ctr = 0; ctr < 10; ctr++) {
        printf("%d\n", nums[ctr]);
    }

    //Sorting the arrays

    for (outer = 0; outer < 9; outer++) {
        didSwap = 0;
        for (inner = outer; inner < 10; inner++) {
            if (nums[inner] < nums[outer]) {
                temp = nums[inner];
                nums[inner] = nums[outer];
                nums[outer] = temp;
                didSwap = 1;
            }
        }
        if (didSwap == 0) {
            break;
        }
    }

    //Listing the array after sorting

    printf("\n\nThis is the sorted array\n");
    for (ctr = 0; ctr < 10; ctr++) {
        printf("%d\n", nums[ctr]);
    }

    return 0;
}

Der Code funktioniert gut, aber ich möchte verstehen, wie in der zweiten for-Schleife inner = outer geschrieben wird und in der nächsten if-Anweisung die Elemente des Arrays verglichen werden, wenn eines von ihnen dieselbe Nummer hat wie inner und der andere hat die gleiche Nummer wie außen. Und da wir das inner = outer gesagt haben, bedeutet dies, dass wir dasselbe Element vergleichen. Ich denke darüber nach, wenn outer = 0 und seit inner = outer auch inner 0 ist, also lautet die nächste if-Anweisung if (nums[0] < nums[0]) und das macht keinen sinn.

Ich weiß, dass ich mich wahrscheinlich irre, weil der Code gut funktioniert, aber was habe ich falsch gedacht?

Danke im Voraus.

4
notopython 19 Feb. 2020 im 20:26

4 Antworten

Beste Antwort

Die Essenz Ihrer Blasensortierung besteht darin, dass bei jedem Scan die "Blase" der größte Wert ist, der bisher gesehen wurde. Am Ende des Scans ist der größte Wert also nach oben "gesprudelt". Dann wiederholen Sie von Anfang an, aber jedes Mal (klar) haben Sie einen Wert weniger, den Sie berücksichtigen müssen. Wenn sich am Ende eines Scans nichts bewegt hat, ist alles in Ordnung und Sie können anhalten.

Die Blasensortierung könnte also so aussehen:

    for (int n = 10 ; n > 0 ; n--)
      {
        bool no_swaps ;

        no_swaps = true ;
        for (int i = 1 ; i < n ; ++i)
          {
            if (nums[i-1] > nums[i])
              {
                int temp ;
                temp = nums[i-1];
                nums[i-1] = nums[i];
                nums[i]   = temp;
                no_swaps = false ;
              } ;
          } ;

        if (no_swaps)
          break ;
      } ;

Oder:

    for (int n = 10 ; n > 0 ; n--)
      {
        bool no_swaps ;
        int bubb ;

        no_swaps = true ;
        bubb = nums[0] ;
        for (int i = 1 ; i < n ; ++i)
          {
            int this ;

            this = nums[i] ;
            if (bubb <= this)
              bubb = this ;
            else
              {
                nums[i-1] = this ;
                nums[i]   = bubb ;
                no_swaps = false;
              } ;
          } ;

        if (no_swaps)
          break ;
      } ;

Dies macht möglicherweise klarer, dass die gleichnamige "Blase" (bubb) der größte im aktuellen Scan gefundene Wert ist (oder der am weitesten rechts stehende, wenn 2 oder mehr mit diesem Wert gesehen wurden).

Wenn Sie das didSwap aus Ihrer Sortierung entfernen, funktioniert es einwandfrei. Wie bei Bubble Sort verschiebt jeder Durchgang Ihrer Sortierung einen Gegenstand an sein endgültiges Ziel. Ihre Sortierung führt immer (n-1)*(n-2)/2 Vergleiche durch, was dem schlimmsten Fall für die Blasensortierung entspricht. Der beste Fall für die Blasensortierung ist jedoch (n-1) - wenn die Werte bereits in Ordnung sind!

Eine echte Blasensortierung hat also einen Vorteil gegenüber Ihrer Sortierung. Trotzdem ist Bubble Sort im Allgemeinen auch O (n ^ 2) und daher ungefähr so nützlich wie eine Schokoladenteekanne, außer wenn n klein ist.

4
Chris Hall 19 Feb. 2020 im 19:18

Was ist, wenn Ihr Array an der ersten Position bereits die größte (oder die kleinste Zahl) hat? Ihr Programm stoppt, wenn Outer gleich 0 ist. (Weil didSwap 0 ist.) Wenn Sie einige Variablen wie didSwap oder lastSwapIndex verwenden möchten, sollte die Blasensortierung das Array vergleichen [x] und Array [x-1]. Ihr Algorithmus sieht mehr nach Auswahlsortierung als nach Blasensortierung aus.

1
user9940960 20 Feb. 2020 im 06:31

Tatsächlich könnte die Initialisierung von inner in der inneren Schleife in inner = outer + 1 geändert werden, da der Test in der ersten Iteration immer falsch ist.

Beachten Sie jedoch, dass, wenn das erste Element auch das kleinste ist, alle Tests in dieser inneren Schleife falsch sind und didSwap nicht auf 1 gesetzt wird, was das verursacht äußere Schleife, um auch zu stoppen. Dies ist falsch, wenn der Rest des Arrays nicht sortiert ist.

Sie können dieses Problem beheben, indem Sie die Schleife auf Folgendes ändern:

for (outer = 0; outer < 9; outer++) {
    for (inner = outer + 1; inner < 10; inner++) {
        if (nums[inner] < nums[outer]) {
            temp = nums[inner];
            nums[inner] = nums[outer];
            nums[outer] = temp;
        }
    }
}

Dies führt in allen Fällen zu 45 Iterationen.

Um die Best-Case-Leistung zu verbessern, müssen Sie den Algorithmus geringfügig ändern, um nur benachbarte Elemente auszutauschen:

for (outer = 10; outer-- > 0; ) {
    didSwap = 0;
    for (inner = 0; inner < outer; inner++) {
        if (nums[inner] > nums[inner + 1]) {
            temp = nums[inner];
            nums[inner] = nums[inner + 1];
            nums[inner + 1] = temp;
            didSwap = 1;
        }
    }
    if (didSwap == 0) {
        break;
    }
}

Dies wird in linearer Zeit ausgeführt, wenn das Array bereits sortiert ist, aber im Durchschnitt immer noch O (N 2 ) Iterationen benötigt.

1
chqrlie for yellow blockquotes 19 Feb. 2020 im 19:46

Es ist keine dumme Frage. Sie haben erfolgreich eine Ineffizienz festgestellt. Die erste Iteration der inneren Schleife ist zwar sinnlos, verursacht aber keine Probleme. Der richtige Weg wäre, es von outer + 1 anstelle von outer zu starten.

2
Eraklon 19 Feb. 2020 im 17:36