Array {6, 1, 2, 3, 4, 5} is almost sorted too, but it takes O(n) iterations to sort it. Element {6} is a rabbit. This example demonstrates adaptive property of the bubble sort.
{ 6 1 2 3 4 5 } unsorted
{ 6 1 2 3 4 5 } 6 > 1, swap
{ 1 6 2 3 4 5 } 6 > 2, swap
{ 1 2 6 3 4 5 } 6 > 3, swap
{ 1 2 3 6 4 5 } 6 > 5, swap
{ 1 2 3 4 6 5 } 6 > 5, swap
{ 1 2 3 4 5 6 } 1 < 2, ok
{ 1 2 3 4 5 6 } 2 < 3, ok
{ 1 2 3 4 5 6 } 3 < 4, ok
{ 1 2 3 4 5 6 } 4 < 5, ok
{ 1 2 3 4 5 6 } sorted
Code snippets
There are several ways to implement the bubble sort. Notice, that "swaps" check is absolutely necessary, in order to preserve adaptive property.
Java
public void bubbleSort(int[] arr) {
boolean swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < arr.length - j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
}
C++
void bubbleSort(int arr[], int n) {
bool swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < n - j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
}
Leave reply