Search code examples
algorithmbubble-sort

Is the number of iterations in a bubble sorting algorithm equal to (n-1)! for n elements?


I recently read in a book, that if we're sorting n elements in an array, the number of iterations required will be n*(n-1)*...*1 = 7!.

But I'm sure that the actual number of comparisons will be (n-1)+(n-2)+...+1 = n(n-1)/2. So are the number of iterations and number of comparisons somehow different? I'm guessing no, since in each iteration the values are compared [if(m[j]>m[j+1])]. So am I missing something, or is the book wrong?

The entire code:

for(i=0;i<7;i++)
{
    for(j=0;j<7-i;j++)
    {
        if(m[j]>m[j+1])
        {
            t=m[j];
            m[j]=m[j+1];
            m[j+1]=t;
        }
    }
}

Solution

  • If I understood the question correctly, there is some misunderstanding. For any number n of elements, there are

    n!=1*2*...*(n-1)*n
    

    different possibilities to arrange them, which are also called permutations. However, this as such is unrelated to any sorting algorithm. The asymptotic runtime complexity of Bubblesort is

    O(n^2)
    

    as you already mentioned, as Bubblesort is a bit little bit more clever than trying out all possibilities. To finally answer the question proper, no, Bubblesort does not take (n-1)! iterations on n elements.