CODEWITHSUNDEEP
algorithmbubble-sort
Somenath Sinha
Somenath Sinha

Reputation: 1214

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

Upvotes: 2

Views: 3696

Answers (1)

Codor
Codor

Reputation: 17605

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.

Upvotes: 6

Related Questions