Bubble sort is a simple comparison sorting algorithm where the list is repeatedly traversed through, swapping in-place any items that are in the wrong order.
As the list is traversed through n times, and each traversal is at maximum about n items long, bubble sort has O(n²) complexity (both average-case and worst-case).
The algorithm is named as such because large values "bubble" up rather fast early up in the algorithm.
Algorithm[]
A loop is started that exits when the loop is sorted. Another loop iterates through the list. if the current item is out of order with the next item the items are swapped. If none of the items need swapping the algorithm can exit.
Pseudocode[]
bubble_sort(list of t)
temp as t
swapped as boolean
for i = list.count - 1 to 0 step -1
swap = false
for j = 0 to i - 1
if list(j) > list(j + 1)
temp = list(j) // swap
list(j) = list(j + 1)
list(j + 1) = temp
swapped = true
if not swap then
return
Optimizations[]
- Traversal reduction
- With the knowledge of what happens in bubble sort, we end up with the fact that for each traversal, the largest value will always end up at the end. With this knowledge, each traversal can be stripped off the values that are already sorted.
- Pseudocode replacement:
for j = 0 to list.count - 2→for j = 0 to i - 1
Sort completion detection[]
- For each traversal, we know for a fact that when no swaps occured, the list is already sorted.
- Pseudocode addition: We introduce a swapped boolean that detects when a swap is done.
Rabbits and turtles[]
Small values at the end of the list, the so-called turtles, tend to move rather slowly down the list. Cocktail sort, a variation of bubble sort, solves this problem. Comb sort compares elements with large gaps so turtles can be eliminated early on.
Example[]
Sorting the list: 4, 5, 3, 7, 6, 1, 2.
- 4537612
- pass 1
- 4537612
- 4357612
- 4357612
- 4356712
- 4356172
- 4356127
- pass? 2
- 3456127
- 3456127
- 3456127
- 3451627
- 3451267
- pass? 3
- 3451267
- 3451267
- 3415267
- 3412567
- pass? 4
- 3412567
- 3142567
- 3124567
- pass? 5
- 1324567
- 1234567
- pass? 6
- 1234567
Examples[]
C++[]
void swap(int *xp, int *yp) {
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void bubbleSort(int arr[], int length) {
int i, j;
bool swapped;
for (i = 0; i < length - 1; i++) {
swapped = false;
for (j = 0; j < length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
swapped = true;
}
}
if (swapped == false)
break;
}
}
Java[]
public class BubbleSort {
static void bubbleSort(int[] arr) {
int length = arr.length;
int temp = 0;
for(int i = 0; i < length; i++){
for(int j = 1; j < (length-i); j++){
if(arr[j-1] > arr[j]){
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
}
External links[]
|