Warum machen wir n-1 Iterationen in Bubble-Sort-Algorithmus

Question

Die häufigste Art und Weise der Blase Sortieralgorithmus ist zwei For-Schleifen zu haben. Inneres wird von j = 0 bis j n-i-1 gemacht. Ich nehme an, wir subtrahieren minus ich, denn wenn wir das letzte Element erreichen, vergleichen wir es nicht, weil wir kein Element nach ihm haben. Aber warum benutzen wir n-1. Warum führen wir keine äußere Schleife von i = 0 bis i < n und inner von j = 0 bis n-i? Könnte mir jemand das erklären, Tutorials im Internet betonen das nicht.

for (int i = 0; i < n - 1; i++) // Why do we have n-1 here? 
    { 
     swapped = false; 
     for (int j = 0; j < n - i - 1; j++) 
     { 
      countComparisons++; 
      if (arr[j] > arr[j + 1]) 
      { 
       countSwaps++; 
       swap(&arr[j], &arr[j + 1]); 
       swapped = true; 
      } 

     } 
    } 

Zum Beispiel, wenn ich ein Array mit 6 Elementen haben, warum brauche ich nur 5 Iterationen zu machen?

Answer 1

Weil ein Swap mindestens zwei Elemente benötigt.

Wenn Sie also 6 Elemente haben, müssen Sie nur 5 aufeinanderfolgende Paare berücksichtigen.