Bubble Sort

• The largest elements bubble to the correct side
• Able to handle an already sorted list in $O(n)$ time
• Comparisons: $O(n^2)$, Exchanges: $O(n^2)$

Implementation

For pass=0 to n-1  
	Sorted = true  
	for each pair of adjacent array elements between pass and n
		if the values in a pair are out of order
			Exchange the values  
			Sorted = false

while the array is not sorted

void bubbleSort(int array[], int size) { 
	for (int i = 0; i < size - 1; i++) {
		int swapped = 0;
		for (int j = 0; j < size - i - 1; j++) {
			if (array[j] > array[j + 1]) { 
				int temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
				swapped = 1;
			}
		}
		// If there is no swapping in the last swap,
	    // then the array is already sorted.
		if (swapped == 0)
	      break; 
		}
	}
}