Sorting Techniques

Popular sorting techniques include:

1. Selection sort

2. Bubble sort

3. Insertion sort

4. Merge sort

5. Quick sort

Selection Sort

void selectionSort(vector<int>& arr){
    int n = arr.size();
    for(int i = 0; i < n; i++){
        int minimum = i;
        for(int j = i; j < n; j++) if(arr[j] < arr[minimum]) minimum = j;
        swap(arr[i], arr[minimum]);
    }
}

Bubble Sort

void bubbleSort(vector<int>& arr){
    for(int boundary = arr.size(); boundary > 0; boundary--){
        bool swapped = false;
        for(int i = 0; i < boundary - 1; i++){
            if(arr[i] > arr[i+1]){
                swap(arr[i], arr[i+1]);
                swapped = true;
            }
        }
        if(!swapped) break;
    }
}

Recursive Bubble Sort

// recursive bubble sort
void bubbleSort(vector<int>& arr, int boundary){
    if(boundary == 1) return;
    bool swapped = false;
    for(int i = 0; i < boundary - 1; i++){
        if(arr[i] > arr[i+1]){
            swap(arr[i], arr[i+1]);
            swapped = true;
        }
    }
    if(swapped) bubbleSort(arr, boundary - 1);
}

Insertion Sort

void insertionSort(vector<int>& arr){
    int n = arr.size();
    for(int boundary = 1; boundary < n; boundary++){
        int key = arr[boundary];
        int i = boundary - 1;
        while(i >= 0 && arr[i] > key){
            arr[i+1] = arr[i];
            i--;
        }
        arr[i+1] = key;
    }
}

Recursive Insertion Sort

// recursive insertion sort
void insertionSort(vector<int>& arr, int boundary){
    if(boundary == arr.size()) return;

    int key = arr[boundary];
    int i = boundary - 1;
    while(i >= 0 && arr[i] > key){
        arr[i+1] = arr[i];
        i--;
    }
    arr[i+1] = key;
    insertionSort(arr, boundary + 1);
}

Merge Sort

void merge(vector<int>& arr, int l1, int r1, int l2, int r2){
    vector<int> temp;
    int start = l1;

    while(l1 <= r1 && l2 <= r2){
        if(arr[l1] <= arr[l2]) temp.push_back(arr[l1++]);
        else temp.push_back(arr[l2++]);
    }

    while(l1 <= r1) temp.push_back(arr[l1++]);
    while(l2 <= r2) temp.push_back(arr[l2++]);

    for(int i=0; i<temp.size(); i++) arr[start + i] = temp[i];
}

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

Quick Sort

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

    int pivot = arr[start], smallerElements = 0;
    for(int i = start; i <= end; i++){
        if(arr[i] < pivot) smallerElements++;
    }
    int pivotIndex = start + smallerElements;
    swap(arr[start], arr[pivotIndex]);

    int i = start, j = end;
    while(i < pivotIndex && j > pivotIndex){
        while(arr[i] <= pivot) i++;
        while(arr[j] > pivot) j--;
        if(i < pivotIndex && j > pivotIndex) swap(arr[i], arr[j]);
    }

    quickSort(arr, start, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, end);
}