Bubble Sort

It is the simplest sorting algorithm that repeatedly steps through the list, compares adjacent elements and swap them if they are in wrong order.

The pass through the list is repeated until the list is sorted.

---

Example:

First pass:

(8 3 5 4 9) => (3 8 5 4 9), Here it compares the first two elements and swaps since 8>3.

(3 8 5 4 9) => (3 5 8 4 9), Swap since 8>5.

(3 5 8 4 9) => (3 5 4 8 9), Swap since 8>4.

(3 5 4 8 9) => (3 5 4 8 9), Now since these elements are already in order(8>5), algorithm does not swap them.

Second Pass:

(3 5 4 8 9) => (3 5 4 8 9)

(3 5 4 8 9) => (3 4 5 8 9), Swap since 5>4

(3 4 5 8 9) => (3 4 5 8 9)

(3 4 5 8 9) => (3 4 5 8 9)

Now, the array is already sorted, but our algorithm does not know if it is sorted or not. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:

(3 4 5 8 9) => (3 4 5 8 9)

(3 4 5 8 9) => (3 4 5 8 9)

(3 4 5 8 9) => (3 4 5 8 9)

(3 4 5 8 9) => (3 4 5 8 9)

---

Another visual example:

---

Pseudo code:

procedure bubble_Sort( list : array of items )

   loop = list.count;
   
   for i = 0 to loop-1 do:
      swapped = false
		
      for j = 0 to loop-1 do:
      
         // compare the adjacent elements   
         if list[j] > list[j+1] then
            // swap them 
            swap( list[j], list[j+1] )		 
            swapped = true
         end if
         
      end for
      
      /*if no number was swapped that means 
      array is sorted now, break the loop.*/
      
      if(not swapped) then
         break
      end if
      
   end for
   
end procedure return list

---

Implementation using C:

#include <stdio.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// An optimized version of Bubble Sort
void bubbleSort(int arr[], int n)
{
   int i, j;
   int swapped=1;
   for (i = 0; i < n-1; i++)
   {
     swapped = 0;
     for (j = 0; j < n-i-1; j++)
     {
        if (arr[j] > arr[j+1])
        {
           swap(&arr[j], &arr[j+1]);
           swapped = 1;
        }
     }

     // IF no two elements were swapped by inner loop, then break
     if (swapped == 0)
        break;
   }
}

/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test above functions
int main()
{
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Output:
Sorted array:
11 12 22 25 34 64 90

---

Miscellaneous:

In-place: Yes

Stable: Yes

Worst case & Average case: O(n*n), occurs when array is reverse sorted.

Best case: O(n), occurs when array is already sorted.