COMP1927 - Bubble Sort

Bubble Sort is a very very basic sort. Each element is compared to the one next to it, and if they are out of order, swapped. The list is traversed in this manner as many times as needed until sorted.

Stable
In-Place

## Complexity

Bubble Sort has a worst case of O(n2) (although each traversal the list becomes one element shorter, as the biggest always bubbles to the top and is hence sorted).

It has a best case of O(n), as if the list is already sorted (no swaps are made) it early exits.

(There's actually a more efficient version; cocktail sort where the smallest and biggest element are shifted appropriately each time).

## Example ## Code

```void bubbleSort (int array[], int length) {

int temp;

int sorted = FALSE;
int swapped = FALSE;

// We access i+1, so we need to stop i at one before the end.
int lengthToTraverse = length-1;
int i;

// While there is an unsorted part of the list
while ((lengthToTraverse > 0) && (!sorted)) {

for (i = 0; i < lengthToTraverse; i++) {
// If they're out of order, swap them
if (array[i] > array[i+1]) {
temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
swapped = TRUE;
}
}

// If no swaps were made, early exit
if (!swapped) {
sorted = TRUE;
}

swapped = FALSE;
lengthToTraverse--;
}

}
```
page revision: 8, last edited: 20 Aug 2011 05:23