Chapter 13
HomeSorting arranges data in order. You'll almost never write your own sort in a contest — but understanding how sorting works is essential for knowing when to use it.
Repeatedly step through the array, swapping adjacent elements that are in the wrong order. Larger values "bubble" to the end with each pass.
void bubble_sort(vector<int>& arr) {
int n = arr.size();
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]);
}
}
}
}
fn bubble_sort(arr: &mut [i32]) {
let n = arr.len();
for i in 0..n - 1 {
for j in 0..n - i - 1 {
if arr[j] > arr[j + 1] {
arr.swap(j, j + 1);
}
}
}
}
On each pass, find the smallest element in the unsorted part and swap it into the correct position.
void selection_sort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
swap(arr[i], arr[min_idx]);
}
}
fn selection_sort(arr: &mut [i32]) {
let n = arr.len();
for i in 0..n - 1 {
let mut min_idx = i;
for j in i + 1..n {
if arr[j] < arr[min_idx] {
min_idx = j;
}
}
arr.swap(i, min_idx);
}
}
📐 Complexity
Both bubble sort and selection sort run in O(N²) time. For N=10⁵, that's 10¹⁰ operations — far too slow. In contests you'll use the built-in sort (O(N log N)), but these simple sorts help you understand the mechanics.