Bubble and Insertion Sort
Simple sorts.
Bubble and Insertion Sort is a free C Academy lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the C Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Simple Sorts
Bubble sort and insertion sort are the two simplest comparison sorts. Both are O(n squared) in the worst case but easy to understand and useful for small or nearly sorted arrays.
How Bubble Sort Works
Bubble sort repeatedly walks the array, swapping adjacent out-of-order pairs. After each full pass the largest remaining element bubbles to its final position at the end.
Swapping Two Ints
A reusable swap helper keeps the sort code clean.
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a; *a = *b; *b = t;
}
int main(void) {
int x = 1, y = 2;
swap(&x, &y);
printf("%d %d\n", x, y);
return 0;
}Bubble Sort Implementation
Nested loops: the outer loop counts passes, the inner loop compares adjacent pairs and swaps. After pass i, the last i elements are sorted.
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
bubble_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Early-Exit Optimization
If a full pass makes no swaps, the array is already sorted and you can stop. This makes bubble sort O(n) on already-sorted input.
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = 1;
}
if (!swapped) break;
}
}
int main(void) {
int a[] = {1, 2, 3, 4, 5};
bubble_sort(a, 5);
printf("sorted with early exit\n");
return 0;
}How Insertion Sort Works
Insertion sort builds a sorted region at the front. For each new element it shifts larger sorted elements right and drops the new one into its place, like sorting playing cards in your hand.
Insertion Sort Implementation
Take element key = a[i], then shift every larger element in a[0..i-1] one slot right, and insert key into the gap.
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Insertion Sort on Nearly Sorted Data
Insertion sort shines when the array is almost sorted: each element moves only a few positions, approaching O(n). This is why it is used as a finishing step in hybrid sorts.
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
}
int main(void) {
int a[] = {1, 2, 4, 3, 5}; /* one out of place */
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Stability
Both sorts are stable: equal elements keep their original relative order, because they only swap or shift on a strict greater-than comparison. Stability matters when sorting records by multiple keys.
Complexity Comparison
Both are O(n squared) average and worst case, but differ in practice:
- Bubble: many swaps, rarely used in real code
- Insertion: fewer writes, great for small or nearly sorted arrays
Best case for both with optimizations is O(n).
Counting Operations
Let us count comparisons insertion sort performs on a reverse-sorted array, the worst case.
#include <stdio.h>
int main(void) {
int a[] = {5, 4, 3, 2, 1};
int n = 5; long cmp = 0;
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && (cmp++, a[j] > key)) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
printf("comparisons = %ld\n", cmp);
return 0;
}Quick Check
Test your understanding of simple sorts.
Recap
You learned two simple O(n squared) sorts.
- Bubble sort swaps adjacent pairs each pass
- Insertion sort shifts and inserts into a sorted front
- Both are stable; both reach O(n) on sorted input with optimization
- Insertion sort is the better practical choice for small data
Frequently asked questions
Is the “Bubble and Insertion Sort” lesson free?
Yes — the full text of “Bubble and Insertion Sort” is free to read here on the web, and the C Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the C Academy course, upgrade to CoddyKit PRO.
What will I learn in “Bubble and Insertion Sort”?
Simple sorts. You practise C Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start C Academy?
No prior experience is required. C Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Bubble and Insertion Sort” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this C Academy lesson?
Yes. Every C Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Bubble and Insertion Sort
- Quicksort
- Mergesort
- Using qsort