Search code examples
c++sortingbubble-sort

Why do we make n-1 iterations in bubble sort algorithm


Most common way of bubble sort algorithm is to have two for loops. Inner one being done from j=0 until j n-i-1. I assume we substract minus i, because when we reach last element we don't compare it because we don't have an element after him. But why do we use n-1. Why we don't run outer loop from i=0 until i < n and inner from j=0 until n-i? Could someone explain it to me, tutorials on internet does not emphasize this.

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;
            }

        }
     }

For example, if I have an array with 6 elements, why do I only need to make 5 iterations?


Solution

  • Because a swap requires at least two elements.

    So if you have 6 elements, you only need to consider 5 consecutive pairs.