Select an option
▼
- Bubble Sort
- Insertion Sort
- Selection Sort
- Merge Sort
- Quick Sort
- Counting Sort
- Bucket Sort
- Radix Sort
- Heap Sort
- Tree Sort
Bubble Sort Algorithm
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high.
Video: Bubble Sort Algorithm Explained
How Bubble Sort Works?
First Pass:
- ( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
- ( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), Swap since 5 > 4
- ( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), Swap since 5 > 2
- ( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass:
- ( 1 4 2 5 8 ) → ( 1 4 2 5 8 )
- ( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), Swap since 4 > 2
- ( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
- ( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
- ( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
- ( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
- ( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
- ( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
Note: Bubble sort is not a practical sorting algorithm when n is large. It will not be efficient in the case of a reverse-ordered collection.
Bubble Sort Implementations
#include <bits/stdc++.h>
using namespace std;
void bubbleSort(vector<int>& arr) {
int n = arr.size();
bool swapped;
for (int i = 0; i < n - 1; i++) {
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;
}
}
int main() {
vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
cout << "Sorted array: ";
for (int num : arr) cout << num << " ";
return 0;
}def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n-1; i++) {
swapped = false;
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.print("Sorted array: ");
for (int num : arr) System.out.print(num + " ");
}
}function bubbleSort(arr) {
let n = arr.length;
let swapped;
for (let i = 0; i < n-1; i++) {
swapped = false;
for (let j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]];
swapped = true;
}
}
if (!swapped) break;
}
}
let arr = [64, 34, 25, 12, 22, 11, 90];
bubbleSort(arr);
console.log("Sorted array:", arr);using System;
class BubbleSort {
static void BubbleSort(int[] arr) {
int n = arr.Length;
bool swapped;
for (int i = 0; i < n-1; i++) {
swapped = false;
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
static void Main() {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
BubbleSort(arr);
Console.Write("Sorted array: ");
foreach (int num in arr) Console.Write(num + " ");
}
}<?php
function bubbleSort(&$arr) {
$n = count($arr);
$swapped;
for ($i = 0; $i < $n-1; $i++) {
$swapped = false;
for ($j = 0; $j < $n-$i-1; $j++) {
if ($arr[$j] > $arr[$j+1]) {
list($arr[$j], $arr[$j+1]) = array($arr[$j+1], $arr[$j]);
$swapped = true;
}
}
if (!$swapped) break;
}
}
$arr = array(64, 34, 25, 12, 22, 11, 90);
bubbleSort($arr);
echo "Sorted array: " . implode(" ", $arr);
?>How Logic Works?
Bubble Sort is a basic comparison-based sorting algorithm that works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. This process continues until the entire list is sorted. The algorithm ensures that with each pass, the largest unsorted element moves to its correct position at the end of the list, similar to how bubbles rise to the surface in water—hence the name "Bubble Sort." However, this algorithm is inefficient for large datasets because it repeatedly checks and swaps elements, leading to a high time complexity of O(n²) in both the worst and average cases. Due to this inefficiency, Bubble Sort is mainly used for small lists or educational purposes to demonstrate sorting logic.
Note: Bubble sort is not a practical sorting algorithm when n is large. It will not be efficient in the case of a reverse-ordered collection.
Bucket Sort Algorithm
Bucket Sort is a distribution sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm or by recursively applying the bucket sort algorithm.
Video: Bucket Sort Visualization
How Bucket Sort Works?
Step-by-Step Example (Sorting [0.42, 0.32, 0.75, 0.12, 0.89, 0.63]):
Step 1: Create Buckets
- Create 10 buckets (0.0-0.1, 0.1-0.2,...,0.9-1.0)
Step 2: Scatter Elements
- 0.42 → bucket 4
- 0.32 → bucket 3
- 0.75 → bucket 7
- 0.12 → bucket 1
- 0.89 → bucket 8
- 0.63 → bucket 6
Step 3: Sort Individual Buckets
- Bucket 1: [0.12]
- Bucket 3: [0.32]
- Bucket 4: [0.42]
- Bucket 6: [0.63]
- Bucket 7: [0.75]
- Bucket 8: [0.89]
Step 4: Gather Elements
- Concatenate all buckets in order
- Final sorted array: [0.12, 0.32, 0.42, 0.63, 0.75, 0.89]
Performance Analysis:
- Average Time Complexity: O(n + k) where k is number of buckets
- Worst Case: O(n²) when all elements fall in same bucket
- Space Complexity: O(n + k)
- Stability depends on inner sorting algorithm
Bucket Sort Implementations
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void bucketSort(vector<float>& arr) {
int n = arr.size();
// 1) Create n empty buckets
vector<vector<float>> buckets(n);
// 2) Put array elements in different buckets
for (int i = 0; i < n; i++) {
int bucketIndex = n * arr[i]; // Index in bucket
buckets[bucketIndex].push_back(arr[i]);
}
// 3) Sort individual buckets
for (int i = 0; i < n; i++)
sort(buckets[i].begin(), buckets[i].end());
// 4) Concatenate all buckets into arr[]
int index = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < buckets[i].size(); j++)
arr[index++] = buckets[i][j];
}
int main() {
vector<float> arr = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
bucketSort(arr);
cout << "Sorted array: ";
for (float num : arr)
cout << num << " ";
return 0;
}def bucket_sort(arr):
# Create empty buckets
n = len(arr)
buckets = [[] for _ in range(n)]
# Put array elements in different buckets
for num in arr:
bucket_index = int(n * num)
buckets[bucket_index].append(num)
# Sort individual buckets
for bucket in buckets:
bucket.sort()
# Concatenate all buckets into arr
index = 0
for bucket in buckets:
for num in bucket:
arr[index] = num
index += 1
arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
bucket_sort(arr)
print("Sorted array:", arr)import java.util.*;
public class BucketSort {
static void bucketSort(float[] arr) {
int n = arr.length;
// Create n empty buckets
ArrayList<ArrayList<Float>> buckets = new ArrayList<>(n);
for (int i = 0; i < n; i++)
buckets.add(new ArrayList<>());
// Put array elements in different buckets
for (int i = 0; i < n; i++) {
int bucketIndex = (int) (n * arr[i]);
buckets.get(bucketIndex).add(arr[i]);
}
// Sort individual buckets
for (int i = 0; i < n; i++)
Collections.sort(buckets.get(i));
// Concatenate all buckets into arr[]
int index = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < buckets.get(i).size(); j++)
arr[index++] = buckets.get(i).get(j);
}
public static void main(String[] args) {
float[] arr = {0.897f, 0.565f, 0.656f, 0.1234f, 0.665f, 0.3434f};
bucketSort(arr);
System.out.print("Sorted array: ");
for (float num : arr)
System.out.print(num + " ");
}
}function bucketSort(arr) {
let n = arr.length;
// Create n empty buckets
let buckets = new Array(n);
for (let i = 0; i < n; i++) {
buckets[i] = [];
}
// Put array elements in different buckets
for (let i = 0; i < n; i++) {
let bucketIndex = Math.floor(n * arr[i]);
buckets[bucketIndex].push(arr[i]);
}
// Sort individual buckets
for (let i = 0; i < n; i++) {
buckets[i].sort((a, b) => a - b);
}
// Concatenate all buckets into arr[]
let index = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < buckets[i].length; j++) {
arr[index++] = buckets[i][j];
}
}
}
let arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434];
bucketSort(arr);
console.log("Sorted array:", arr);using System;
using System.Collections.Generic;
using System.Linq;
class BucketSort {
static void Sort(float[] arr) {
int n = arr.Length;
// Create n empty buckets
List<float>[] buckets = new List<float>[n];
for (int i = 0; i < n; i++)
buckets[i] = new List<float>();
// Put array elements in different buckets
for (int i = 0; i < n; i++) {
int bucketIndex = (int) (n * arr[i]);
buckets[bucketIndex].Add(arr[i]);
}
// Sort individual buckets
for (int i = 0; i < n; i++)
buckets[i].Sort();
// Concatenate all buckets into arr[]
int index = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < buckets[i].Count; j++)
arr[index++] = buckets[i][j];
}
static void Main() {
float[] arr = {0.897f, 0.565f, 0.656f, 0.1234f, 0.665f, 0.3434f};
Sort(arr);
Console.Write("Sorted array: ");
foreach (float num in arr)
Console.Write(num + " ");
}
}function bucketSort(&$arr) {
$n = count($arr);
// Create n empty buckets
$buckets = array_fill(0, $n, array());
// Put array elements in different buckets
foreach ($arr as $num) {
$bucketIndex = floor($n * $num);
array_push($buckets[$bucketIndex], $num);
}
// Sort individual buckets
for ($i = 0; $i < $n; $i++) {
sort($buckets[$i]);
}
// Concatenate all buckets into arr[]
$index = 0;
for ($i = 0; $i < $n; $i++) {
foreach ($buckets[$i] as $num) {
$arr[$index++] = $num;
}
}
}
$arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434];
bucketSort($arr);
echo "Sorted array: " . implode(" ", $arr);Optimization Techniques
Bucket Size Selection
Optimal bucket count is typically equal to array size with range/n buckets.
Hybrid Approach
Use Insertion Sort for small buckets and QuickSort for larger ones.
Practical Applications
- Sorting floating-point numbers uniformly distributed in [0,1)
- External sorting when data doesn't fit in memory
- Histogram generation
- As part of more complex algorithms
Note: Bucket sort performs best when the input is uniformly distributed across the range, making the elements distribute evenly into buckets. With non-uniform distributions, performance degrades to O(n²) in the worst case.
Counting Sort Algorithm
Counting Sort is a non-comparison based integer sorting algorithm that works by counting the number of objects having distinct key values, then calculating the positions of each key in the output sequence. It operates in O(n + k) time where k is the range of input.
Video: Counting Sort Visualization
How Counting Sort Works?
Step-by-Step Example (Sorting [4, 2, 2, 8, 3, 3, 1]):
Step 1: Find Maximum Value (8)
Step 2: Initialize Count Array
- Create array of size 9 (max+1) initialized to 0
Step 3: Store Counts
- Count of 1: 1
- Count of 2: 2
- Count of 3: 2
- Count of 4: 1
- Count of 8: 1
- Count array: [0, 1, 2, 2, 1, 0, 0, 0, 1]
Step 4: Cumulative Count
- Transform count to cumulative: [0, 1, 3, 5, 6, 6, 6, 6, 7]
Step 5: Build Output Array
- Place elements in sorted order using cumulative counts
- Final sorted array: [1, 2, 2, 3, 3, 4, 8]
Key Characteristics:
- Time Complexity: O(n + k) where k is range of input
- Space Complexity: O(n + k)
- Stable (can be implemented as unstable)
- Not comparison-based
- Only works for non-negative integers (or with modification)
Counting Sort Implementations
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void countingSort(vector<int>& arr) {
int max = *max_element(arr.begin(), arr.end());
int min = *min_element(arr.begin(), arr.end());
int range = max - min + 1;
vector<int> count(range), output(arr.size());
for(int i = 0; i < arr.size(); i++)
count[arr[i] - min]++;
for(int i = 1; i < count.size(); i++)
count[i] += count[i - 1];
for(int i = arr.size() - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for(int i = 0; i < arr.size(); i++)
arr[i] = output[i];
}
int main() {
vector<int> arr = {-5, -10, 0, -3, 8, 5, -1, 10};
countingSort(arr);
cout << "Sorted array: ";
for (int num : arr) cout << num << " ";
return 0;
}def counting_sort(arr):
max_val = max(arr)
min_val = min(arr)
range_size = max_val - min_val + 1
count = [0] * range_size
output = [0] * len(arr)
for num in arr:
count[num - min_val] += 1
for i in range(1, len(count)):
count[i] += count[i - 1]
for i in range(len(arr) - 1, -1, -1):
output[count[arr[i] - min_val] - 1] = arr[i]
count[arr[i] - min_val] -= 1
for i in range(len(arr)):
arr[i] = output[i]
arr = [-5, -10, 0, -3, 8, 5, -1, 10]
counting_sort(arr)
print("Sorted array:", arr)import java.util.Arrays;
public class CountingSort {
static void countingSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int range = max - min + 1;
int[] count = new int[range];
int[] output = new int[arr.length];
for (int i = 0; i < arr.length; i++)
count[arr[i] - min]++;
for (int i = 1; i < count.length; i++)
count[i] += count[i - 1];
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (int i = 0; i < arr.length; i++)
arr[i] = output[i];
}
public static void main(String[] args) {
int[] arr = {-5, -10, 0, -3, 8, 5, -1, 10};
countingSort(arr);
System.out.print("Sorted array: ");
for (int num : arr) System.out.print(num + " ");
}
}function countingSort(arr) {
const max = Math.max(...arr);
const min = Math.min(...arr);
const range = max - min + 1;
const count = new Array(range).fill(0);
const output = new Array(arr.length);
for (let i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
for (let i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
for (let i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (let i = 0; i < arr.length; i++) {
arr[i] = output[i];
}
}
let arr = [-5, -10, 0, -3, 8, 5, -1, 10];
countingSort(arr);
console.log("Sorted array:", arr);using System;
using System.Linq;
class CountingSort {
static void Sort(int[] arr) {
int max = arr.Max();
int min = arr.Min();
int range = max - min + 1;
int[] count = new int[range];
int[] output = new int[arr.Length];
for (int i = 0; i < arr.Length; i++) {
count[arr[i] - min]++;
}
for (int i = 1; i < count.Length; i++) {
count[i] += count[i - 1];
}
for (int i = arr.Length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (int i = 0; i < arr.Length; i++) {
arr[i] = output[i];
}
}
static void Main() {
int[] arr = {-5, -10, 0, -3, 8, 5, -1, 10};
Sort(arr);
Console.Write("Sorted array: ");
foreach (int num in arr) {
Console.Write(num + " ");
}
}
}function countingSort(&$arr) {
$max = max($arr);
$min = min($arr);
$range = $max - $min + 1;
$count = array_fill(0, $range, 0);
$output = array_fill(0, count($arr), 0);
foreach ($arr as $num) {
$count[$num - $min]++;
}
for ($i = 1; $i < count($count); $i++) {
$count[$i] += $count[$i - 1];
}
for ($i = count($arr) - 1; $i >= 0; $i--) {
$output[$count[$arr[$i] - $min] - 1] = $arr[$i];
$count[$arr[$i] - $min]--;
}
for ($i = 0; $i < count($arr); $i++) {
$arr[$i] = $output[$i];
}
}
$arr = [-5, -10, 0, -3, 8, 5, -1, 10];
countingSort($arr);
echo "Sorted array: " . implode(" ", $arr);Variations
Negative Number Handling
Shift all numbers by minimum value to handle negative integers.
In-Place Counting Sort
Modification that reduces space complexity but is more complex.
Practical Applications
- Sorting numbers with small range (e.g., ages, test scores)
- As a subroutine in Radix Sort
- Histogram generation
- Frequency counting problems
Note: Counting sort is extremely fast when the range of input data (k) is not significantly greater than the number of objects (n). However, it becomes impractical when k is very large compared to n.
Heap Sort Algorithm
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving it to the sorted region.
Video: Heap Sort Visualization
How Heap Sort Works?
Step-by-Step Example (Sorting [4, 10, 3, 5, 1]):
Step 1: Build Max Heap
- Original array visualized as complete binary tree
- Heapify from last non-leaf node to root
- After heapify: [10, 5, 3, 4, 1]
Step 2: Extract Elements
- Swap root (10) with last element (1)
- Heapify reduced heap [1, 5, 3, 4] → [5, 4, 3, 1]
- Swap root (5) with last element (1)
- Heapify [1, 4, 3] → [4, 1, 3]
- Continue until fully sorted
- Final sorted array: [1, 3, 4, 5, 10]
Performance Analysis:
- Time Complexity: O(n log n) in all cases
- Space Complexity: O(1) (in-place)
- Not stable
- Guaranteed O(n log n) unlike QuickSort's worst case
- Slower in practice than well-implemented QuickSort
Sorting Algorithm Implementations
Heap Sort Implementations
#include <iostream>
#include <vector>
using namespace std;
void heapify(vector<int>& arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
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();
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
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 array: ";
for (int num : arr) cout << num << " ";
return 0;
}def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array:", arr)public class HeapSort {
public void sort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
public static void main(String args[]) {
int[] arr = {12, 11, 13, 5, 6, 7};
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.print("Sorted array: ");
for (int num : arr) System.out.print(num + " ");
}
}function heapify(arr, n, i) {
let largest = i;
let left = 2 * i + 1;
let right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest);
}
}
function heapSort(arr) {
let n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--)
heapify(arr, n, i);
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, i, 0);
}
}
let arr = [12, 11, 13, 5, 6, 7];
heapSort(arr);
console.log("Sorted array:", arr);using System;
class HeapSort {
static void Heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
Heapify(arr, n, largest);
}
}
static void Sort(int[] arr) {
int n = arr.Length;
for (int i = n / 2 - 1; i >= 0; i--)
Heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
Heapify(arr, i, 0);
}
}
static void Main() {
int[] arr = {12, 11, 13, 5, 6, 7};
Sort(arr);
Console.Write("Sorted array: ");
foreach (int num in arr) {
Console.Write(num + " ");
}
}
}function heapify(&$arr, $n, $i) {
$largest = $i;
$left = 2 * $i + 1;
$right = 2 * $i + 2;
if ($left < $n && $arr[$left] > $arr[$largest]) {
$largest = $left;
}
if ($right < $n && $arr[$right] > $arr[$largest]) {
$largest = $right;
}
if ($largest != $i) {
$temp = $arr[$i];
$arr[$i] = $arr[$largest];
$arr[$largest] = $temp;
heapify($arr, $n, $largest);
}
}
function heapSort(&$arr) {
$n = count($arr);
for ($i = intval($n / 2) - 1; $i >= 0; $i--) {
heapify($arr, $n, $i);
}
for ($i = $n - 1; $i > 0; $i--) {
$temp = $arr[0];
$arr[0] = $arr[$i];
$arr[$i] = $temp;
heapify($arr, $i, 0);
}
}
$arr = [12, 11, 13, 5, 6, 7];
heapSort($arr);
echo "Sorted array: " . implode(" ", $arr);Optimization Techniques
Bottom-Up Heap Construction
Builds the heap in O(n) time rather than O(n log n).
Ternary Heaps
Uses 3 children per node to reduce height and operations.
Practical Applications
- When worst-case O(n log n) is required
- Embedded systems (predictable performance)
- As part of hybrid algorithms like Introsort
- Priority queue implementations
- Systems where memory is constrained (in-place)
Note: While heap sort has the advantage of predictable O(n log n) performance and in-place operation, it tends to be slower in practice than quick sort due to poor cache performance (more random memory access patterns) and higher constant factors.
Insertion Sort Algorithm
Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms like quicksort, heapsort, or merge sort, but it has several advantages including being efficient for small data sets and adaptive for data sets that are already substantially sorted.
Video: Insertion Sort Visualization
How Insertion Sort Works?
Step-by-Step Example:
Let's sort the array: [12, 11, 13, 5, 6]
First Iteration:
- Start with second element (11)
- Compare with 12 → 11 < 12 → shift 12 right
- Array becomes: [11, 12, 13, 5, 6]
Second Iteration:
- Next element is 13
- Compare with 12 → 13 > 12 → no shift
- Array remains: [11, 12, 13, 5, 6]
Third Iteration:
- Next element is 5
- Compare with 13 → shift right
- Compare with 12 → shift right
- Compare with 11 → shift right
- Array becomes: [5, 11, 12, 13, 6]
Fourth Iteration:
- Next element is 6
- Compare with 13 → shift right
- Compare with 12 → shift right
- Compare with 11 → shift right
- Compare with 5 → insert
- Final sorted array: [5, 6, 11, 12, 13]
Key Characteristics:
- Time Complexity: O(n²) worst and average cases, O(n) best case (when nearly sorted)
- Space Complexity: O(1) (in-place)
- Stable: Maintains relative order of equal elements
- Adaptive: Performance improves when input is partially sorted
Insertion Sort Implementations
#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;
// Move elements of arr[0..i-1] that are greater than key
// to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
int main() {
vector<int> arr = {12, 11, 13, 5, 6};
insertionSort(arr);
cout << "Sorted array: ";
for (int num : arr) cout << num << " ";
return 0;
}def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# Move elements of arr[0..i-1] that are greater than key
# to one position ahead of their current position
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array:", arr)public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1] that are greater than key
// to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
insertionSort(arr);
System.out.print("Sorted array: ");
for (int num : arr) System.out.print(num + " ");
}
}function insertionSort(arr) {
let n = arr.length;
for (let i = 1; i < n; i++) {
let key = arr[i];
let j = i - 1;
// Move elements of arr[0..i-1] that are greater than key
// to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
let arr = [12, 11, 13, 5, 6];
insertionSort(arr);
console.log("Sorted array:", arr);using System;
class InsertionSort {
static void Sort(int[] arr) {
int n = arr.Length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1] that are greater than key
// to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
static void Main() {
int[] arr = {12, 11, 13, 5, 6};
Sort(arr);
Console.Write("Sorted array: ");
foreach (int num in arr) Console.Write(num + " ");
}
}<?php
function insertionSort(&$arr) {
$n = count($arr);
for ($i = 1; $i < $n; $i++) {
$key = $arr[$i];
$j = $i - 1;
// Move elements of arr[0..i-1] that are greater than key
// to one position ahead of their current position
while ($j >= 0 && $arr[$j] > $key) {
$arr[$j + 1] = $arr[$j];
$j = $j - 1;
}
$arr[$j + 1] = $key;
}
}
$arr = array(12, 11, 13, 5, 6);
insertionSort($arr);
echo "Sorted array: " . implode(" ", $arr);
?>Optimization Techniques
Binary Insertion Sort
Uses binary search to find the proper location to insert the selected item, reducing the number of comparisons from O(n) to O(log n) in the worst case.
Shell Sort
A generalization of insertion sort that allows exchange of items that are far apart, improving performance to about O(n^(7/6)) for the best known sequence.
Practical Applications
- Small datasets (typically less than 50 elements)
- Nearly sorted datasets where it performs in near-linear time
- As the base case for hybrid sorting algorithms like Timsort
- Online algorithms where new elements are added to a sorted list
Note: While insertion sort is inefficient for large random lists, it is one of the fastest algorithms for small arrays (about 10-20 elements) due to its low overhead.
Merge Sort Algorithm
Merge Sort is a divide-and-conquer algorithm that recursively divides the input array into two halves, sorts each half, and then merges them back together. It guarantees O(n log n) time complexity in all cases, making it efficient for large datasets.
Video: Merge Sort Visualization
How Merge Sort Works?
Step-by-Step Example (Sorting [38, 27, 43, 3, 9, 82, 10]):
Division Phase:
- Original array: [38, 27, 43, 3, 9, 82, 10]
- First split: [38, 27, 43, 3] and [9, 82, 10]
- Second split: [38, 27], [43, 3], [9, 82], [10]
- Third split: [38], [27], [43], [3], [9], [82], [10]
Merge Phase:
- Merge [38] and [27] → [27, 38]
- Merge [43] and [3] → [3, 43]
- Merge [9] and [82] → [9, 82]
- Merge [27, 38] and [3, 43] → [3, 27, 38, 43]
- Merge [9, 82] and [10] → [9, 10, 82]
- Final merge: [3, 9, 10, 27, 38, 43, 82]
Key Characteristics:
- Time Complexity: O(n log n) in all cases
- Space Complexity: O(n) auxiliary space
- Stable: Maintains relative order of equal elements
- Not in-place (standard implementation)
- Excellent for linked lists and external sorting
Merge Sort Implementations
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(vector<int>& arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
vector<int> arr = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 0, arr.size() - 1);
cout << "Sorted array: ";
for (int num : arr) cout << num << " ";
return 0;
}def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("Sorted array:", arr)public class MergeSort {
void merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void sort(int[] arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
sort(arr, l, m);
sort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
public static void main(String args[]) {
int[] arr = {12, 11, 13, 5, 6, 7};
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length - 1);
System.out.print("Sorted array: ");
for (int num : arr) System.out.print(num + " ");
}
}function merge(arr, l, m, r) {
let n1 = m - l + 1;
let n2 = r - m;
let L = new Array(n1);
let R = new Array(n2);
for (let i = 0; i < n1; i++)
L[i] = arr[l + i];
for (let j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
let i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
function mergeSort(arr, l, r) {
if (l < r) {
let m = l + Math.floor((r - l) / 2);
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
let arr = [12, 11, 13, 5, 6, 7];
mergeSort(arr, 0, arr.length - 1);
console.log("Sorted array:", arr);using System;
class MergeSort {
static void Merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
static void Sort(int[] arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
Sort(arr, l, m);
Sort(arr, m + 1, r);
Merge(arr, l, m, r);
}
}
static void Main() {
int[] arr = {12, 11, 13, 5, 6, 7};
Sort(arr, 0, arr.Length - 1);
Console.Write("Sorted array: ");
foreach (int num in arr) {
Console.Write(num + " ");
}
}
}function merge(&$arr, $l, $m, $r) {
$n1 = $m - $l + 1;
$n2 = $r - $m;
$L = array_fill(0, $n1, 0);
$R = array_fill(0, $n2, 0);
for ($i = 0; $i < $n1; $i++)
$L[$i] = $arr[$l + $i];
for ($j = 0; $j < $n2; $j++)
$R[$j] = $arr[$m + 1 + $j];
$i = 0; $j = 0; $k = $l;
while ($i < $n1 && $j < $n2) {
if ($L[$i] <= $R[$j]) {
$arr[$k] = $L[$i];
$i++;
} else {
$arr[$k] = $R[$j];
$j++;
}
$k++;
}
while ($i < $n1) {
$arr[$k] = $L[$i];
$i++;
$k++;
}
while ($j < $n2) {
$arr[$k] = $R[$j];
$j++;
$k++;
}
}
function mergeSort(&$arr, $l, $r) {
if ($l < $r) {
$m = $l + intval(($r - $l) / 2);
mergeSort($arr, $l, $m);
mergeSort($arr, $m + 1, $r);
merge($arr, $l, $m, $r);
}
}
$arr = [12, 11, 13, 5, 6, 7];
mergeSort($arr, 0, count($arr) - 1);
echo "Sorted array: " . implode(" ", $arr);Optimization Techniques
Hybrid Merge Sort
Uses Insertion Sort for small subarrays (typically < 15 elements) to reduce recursion overhead.
In-Place Merge Sort
More complex implementation that reduces space complexity to O(1) but with performance tradeoffs.
Natural Merge Sort
Takes advantage of existing ordered runs in the input data for improved performance on partially sorted data.
Practical Applications
- Sorting large datasets that don't fit in memory (external sorting)
- Implementation in standard libraries (Java's Arrays.sort() for objects)
- Sorting linked lists (requires only O(1) extra space)
- Inversion count problems
- Used as the basis for Timsort (Python, Android, Java)
Note: While merge sort has excellent O(n log n) time complexity, its O(n) space requirement makes it less desirable than quicksort for in-memory sorting of arrays in many practical implementations.
Quick Sort Algorithm
Quick Sort is a highly efficient divide-and-conquer sorting algorithm that works by selecting a 'pivot' element and partitioning the array around the pivot, placing smaller elements before it and larger elements after it. The algorithm then recursively sorts the subarrays.
Video: Quick Sort Visualization
How Quick Sort Works?
Detailed Example (Sorting [10, 80, 30, 90, 40, 50, 70]):
First Partition (Pivot = 70):
- Initialize: i = -1, j = 0, pivot = 70
- 10 < 70 → swap arr[0] with arr[0] → i=0 → [10, 80, 30, 90, 40, 50, 70]
- 80 > 70 → no swap
- 30 < 70 → swap arr[1] with arr[2] → i=1 → [10, 30, 80, 90, 40, 50, 70]
- 90 > 70 → no swap
- 40 < 70 → swap arr[2] with arr[4] → i=2 → [10, 30, 40, 90, 80, 50, 70]
- 50 < 70 → swap arr[3] with arr[5] → i=3 → [10, 30, 40, 50, 80, 90, 70]
- Final swap: pivot with arr[i+1] → [10, 30, 40, 50, 70, 90, 80]
Recursive Calls:
- Left subarray [10, 30, 40, 50]
- Right subarray [90, 80]
- Repeat process until fully sorted
Performance Characteristics:
- Average Time Complexity: O(n log n)
- Worst Case: O(n²) (rare with good pivot selection)
- Space Complexity: O(log n) (stack space for recursion)
- Not stable but in-place
- Cache-efficient due to sequential memory access
Quick Sort Implementations
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j <= high - 1; 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);
quickSort(arr, pi + 1, high);
}
}
int main() {
vector<int> arr = {10, 7, 8, 9, 1, 5};
int n = arr.size();
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
for (int num : arr) cout << num << " ";
return 0;
}def partition(arr, low, high):
i = low - 1
pivot = arr[high]
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi-1)
quick_sort(arr, pi+1, high)
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quick_sort(arr, 0, n-1)
print("Sorted array:", arr)public class QuickSort {
int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
void sort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
public static void main(String args[]) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n - 1);
System.out.print("Sorted array: ");
for (int num : arr) System.out.print(num + " ");
}
}function partition(arr, low, high) {
let pivot = arr[high];
let i = low - 1;
for (let j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
function quickSort(arr, low, high) {
if (low < high) {
let pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
let arr = [10, 7, 8, 9, 1, 5];
let n = arr.length;
quickSort(arr, 0, n - 1);
console.log("Sorted array:", arr);using System;
class QuickSort {
static int Partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp2 = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp2;
return i + 1;
}
static void Sort(int[] arr, int low, int high) {
if (low < high) {
int pi = Partition(arr, low, high);
Sort(arr, low, pi - 1);
Sort(arr, pi + 1, high);
}
}
static void Main() {
int[] arr = {10, 7, 8, 9, 1, 5};
Console.WriteLine("Original array: " + string.Join(" ", arr));
Sort(arr, 0, arr.Length - 1);
Console.WriteLine("Sorted array: " + string.Join(" ", arr));
}
}function partition(&$arr, $low, $high) {
$pivot = $arr[$high];
$i = $low - 1;
for ($j = $low; $j < $high; $j++) {
if ($arr[$j] < $pivot) {
$i++;
[$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
}
}
[$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];
return $i + 1;
}
function quickSort(&$arr, $low, $high) {
if ($low < $high) {
$pi = partition($arr, $low, $high);
quickSort($arr, $low, $pi - 1);
quickSort($arr, $pi + 1, $high);
}
}
$arr = [10, 7, 8, 9, 1, 5];
$n = count($arr);
echo "Original array: " . implode(" ", $arr) . PHP_EOL;
quickSort($arr, 0, $n - 1);
echo "Sorted array: " . implode(" ", $arr) . PHP_EOL;Optimization Techniques
Pivot Selection Strategies
- Median-of-Three: Choose median of first, middle, and last elements
- Randomized QuickSort: Random pivot avoids worst-case scenarios
- Introsort: Hybrid that switches to heapsort for bad cases
Three-Way Partitioning
Special handling for arrays with many duplicate keys (Dutch National Flag problem).
Tail Recursion Optimization
Reduces worst-case stack space to O(log n).
Practical Applications
- Default sorting algorithm in many languages (C qsort, Java primitives)
- When average performance matters more than worst-case
- In-memory sorting of large arrays
- Used in hybrid algorithms like Introsort
Note: QuickSort is generally preferred over MergeSort for sorting arrays due to better cache performance and in-place operation, though it's not stable and has O(n²) worst-case (mitigated by proper pivot selection).
Radix Sort Algorithm
Radix Sort is a non-comparative integer sorting algorithm that processes digits by grouping numbers by each digit, from least significant to most significant (LSD) or vice versa (MSD). It avoids comparison by creating and distributing elements into buckets according to their radix.
Video: Radix Sort Visualization
How Radix Sort Works?
LSD Radix Sort Example (Sorting [170, 45, 75, 90, 802, 24, 2, 66]):
Step 1: Sort by least significant digit (1s place)
- Original: 170, 045, 075, 090, 802, 024, 002, 066
- After 1st pass: 170, 090, 802, 002, 024, 045, 075, 066
Step 2: Sort by next digit (10s place)
- After 2nd pass: 802, 002, 024, 045, 066, 170, 075, 090
Step 3: Sort by most significant digit (100s place)
- After 3rd pass: 002, 024, 045, 066, 075, 090, 170, 802
- Final sorted array: [2, 24, 45, 66, 75, 90, 170, 802]
Key Characteristics:
- Time Complexity: O(d*(n + b)) where d is digits, b is base
- Space Complexity: O(n + b)
- Stable (when implemented properly)
- Not in-place
- Works for integers, strings, and fixed-length data
Radix Sort Implementations
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int getMax(vector<int>& arr) {
return *max_element(arr.begin(), arr.end());
}
void countSort(vector<int>& arr, int exp) {
int n = arr.size();
vector<int> output(n);
int count[10] = {0};
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void radixSort(vector<int>& arr) {
int m = getMax(arr);
for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, exp);
}
int main() {
vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
cout << "Sorted array: ";
for (int num : arr) cout << num << " ";
return 0;
}def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
index = (arr[i] // exp) % 10
count[index] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
i -= 1
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("Sorted array:", arr)public class RadixSort {
static int getMax(int[] arr) {
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
return max;
}
static void countSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
static void radixSort(int[] arr) {
int m = getMax(arr);
for (int exp = 1; m / exp > 0; exp *= 10) {
countSort(arr, exp);
}
}
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
System.out.print("Sorted array: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}function getMax(arr) {
let max = arr[0];
for (let num of arr) {
if (num > max) {
max = num;
}
}
return max;
}
function countSort(arr, exp) {
let n = arr.length;
let output = new Array(n).fill(0);
let count = new Array(10).fill(0);
for (let i = 0; i < n; i++) {
let index = Math.floor(arr[i] / exp) % 10;
count[index]++;
}
for (let i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (let i = n - 1; i >= 0; i--) {
let index = Math.floor(arr[i] / exp) % 10;
output[count[index] - 1] = arr[i];
count[index]--;
}
for (let i = 0; i < n; i++) {
arr[i] = output[i];
}
}
function radixSort(arr) {
let max = getMax(arr);
for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
countSort(arr, exp);
}
}
let arr = [170, 45, 75, 90, 802, 24, 2, 66];
radixSort(arr);
console.log("Sorted array:", arr);using System;
class RadixSort {
static int GetMax(int[] arr) {
int max = arr[0];
foreach (int num in arr) {
if (num > max) {
max = num;
}
}
return max;
}
static void CountSort(int[] arr, int exp) {
int n = arr.Length;
int[] output = new int[n];
int[] count = new int[10];
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
static void Sort(int[] arr) {
int m = GetMax(arr);
for (int exp = 1; m / exp > 0; exp *= 10) {
CountSort(arr, exp);
}
}
static void Main() {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
Sort(arr);
Console.Write("Sorted array: ");
foreach (int num in arr) {
Console.Write(num + " ");
}
}
}function getMax($arr) {
$max = $arr[0];
foreach ($arr as $num) {
if ($num > $max) {
$max = $num;
}
}
return $max;
}
function countSort(&$arr, $exp) {
$n = count($arr);
$output = array_fill(0, $n, 0);
$count = array_fill(0, 10, 0);
for ($i = 0; $i < $n; $i++) {
$index = (int)($arr[$i] / $exp) % 10;
$count[$index]++;
}
for ($i = 1; $i < 10; $i++) {
$count[$i] += $count[$i - 1];
}
for ($i = $n - 1; $i >= 0; $i--) {
$index = (int)($arr[$i] / $exp) % 10;
$output[$count[$index] - 1] = $arr[$i];
$count[$index]--;
}
for ($i = 0; $i < $n; $i++) {
$arr[$i] = $output[$i];
}
}
function radixSort(&$arr) {
$m = getMax($arr);
for ($exp = 1; $m / $exp > 0; $exp *= 10) {
countSort($arr, $exp);
}
}
$arr = [170, 45, 75, 90, 802, 24, 2, 66];
radixSort($arr);
echo "Sorted array: " . implode(" ", $arr);Variations
MSD Radix Sort
Most-significant-digit first approach that works well with variable-length strings.
In-Place Radix Sort
More complex implementation that reduces space complexity.
Hybrid Radix Sort
Combines MSD and LSD approaches for better performance.
Practical Applications
- Sorting large collections of numbers with fixed digit length
- Card sorting machines
- String sorting (dictionary order)
- Implementations in database systems
- Used in suffix array construction algorithms
Note: Radix sort is particularly effective when the range of input values (k) is larger than the number of elements (n), where comparison sorts would perform poorly (O(n log n) vs Radix's O(n) for fixed digit numbers).
Selection Sort Algorithm
Selection Sort is an in-place comparison sorting algorithm that divides the input list into two parts: a sorted sublist which is built up from left to right and a sublist of the remaining unsorted elements. The algorithm repeatedly selects the smallest (or largest) element from the unsorted sublist and moves it to the end of the sorted sublist.
Video: Selection Sort Visualization
How Selection Sort Works?
Detailed Step-by-Step Example:
Sorting the array: [64, 25, 12, 22, 11]
First Pass:
- Entire array is unsorted
- Find minimum: 11 at index 4
- Swap with first element (64)
- Array becomes: [11, 25, 12, 22, 64]
Second Pass:
- First element is sorted
- Find minimum in remaining: 12 at index 2
- Swap with second element (25)
- Array becomes: [11, 12, 25, 22, 64]
Third Pass:
- First two elements are sorted
- Find minimum in remaining: 22 at index 3
- Swap with third element (25)
- Array becomes: [11, 12, 22, 25, 64]
Fourth Pass:
- First three elements are sorted
- Find minimum in remaining: 25 at index 3
- No swap needed
Performance Analysis:
- Time Complexity: Always O(n²) as it performs O(n²) comparisons
- Space Complexity: O(1) (in-place)
- Not stable but can be made stable with extra space
- Makes only O(n) swaps (minimum among all O(n²) algorithms)
Selection Sort Implementations
#include <iostream>
#include <vector>
using namespace std;
void selectionSort(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;
}
}
if (min_idx != i) {
swap(arr[i], arr[min_idx]);
}
}
}
int main() {
vector<int> arr = {64, 25, 12, 22, 11};
selectionSort(arr);
cout << "Sorted array: ";
for (int num : arr) cout << num << " ";
return 0;
}def selection_sort(arr):
n = len(arr)
for i in range(n-1):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)public class SelectionSort {
void sort(int[] arr) {
int n = arr.length;
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;
}
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
public static void main(String args[]) {
int[] arr = {64, 25, 12, 22, 11};
SelectionSort ob = new SelectionSort();
ob.sort(arr);
System.out.print("Sorted array: ");
for (int num : arr) System.out.print(num + " ");
}
}function selectionSort(arr) {
let n = arr.length;
for (let i = 0; i < n-1; i++) {
let min_idx = i;
for (let j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
if (min_idx != i) {
[arr[i], arr[min_idx]] = [arr[min_idx], arr[i]];
}
}
}
let arr = [64, 25, 12, 22, 11];
selectionSort(arr);
console.log("Sorted array:", arr);using System;
class SelectionSort {
static void Sort(int[] arr) {
int n = arr.Length;
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;
}
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
static void Main() {
int[] arr = {64, 25, 12, 22, 11};
Sort(arr);
Console.Write("Sorted array: ");
foreach (int num in arr) {
Console.Write(num + " ");
}
}
}function selectionSort(&$arr) {
$n = count($arr);
for ($i = 0; $i < $n-1; $i++) {
$min_idx = $i;
for ($j = $i+1; $j < $n; $j++) {
if ($arr[$j] < $arr[$min_idx]) {
$min_idx = $j;
}
}
if ($min_idx != $i) {
$temp = $arr[$i];
$arr[$i] = $arr[$min_idx];
$arr[$min_idx] = $temp;
}
}
}
$arr = [64, 25, 12, 22, 11];
selectionSort($arr);
echo "Sorted array: " . implode(" ", $arr);Variations
Double Selection Sort
Finds both the minimum and maximum in each pass, placing them at both ends of the unsorted portion, reducing the number of passes by half.
Bingo Sort
An optimization when there are many duplicate values, where the minimum is found and all equal values are moved in one pass.
When to Use Selection Sort?
- When memory writes are expensive (fewest swaps among O(n²) algorithms)
- When the array is small
- When checking all elements is compulsory
- When memory space is limited
Note: Selection sort is not suitable for large datasets due to its O(n²) time complexity, but it outperforms more complex algorithms for small lists due to its simplicity.
Tree Sort Algorithm
Tree Sort is a sorting algorithm that builds a binary search tree from the elements to be sorted, and then performs an in-order traversal of the tree to get the elements in sorted order. Its efficiency depends on the balance of the tree.
Video: Tree Sort Visualization
How Tree Sort Works?
Step-by-Step Example (Sorting [7, 4, 9, 2, 5]):
Step 1: Build Binary Search Tree
- Insert 7 as root
- Insert 4 (left of 7)
- Insert 9 (right of 7)
- Insert 2 (left of 4)
- Insert 5 (right of 4)
Step 2: In-Order Traversal
- Visit left subtree (2, 4, 5)
- Visit root (7)
- Visit right subtree (9)
- Final sorted order: [2, 4, 5, 7, 9]
Performance Characteristics:
- Average Time Complexity: O(n log n)
- Worst Case: O(n²) (when tree becomes skewed)
- Space Complexity: O(n)
- Stable if implemented carefully
- Adaptive: Efficient for partially sorted data
Tree Sort Implementations
#include <iostream>
#include <vector>
using namespace std;
class Node {
public:
int data;
Node* left;
Node* right;
Node(int value) : data(value), left(nullptr), right(nullptr) {}
};
void insert(Node*& root, int value) {
if (root == nullptr) {
root = new Node(value);
return;
}
if (value < root->data)
insert(root->left, value);
else
insert(root->right, value);
}
void inOrderTraversal(Node* root, vector<int>& result) {
if (root == nullptr) return;
inOrderTraversal(root->left, result);
result.push_back(root->data);
inOrderTraversal(root->right, result);
}
void treeSort(vector<int>& arr) {
Node* root = nullptr;
for (int num : arr)
insert(root, num);
arr.clear();
inOrderTraversal(root, arr);
}
int main() {
vector<int> arr = {12, 11, 13, 5, 6, 7};
treeSort(arr);
cout << "Sorted array: ";
for (int num : arr) cout << num << " ";
return 0;
}class Node:
def __init__(self, value):
self.data = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.data:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def in_order_traversal(root, result):
if root:
in_order_traversal(root.left, result)
result.append(root.data)
in_order_traversal(root.right, result)
def tree_sort(arr):
root = None
for num in arr:
root = insert(root, num)
sorted_arr = []
in_order_traversal(root, sorted_arr)
return sorted_arr
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = tree_sort(arr)
print("Sorted array:", sorted_arr)class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
public class TreeSort {
Node root;
void insert(int key) {
root = insertRec(root, key);
}
Node insertRec(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.data)
root.left = insertRec(root.left, key);
else if (key > root.data)
root.right = insertRec(root.right, key);
return root;
}
void inOrderRec(Node root, java.util.List<Integer> result) {
if (root != null) {
inOrderRec(root.left, result);
result.add(root.data);
inOrderRec(root.right, result);
}
}
void treeSort(int[] arr) {
for (int num : arr)
insert(num);
java.util.List<Integer> sortedList = new java.util.ArrayList<>();
inOrderRec(root, sortedList);
for (int i = 0; i < arr.length; i++)
arr[i] = sortedList.get(i);
}
public static void main(String args[]) {
int[] arr = {12, 11, 13, 5, 6, 7};
TreeSort tree = new TreeSort();
tree.treeSort(arr);
System.out.print("Sorted array: ");
for (int num : arr) System.out.print(num + " ");
}
}class Node {
constructor(value) {
this.data = value;
this.left = null;
this.right = null;
}
}
function insert(root, value) {
if (root === null) {
return new Node(value);
}
if (value < root.data) {
root.left = insert(root.left, value);
} else {
root.right = insert(root.right, value);
}
return root;
}
function inOrderTraversal(root, result) {
if (root !== null) {
inOrderTraversal(root.left, result);
result.push(root.data);
inOrderTraversal(root.right, result);
}
}
function treeSort(arr) {
let root = null;
for (let num of arr) {
root = insert(root, num);
}
let sortedArr = [];
inOrderTraversal(root, sortedArr);
return sortedArr;
}
let arr = [12, 11, 13, 5, 6, 7];
let sortedArr = treeSort(arr);
console.log("Sorted array:", sortedArr);using System;
using System.Collections.Generic;
class Node {
public int Data;
public Node Left, Right;
public Node(int item) {
Data = item;
Left = Right = null;
}
}
class TreeSort {
Node root;
void Insert(int key) {
root = InsertRec(root, key);
}
Node InsertRec(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.Data)
root.Left = InsertRec(root.Left, key);
else if (key > root.Data)
root.Right = InsertRec(root.Right, key);
return root;
}
void InOrderRec(Node root, List<int> result) {
if (root != null) {
InOrderRec(root.Left, result);
result.Add(root.Data);
InOrderRec(root.Right, result);
}
}
public void Sort(int[] arr) {
foreach (int num in arr)
Insert(num);
List<int> sortedList = new List<int>();
InOrderRec(root, sortedList);
for (int i = 0; i < arr.Length; i++)
arr[i] = sortedList[i];
}
static void Main() {
int[] arr = {12, 11, 13, 5, 6, 7};
TreeSort tree = new TreeSort();
tree.Sort(arr);
Console.Write("Sorted array: ");
foreach (int num in arr) Console.Write(num + " ");
}
}class Node {
public $data;
public $left;
public $right;
public function __construct($value) {
$this->data = $value;
$this->left = null;
$this->right = null;
}
}
function insert($root, $value) {
if ($root === null) {
return new Node($value);
}
if ($value < $root->data) {
$root->left = insert($root->left, $value);
} else {
$root->right = insert($root->right, $value);
}
return $root;
}
function inOrderTraversal($root, &$result) {
if ($root !== null) {
inOrderTraversal($root->left, $result);
$result[] = $root->data;
inOrderTraversal($root->right, $result);
}
}
function treeSort($arr) {
$root = null;
foreach ($arr as $num) {
$root = insert($root, $num);
}
$sortedArr = [];
inOrderTraversal($root, $sortedArr);
return $sortedArr;
}
$arr = [12, 11, 13, 5, 6, 7];
$sortedArr = treeSort($arr);
echo "Sorted array: " . implode(" ", $sortedArr);Variations
Balanced Tree Sort
Using AVL or Red-Black trees to guarantee O(n log n) performance.
Threaded Binary Tree Sort
Improves traversal efficiency by adding threads to nodes.
Practical Applications
- When maintaining a sorted data structure is needed
- Database indexing
- Auto-completion features
- Range queries in databases
- As part of more complex algorithms
Note: While simple to implement, basic tree sort has O(n²) worst-case performance with unbalanced trees. For production use, balanced tree variants should be used to guarantee O(n log n) performance in all cases.