Sorting Algorithm Categories

Insertion-based: Straight insertion sort, Shell sort
Exchange-based: Bubble sort, Quick sort
Selection-based: Selection sort, Heap sort
Other: Merge sort, Counting-based sorts

Sorting Characteristics

1. In-place sorting capability
2. Internal vs external sorting (external uses auxiliary storage)
3. Stability (maintains relative order of equal elements)
4. Time complexity analysis

Test Environment

#include <iostream>
#include <vector>
using namespace std;

vector<int> data;
int size;

int main()
{
    data = {23523, 51345, 1345314, 9876, 8765, 2345, 4, 3, 8, 7, 5, 4, 2349, 1, 54, 29, 53, 98, 275946382, 305};
    size = data.size();
    
    cout << "-------Before Sorting------\n";
    for (int i = 0; i < size; i++) {
        cout << data[i] << ' ';
    }
    cout << "\n";

    performSorting();

    cout << "-------After Sorting-------\n";
    for (int i = 0; i < size; i++) {
        cout << data[i] << ' ';
    }
    cout << endl;
}

Insertion-Based Sorting

Straight Insertion Sort

Properties: In-place, stable, O(n²)

Maintains a sorted section and inserts each subsequent element into its correct position using linear search.

void insertionSort()
{
    int currentValue;
    int insertPosition;
    
    for (int i = 1; i < size; i++) {
        currentValue = data[i];
        insertPosition = i;
        
        for (int j = 0; j < i; j++) {
            if (currentValue < data[j]) {
                insertPosition = j;
                break;
            }
        }

        for (int k = i; k > insertPosition; k--) {
            data[k] = data[k - 1];
        }
        data[insertPosition] = currentValue;
    }
}

Binary Insertion Sort

Uses binary search to locate insertion points, though shifting still requires O(n) time.

Properties: In-place, stable, O(n²)

void binaryInsertionSort()
{
    int element;
    int position;
    int low, high, middle;
    
    for (int i = 1; i < size; i++) {
        element = data[i];
        position = i;

        low = 0;
        high = i - 1;
        
        while (low < high) {
            middle = (high - low) / 2 + low;
            if (data[middle] > element) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }
        
        position = low;
        if (data[position] <= element) {
            position++;
        }

        for (int k = i; k > position; k--) {
            data[k] = data[k - 1];
        }
        data[position] = element;
    }
}

Two-Way Insertion Sort

Employs a circular buffer to reduce shifting operations by approximately half.

Properties: Not in-place, stable, O(n²)

void twoWayInsertionSort()
{
    vector<int> tempBuffer(size);
    tempBuffer[0] = data[0];
    int head = 0;
    int tail = 0;
    
    for (int i = 1; i < size; i++) {
        if (tempBuffer[head] > data[i]) {
            head = (head - 1 + size) % size;
            tempBuffer[head] = data[i];
        }
        else if (tempBuffer[tail] < data[i]) {
            tail = (tail + 1) % size;
            tempBuffer[tail] = data[i];
        }
        else {
            int index = tail;
            while (tempBuffer[index] > data[i]) {
                tempBuffer[(index + 1) % size] = tempBuffer[index];
                index = (index - 1 + size) % size;
            }
            tempBuffer[(index + 1) % size] = data[i];
            tail = (tail + 1) % size;
        }
    }

    for (int i = 0; i < size; i++) {
        data[i] = tempBuffer[(head + i) % size];
    }
}

Shell Sort

Divides array into subgroupss with decreasing gaps, sorting each subgroup.

Properties: In-place, unstable, Worst case O(n²)

void shellSort()
{
    int gap = size / 2;
    int currentElement;
    
    while (gap > 0) {
        for (int i = gap; i < size; i++) {
            currentElement = data[i];
            int pos;
            
            for (pos = i - gap; pos >= 0; pos -= gap) {
                if (data[pos] > currentElement)
                    data[pos + gap] = data[pos];
                else
                    break;
            }
            data[pos + gap] = currentElement;
        }
        gap /= 2;
    }
}

Exchange-Based Sorting

Bubble Sort

Repeatedly compares adjacent elements and swaps them if needed.

Properties: In-place, stable, O(n²)

void bubbleSort()
{
    int sortedBoundary = size;
    int lastSwapPos = size;
    
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < lastSwapPos - 1; j++) {
            if (data[j] > data[j + 1]) {
                data[j] += data[j + 1];
                data[j + 1] = data[j] - data[j + 1];
                data[j] -= data[j + 1];
                sortedBoundary = j + 1;
            }
        }
        lastSwapPos = sortedBoundary;
    }
}

Quick Sort

Selects a pivot element and partitions the array around it recursively.

Properties: In-place, unstable, Average O(n log n)

void quickSort(vector<int> &arr, int left, int right)
{
    if (left >= right)
        return;

    int pivot = arr[left];
    int l = left;
    int r = right;
    
    while (l < r) {
        while (l < r && pivot <= arr[r])
            r--;
        if (l < r)
            arr[l++] = arr[r];

        while (l < r && arr[l] <= pivot)
            l++;
        if (l < r)
            arr[r--] = arr[l];
    }

    arr[l] = pivot;
    
    if (l != left)
        quickSort(arr, left, l - 1);
    if (r != right)
        quickSort(arr, l + 1, right);
}

Selection-Based Sorting

Selection Sort

Finds the minimum element in unsorted portion and places it at the beginning.

Properties: In-place, unstable, O(n²)

void selectionSort()
{
    int minIndex;
    int temp;
    
    for (int i = 0; i < size; i++) {
        minIndex = i;
        for (int j = i + 1; j < size; j++) {
            if (data[minIndex] > data[j])
                minIndex = j;
        }
        temp = data[i];
        data[i] = data[minIndex];
        data[minIndex] = temp;
    }
}

Heap Sort

Uses heap properties to efficiently find extremum values.

Properties: In-place, unstable, O(n log n)

void heapAdjust(vector<int> &heap, int root, int end)
{
    if (root >= end)
        return;

    int maxChild = 2 * root + 1;
    int parentValue = heap[root];
    
    while (maxChild <= end) {
        if (maxChild < end && heap[maxChild + 1] > heap[maxChild])
            maxChild++;
        
        if (parentValue < heap[maxChild]) {
            heap[(maxChild - 1) / 2] = heap[maxChild];
            maxChild = 2 * maxChild + 1;
        } else {
            break;
        }
    }
    heap[(maxChild - 1) / 2] = parentValue;
}

void heapSort()
{
    for (int i = (size - 1) / 2; i >= 0; i--) {
        heapAdjust(data, i, size - 1);
    }

    int temp;
    for (int i = 0; i < size;) {
        temp = data[size - 1 - i];
        data[size - 1 - i] = data[0];
        data[0] = temp;

        i++;
        heapAdjust(data, 0, size - 1 - i);
    }
}

Other Sorting Methods

Merge Sort

Divides array into halves recursively, then merges sorted subarrays.

Properteis: Not in-place, stable, O(n log n)

void mergeSort(vector<int> &arr, int left, int right)
{
    if (left >= right)
        return;
        
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    int p1 = left;
    int p2 = mid + 1;
    vector<int> temp(right - left + 1);
    int i = 0;
    
    while (p1 <= mid && p2 <= right) {
        if (arr[p1] > arr[p2])
            temp[i++] = arr[p2++];
        else
            temp[i++] = arr[p1++];
    }
    
    while (p1 <= mid)
        temp[i++] = arr[p1++];
    while (p2 <= right)
        temp[i++] = arr[p2++];

    i = 0;
    for (int j = left; j <= right; j++, i++) {
        arr[j] = temp[i];
    }
}

Counting-Based Sorting

Counting Sort: Records frequency of each value and outputs based on counts.

Bucket Sort: Distributes elements into buckets and sorts within buckets.

Radix Sort: Processes digits from least significant to most significant using stable counting sort.

Algorithm Summary