Loading W Code...
Bubble, Selection, Insertion, Merge, Quick, Counting Sort & more.
Imagine holding a hand of playing cards. To evaluate your possibilities quickly, you arrange the cards in increasing order of their ranks.
Sorting is the algorithmic process of rearranging a collection of elements into a specified order (e.g., ascending or descending).
O(log n)).#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
// Using STL sort (Introsort - hybrid of Quick, Heap, Insertion)
sort(arr.begin(), arr.end()); // Ascending
cout << "Ascending: ";
for (int x : arr) cout << x << " ";
cout << endl;
sort(arr.begin(), arr.end(), greater<int>()); // Descending
cout << "Descending: ";
for (int x : arr) cout << x << " ";
cout << endl;
return 0;
}Imagine bubbles in a glass of soda. The largest, lightest bubbles rise to the surface first.
Bubble Sort is a simple comparison-based algorithm that works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order.
arr[j] and arr[j + 1].arr[j] > arr[j + 1], swap them.n - 1 times, reducing the active scanning window size by one each time.If we complete a full pass without making a single swap, the array is already sorted. We can break out of the loop early, achieving O(n) best-case performance for sorted inputs.
#include <iostream>
#include <vector>
using namespace std;
// Optimized Bubble Sort (early termination)
void bubbleSortOptimized(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; 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 no swaps, array is sorted
if (!swapped) break;
}
}
int main() {
vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSortOptimized(arr);
cout << "Sorted: ";
for (int x : arr) cout << x << " ";
cout << endl;
return 0;
}Imagine sorting a line of actors by height. You scan the entire line, select the shortest actor, and swap them with the actor at the front of the line. You then repeat this scan starting at the second actor, swapping the next shortest actor to the second spot, and so on.
Selection Sort divides the array into sorted and unsorted regions. It repeatedly finds the smallest element in the unsorted region and swaps it to the beginning of the unsorted boundary.
O(n) swaps, making it highly efficient when write operations to memory are expensive.O(n²) time across all cases, even if the array is already sorted.#include <iostream>
#include <vector>
using namespace std;
void selectionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
// Find minimum in unsorted portion
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// Swap minimum with first unsorted element
if (minIdx != i) {
swap(arr[i], arr[minIdx]);
}
}
}
int main() {
vector<int> arr = {64, 25, 12, 22, 11};
selectionSort(arr);
cout << "Sorted: ";
for (int x : arr) cout << x << " ";
cout << endl;
return 0;
}Imagine holding a sorted hand of playing cards. When you draw a new card, you compare it against the existing cards from right to left, shifting the larger cards to the right until you find the exact slot where the new card fits.
Insertion Sort maintains a sorted sublist at the beginning of the array. It steps through the unsorted elements one by one, shifting larger elements rightward to insert the current element in its proper place.
O(n) time on nearly sorted arrays.O(1) extra memory.#include <iostream>
#include <vector>
using namespace std;
void insertionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Shift elements greater than key to right
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// Insert key at correct position
arr[j + 1] = key;
}
}
int main() {
vector<int> arr = {12, 11, 13, 5, 6};
insertionSort(arr);
cout << "Sorted: ";
for (int x : arr) cout << x << " ";
cout << endl;
return 0;
}Imagine two teachers grading exams. They split the stack of exams in half, grade and sort their respective piles, and then merge their sorted piles back together into a single, ordered stack.
Merge Sort is a comparison-based sorting algorithm that uses a divide-and-conquer strategy:
O(n log n) time in best, average, and worst-case scenarios.O(n) auxiliary space to allocate temporary merging buffers.#include <iostream>
#include <vector>
using namespace std;
// Merge two sorted subarrays
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temp arrays
vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Merge back
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Sort first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge sorted halves
merge(arr, left, mid, right);
}
}
int main() {
vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
mergeSort(arr, 0, arr.size() - 1);
cout << "Sorted: ";
for (int x : arr) cout << x << " ";
cout << endl;
return 0;
}Imagine selecting a student in a class as a "pivot". You place all students shorter than the pivot on the left and all students taller than the pivot on the right, then recursively repeat this sorting process for the left and right groups.
Quick Sort is an in-place divide-and-conquer sorting algorithm:
O(n²) performance on already sorted data.O(n log n).#include <iostream>
#include <vector>
using namespace std;
// Partition function (Lomuto scheme)
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high]; // Choose last element as pivot
int i = low - 1; // Index of smaller element
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Sort left
quickSort(arr, pi + 1, high); // Sort right
}
}
int main() {
vector<int> arr = {10, 7, 8, 9, 1, 5};
int n = arr.size();
quickSort(arr, 0, n - 1);
cout << "Sorted: ";
for (int x : arr) cout << x << " ";
cout << endl;
return 0;
}Imagine a tournament pyramid where the strongest player always sits at the peak (Max-Heap root). When they win, they leave the tournament and join the sorted winners list. The remaining players then compete to determine the next strongest player at the peak.
Heap Sort uses a binary heap data structure to sort elements:
O(n) time).O(n log n) time across all cases without degradation.O(1) auxiliary space, making it space-efficient.#include <iostream>
#include <vector>
using namespace std;
// Heapify subtree rooted at index i
void heapify(vector<int>& arr, int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // Left child
int right = 2 * i + 2; // Right child
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(vector<int>& arr) {
int n = arr.size();
// Build max heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Extract elements from heap one by one
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
vector<int> arr = {12, 11, 13, 5, 6, 7};
heapSort(arr);
cout << "Sorted: ";
for (int x : arr) cout << x << " ";
cout << endl;
return 0;
}Imagine sorting laundry by color. Instead of comparing a red shirt against a blue shirt, you simply count the number of red, blue, and green shirts you have, then place that exact count of each shirt color back in sorted piles.
Counting Sort is a non-comparison sorting algorithm that counts the occurrences of each unique value in a temporary index array:
k = max - min + 1).k and count occurrences.O(n + k) space, which becomes highly inefficient if the range k is large.#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void countingSort(vector<int>& arr) {
if (arr.empty()) return;
int minVal = *min_element(arr.begin(), arr.end());
int maxVal = *max_element(arr.begin(), arr.end());
int range = maxVal - minVal + 1;
vector<int> count(range, 0);
vector<int> output(arr.size());
for (int x : arr) {
count[x - minVal]++;
}
for (int i = 1; i < range; i++) {
count[i] += count[i - 1];
}
for (int i = arr.size() - 1; i >= 0; i--) {
output[count[arr[i] - minVal] - 1] = arr[i];
count[arr[i] - minVal]--;
}
arr = output;
}
int main() {
vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
countingSort(arr);
cout << "Sorted: ";
for (int x : arr) cout << x << " ";
cout << endl;
return 0;
}No single sorting algorithm is optimal for every scenario. Developers must weigh speed, stability, and memory constraints:
O(n) time complexity).O(1) auxiliary space).#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void stlSorting() {
vector<int> arr = {5, 2, 8, 1, 9, 3};
// sort - O(n log n) average, unstable
sort(arr.begin(), arr.end());
// stable_sort - O(n log n), stable
stable_sort(arr.begin(), arr.end());
// partial_sort - Sort first k elements
partial_sort(arr.begin(), arr.begin() + 3, arr.end()); // First 3 sorted
// nth_element - Find nth element in sorted order (Quick Select)
nth_element(arr.begin(), arr.begin() + 2, arr.end()); // arr[2] is median
}
int main() {
stlSorting();
return 0;
}