Bubble Sort
Bubble sort
Bubble sort is the most basic exchange sort. Items move towards one edge in small steps, like bubbles moving through a drink.
Compare neighboring items. If the left value is larger than the right, exchange them. If it is smaller or equal, keep their positions.
For example, sort this eight-item sequence in ascending order:
Basic bubble sort: adjacent comparisons
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
The largest item, 9, reaches the far right like a rising bubble. This ends the first pass. Its position is settled, forming a sorted region containing one item.
Now perform the second pass.
The sorted region on the right now contains two items.
Continue with the same method.
Algorithm analysis
Bubble sort is stable because equal values are never exchanged. Each pass scans the remaining unsettled neighboring pairs, with n−1 effective passes.
| Time | Extra space | Stability | Design idea |
|---|---|---|---|
| Stable | Greedy |
Bubble sort
#include <stdio.h>
#include <stdbool.h>
typedef int T;
#define swap(x, y) \
{ \
T temp = x; \
x = y; \
y = temp; \
}
/**
* Bubble Sort (original v1.0)
*/
T *bubble_sort(T *arr, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
return arr;
}
int main() {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}Inversions
For an n-item array, with makes and an inversion.
#include <stdio.h>
int count_inverses(int *arr, int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
count++;
}
}
}
return count;
}
int main() {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", count_inverses(arr, n));
return 0;
}First optimization
Ordinary bubble sort continues for n−1 passes even if the array becomes sorted earlier. For {2,1,3,4,5}, one pass already produces a sorted array; further exchanges are unnecessary.
Keep a flag indicating whether a pass made an exchange. An exchanging pass does not by itself establish that sorting is complete. A pass with no exchanges does establish sortedness.
First bubble-sort optimization
First optimization: stop after a pass without swaps
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
#include <stdio.h>
#include <stdbool.h>
typedef int T;
#define swap(x, y) \
{ \
T temp = x; \
x = y; \
y = temp; \
}
/**
* Bubble Sort (original v1.0)
*/
T *bubble_sort(T *arr, int n) {
for (int i = 0; i < n; i++) {
bool swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) {
break;
}
}
return arr;
}
int main() {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}Second optimization
Even with early exit, some comparisons remain unnecessary. One pass on {2,3,1,4,5,6} produces {2,1,3,4,5,6}; much of the next pass would revisit items that did not exchange.
Record the index of the last exchange. The next pass only needs to compare up to this boundary: the suffix after it was unchanged and is already settled.
Second bubble-sort optimization
Second optimization: the last-swap boundary
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
#include <stdio.h>
#include <stdbool.h>
typedef int T;
#define swap(x, y) \
{ \
T temp = x; \
x = y; \
y = temp; \
}
/**
* Bubble Sort (original v1.0)
*/
T *bubble_sort(T *arr, int n) {
int right = n - 1;
for (int i = 0; i < n; i++) {
bool swapped = false;
int last = 0;
for (int j = 0; j < right; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
last = j;
}
}
if (!swapped) {
break;
}
right = last;
}
return arr;
}
int main() {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}KNOWLEDGE QUIZ
KNOWLEDGE QUIZ
Trace adjacent exchanges
Run basic bubble sort on [4,1,3,2]. Record the array after each neighbor comparison, counting comparisons and effective swaps separately. Use no early-exit optimization.