Bucket Sort

Time Complexity: O(N+M)

Bucket sort operates by distributing elements into a number of buckets, then sorting each bucket individually. Imagine you have 100 buckets, each labeled with a unique number from 1 to 100. When given n balls with numbers between 1 and 100, you place each ball into the bucket matching its number. The balls are now sorted by their numbers. In implementation, we use arrays to track which numbers have appeared and their frequencies.

Advantage: Simple implementation for data within a known range

Disadvantage: Space complexity can be high when n is large or when data has a wide range

#include <iostream>
using namespace std;

int main() {
    int elementCount;
    const int MAX_SIZE = 100;
    int presence[MAX_SIZE] = {0}; // Tracks unique elements
    int frequency[MAX_SIZE] = {0}; // Tracks element frequencies
    currentValue;
    
    cin >> elementCount;
    
    // Record unique elements and frequencies
    for (int i = 0; i < elementCount; i++) {
        cin >> currentValue;
        presence[currentValue] = 1;
        frequency[currentValue]++;
    }
    
    // Print unique elements in order
    for (int i = 1; i < MAX_SIZE; i++) {
        if (presence[i] == 1) {
            cout << i << " ";
        }
    }
    cout << endl;
    
    // Print all elements with duplicates
    for (int i = 1; i < MAX_SIZE; i++) {
        for (int j = 0; j < frequency[i]; j++) {
            cout << i << " ";
        }
    }
    
    return 0;
}
</iostream>

Bubble Sort

Time Complexity: O(n²)

Bubble sort works by repeatedly swapping adjacent elements if they are in the wrong order. This process conitnues until the entire list is sorted. With each pass through the list, the largest unsorted element "bubbles up" to its correct position at the end.

#include <iostream>
using namespace std;

int main() {
    int size;
    int data[100];
    
    cin >> size;
    for (int i = 0; i < size; i++) {
        cin >> data[i];
    }
    
    // Bubble sort implementation
    for (int pass = 0; pass < size; pass++) {
        for (int i = 0; i < size - 1; i++) {
            if (data[i] > data[i + 1]) {
                // Swap elements
                int temp = data[i + 1];
                data[i + 1] = data[i];
                data[i] = temp;
            }
        }
    }
    
    // Display sorted array
    for (int i = 0; i < size; i++) {
        cout << data[i] << " ";
    }
    
    return 0;
}
</iostream>

Quick Sort

Time Complexity: O(n log n)

Quick sort employs a divide-and-conquer strategy. It selects a 'pivot' element and partitions the array into two sub-arrays: elements less than the pivot and elements greater than the pivot. The process is then recursively applied to each sub-array.

The algorithm can be visualized as soldiers lining up by height: a soldier at the front directs shorter soldiers to stand in front and taller soldiers to stand behind. This creates two groups wich are then sorted using the same method.

#include <iostream>
using namespace std;

int dataArray[101];
int arraySize;

void quickSort(int leftIndex, int rightIndex) {
    if (leftIndex > rightIndex) return;
    
    int pivot = dataArray[leftIndex];
    int i = leftIndex;
    int j = rightIndex;
    int temp;
    
    while (i != j) {
        // Find element smaller than pivot from right
        while (dataArray[j] >= pivot && i < j) j--;
        
        // Find element larger than pivot from left
        while (dataArray[i] <= pivot && i < j) i++;
        
        // Swap elements if valid
        if (i < j) {
            temp = dataArray[i];
            dataArray[i] = dataArray[j];
            dataArray[j] = temp;
        }
    }
    
    // Place pivot in correct position
    dataArray[leftIndex] = dataArray[i];
    dataArray[i] = pivot;
    
    // Recursively sort left and right partitions
    quickSort(leftIndex, i - 1);
    quickSort(i + 1, rightIndex);
}

int main() {
    cin >> arraySize;
    
    for (int i = 0; i < arraySize; i++) {
        cin >> dataArray[i];
    }
    
    quickSort(0, arraySize - 1);
    
    for (int i = 0; i < arraySize; i++) {
        cout << dataArray[i] << " ";
    }
    
    return 0;
}
</iostream>