Why is bubble sort O(n^2)?

user_1218599 0
Viewed 45425
for (int front = 1; front < intArray.length; front++)
{
    for (int i = 0; i  < intArray.length - front; i++)
    {
        if (intArray[i] > intArray[i + 1])
        {
            int temp = intArray[i];
            intArray[i] = intArray[i + 1];
            intArray[i + 1] = temp;
        }
    }
}

The inner loop is iterating: n + (n-1) + (n-2) + (n-3) + ... + 1 times.

The outer loop is iterating: n times.

So you get n * (the sum of the numbers 1 to n)

Isn't that n * ( n*(n+1)/2 ) = n * ( (n^2) + n/2 )

Which would be (n^3) + (n^2)/2 = O(n^3) ?

I am positive I am doing this wrong. Why isn't O(n^3)?

bubble-sort big-o complexity-theory sorting algorithm
6 Answers

This is another version to speed up bubble sort, when we use just a variable swapped to terminate the first for loop early. You can gain better time complexity.

#include <stdio.h>
#include <stdbool.h>
#define MAX 10

int list[MAX] = {1,8,4,6,0,3,5,2,7,9};

void display(){
   int i;
   printf("[");

   for(i = 0; i < MAX; i++){
      printf("%d ",list[i]);
   }

   printf("]\n");
}

void bubbleSort() {
   int temp;
   int i,j;

   bool swapped = false;       

   // 1st loop
   for(i = 0; i < MAX-1; i++) { 
      swapped = false;

      // 2nd loop
      for(j = 0; j < MAX-1-i; j++) {
         printf("     Compare: [ %d, %d ] ", list[j],list[j+1]);

         if(list[j] > list[j+1]) {
            temp = list[j];
            list[j] = list[j+1];
            list[j+1] = temp;

            swapped = true;
         }

      }

      if(!swapped) {
         break;
      }

      printf("Loop number %d#: ",(i+1)); 
      display();                     
   }

}

main(){
   printf("Before: ");
   display();
   printf("\n");

   bubbleSort();
   printf("\nAfter: ");
   display();
}
user_89853080
Related