Bubble Sort Running

CODE

void bubbleSort(int arr[], int n)
{ int i, j;
for (i = 0; i < n - 1; i++)

// Last i elements are already in place
for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}

Description

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.

Time Complexity

For Worst case:

Total number of swaps = Total number of comparison
Total number of comparison (Worst case) = n(n-1)/2
Total number of swaps (Worst case) = n(n-1)/2

Worst and Average Case Time Complexity: O(n*n).
The worst case occurs when an array is reverse sorted.

Best Case Time Complexity: O(n).
The best case occurs when an array is already sorted.

Auxiliary Space: O(1)

Boundary Cases: Bubble sort takes minimum time (Order of n)
when elements are already sorted.

Sorting In Place: Yes

Stable: Yes

Size Speed