Die Bubble Sort verstehen

Question

Stack Overflow Ich habe nach Algorithmen gesucht, damit ich sie Stück für Stück zerlegen kann, um zu verstehen, was vor sich geht. Wie auch immer, ich schaute auf this Tutorial, um in die Blase sortieren zu sehen. Ich war verwirrt von einem sehr kleinen Teil des Demo-Algorithmus in C++, der Ganzzahl j.

void bubbleSort(int arr[], int n) { 
    bool swapped = true; 
    int j = 0; 
    int tmp; 
    while (swapped) { 
     swapped = false; 
     j++; 
     for (int i = 0; i < n - j; i++) { 
       if (arr[i] > arr[i + 1]) { 
        tmp = arr[i]; 
        arr[i] = arr[i + 1]; 
        arr[i + 1] = tmp; 
        swapped = true; 
       } 
     } 
    } 
} 

Ist es ein erforderlicher Teil des Algorithmus? Ich verstehe nicht wirklich, was es tut, als ich, als ich j innerhalb der for-Schleife für 1 tauschte, habe ich die gleichen Ergebnisse.

for (int i = 0; i < n - 1; i++) 

TL; DR: Warum ist die int j im Algorithmus?

Answer 1

In der ersten äußeren Iteration blasen wir die größte ganze Zahl in a[n-1]. Die zweite Iteration muss nur den verbleibenden unsortierten Teil des Arrays durchqueren, d. H. Von Index 0 nach n-2, und die zweitgrößte ganze Zahl nach a[n-2] blasen. Die dritte Iteration muss nur Array von Index 0 bis n-3 durchqueren und so weiter.

Die Variable j erreicht dies, indem sie den Bereich der zu überquerenden Matrix in nachfolgenden äußeren Iterationen begrenzt. Wir können sehr gut das gesamte Array in jeder Iteration durchqueren (wie Sie es tun würden, nachdem Sie n-j mit n-1 geändert haben) und das gleiche Ergebnis erhalten. Aber das wäre ineffizient, da wir Elemente in sortierten Teilen des Arrays in jeder Iteration unnötigerweise vergleichen würden. Lass es mich wissen, wenn du irgendwelche Fragen hast.

Answer 2

Die Variable j wird verwendet, um die größte Zahl nach rechts zu verschieben. Bei jeder Iteration verschieben wir den Zeiger von n (zuerst n-j = n, wenn j 0 ist) auf 0 durch Schritt 1. Schließlich haben wir ein sortiertes Array.

Answer 3

Da bubblesort arbeitet, ist es weit oben auf der Liste, es tauscht die größere Zahl bis zum Ende der Liste. Dies bedeutet, dass bei jeder Iteration des Algorithmus die letzten Elemente garantiert sortiert werden. Wenn die letzten Elemente sortiert sind, ist es nicht sinnvoll, sie erneut zu sortieren, um sie erneut zu sortieren. n-j verhindert dies, indem der Bereich der Liste eingeschränkt wird, die bei jeder Iteration besucht werden soll. Wenn mit fortschreitendem Algorithmus wächst, werden n-j Verträge abgeschlossen.

Anstatt nur den Code anzusehen, feuern Sie es in the debugger, die fast sicher mit Ihrer Entwicklungsumgebung kam (und wenn Sie keine Entwicklungsumgebung mit einem Debugger haben, ist es lange Zeit, dass Sie dies korrigiert. Der Debugger ist möglicherweise das größte Produktivitätswerkzeug, das der arbeitende Programmierer hat) und durch den Code gehen. Beobachten Sie, was mit der Liste und dem Bereich der Liste passiert, die bei jeder Iteration besucht wird.

Der Debugger ist nicht nur ein großartiges Tool zum Reparieren von Code, sondern kann auch ein großartiges Lernwerkzeug sein.