# 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.