Bubble sorting max number of times?

Question

I am trying to create a function that sorts 100 random numbers using bubble sort. I think I might be doing something wrong, however.. Let me show you my code first:

#define MAXVALUE 100

void sortera_nummer(int slumptal[]){
int i,j,temp,k=0;


for(i=0;i<MAXVALUE;i++){
    for(j=MAXVALUE-1;j>i;j--){
        if(slumptal[j-1]>slumptal[j]){
            temp=slumptal[j-1];
            slumptal[j-1]=slumptal[j];
            slumptal[j]=temp;
            k++;
        }
    }
}
printf("K = %d",k);
}

The numbers all get sorted from lowest to highest, so the sorting works. But I'm getting K = an unexpectedly high number. (It's been everywhere between 2300 to 2700.)

So now I'm wondering - what should be the max number of times a properly working bubble sort could run with 100 elements? What's the equation for calculating it?

(This is my first post here, I'm sorry if I made any mistakes.) Thanks in advance.

Answer 1

The worst case scenario is if the input array is sorted in descending order. The first loop executes 99 times, the next 98, the next 97...... which equates to "sum(n) from n=99 to n=1" , which means the worst case is n(n+1)/2, in your case n=99 that's 4950.