Sorting Basics

Sorting Techniques in C++

This GitHub wiki page provides detailed explanations and examples of various sorting algorithms implemented in C++. The following sorting techniques are covered:

1. Bubble Sort
2. Heap Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
6. Selection Sort

Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Code Example

#include<bits/stdc++.h>
using namespace std;

void printarr(int* arr, int n) {
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void bubbleSort(int* arr, int n) {
    for(int i = 1; i < n; i++) 
        for(int j = 0; j < n - i; j++) 
            if(arr[j] > arr[j + 1]) 
                swap(arr[j], arr[j + 1]);
    printarr(arr, n);
}

int main() {
    int arr[] = {4, 3, 2, 1};
    bubbleSort(arr, 4);
    return 0;
}

Explanation

• printarr: A utility function to print the array.
• bubbleSort: Implements the Bubble Sort algorithm. It uses nested loops to compare and swap elements.
• main: Initializes an array and calls the bubbleSort function.

Heap Sort

Heap Sort is a comparison-based sorting technique based on a Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements.

Code Example

#include<bits/stdc++.h>
using namespace std;

// Child-parent relation in heap
void insert(vector<int>& arr, int val) {
    if(arr.size() == 0) arr.push_back(val);
    else {
        arr.push_back(val);
        int s = arr.size() - 1;
        while (s > 0 && arr[s] > arr[(s - 1) / 2]) {
            swap(arr[s], arr[(s - 1) / 2]);
            s = (s - 1) / 2;
        }
    }
}

// Heapify using insert method
vector<int> heapify(vector<int>& arr) {
    vector<int> ans;
    for(int i : arr) insert(ans, i);
    return ans;
}

void maxheap(vector<int>& arr, int i, int n) {
    int left = i * 2 + 1, right = i * 2 + 2, max = i;
    if(left < n && arr[max] < arr[left]) max = left;
    if(right < n && arr[max] < arr[right]) max = right;
    if(max != i) {
        swap(arr[max], arr[i]);
        maxheap(arr, max, n);
    }
}

void minheap(vector<int>& arr, int i, int n) {
    int left = i * 2 + 1, right = i * 2 + 2, min = i;
    if(left < n && arr[min] > arr[left]) min = left;
    if(right < n && arr[min] > arr[right]) min = right;
    if(min != i) {
        swap(arr[min], arr[i]);
        maxheap(arr, min, n);
    }
}

void buildmaxheap(vector<int>& arr, int n) {
    for(int i = (n / 2) - 1; i >= 0; i--) {
        maxheap(arr, i, n);
    }
}

void heapsort(vector<int>& arr) {
    buildmaxheap(arr, arr.size());
    for(int i = arr.size() - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        minheap(arr, 0, i);
    }
}

int main() {
    vector<int> arr = {1, 4, 2, 3, 6};
    vector<int> ans = heapify(arr);
    for(int i : ans) cout << i << " ";
    heapsort(arr);
    for(int i : arr) cout << i << " ";
    return 0;
}

Explanation

• insert: Inserts a new value into the heap.
• heapify: Converts an array into a heap.
• maxheap: Maintains the max-heap property.
• minheap: Maintains the min-heap property.
• buildmaxheap: Builds a max-heap from an array.
• heapsort: Implements the Heap Sort algorithm.

Insertion Sort

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 such as quicksort, heapsort, or merge sort.

Code Example

#include<bits/stdc++.h>
using namespace std;

void printarr(int* arr, int n) {
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void insertionsort(int arr[], int n) {
    int key;
    for(int i = 1; i < n; i++) {
        key = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    printarr(arr, n);
}

int main() {
    int arr[] = {4, 3, 2, 1};
    insertionsort(arr, 4);
    return 0;
}

Explanation

• printarr: A utility function to print the array.
• insertionsort: Implements the Insertion Sort algorithm. It uses a nested loop to insert elements in the correct position.
• main: Initializes an array and calls the insertionsort function.

Merge Sort

Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

Code Example

#include<iostream>
using namespace std;

void merge(int arr[], int l, int m, int r) {
    int left = l, right = m + 1;
    while(left <= m && right <= r) {
        if(arr[left] < arr[right]) {
            left++;
        } else {
            swap(arr[left], arr[right]);
            left++;
        }
    }
    for(int i = l; i <= r; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

void mergesort(int arr[], int l, int r) {
    if(l < r) {
        int mid = l + (r - l) / 2;
        mergesort(arr, l, mid);
        mergesort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }
}

void printarr(int arr[], int n) {
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
}

int main() {
    int arr[] = {4, 3, 2, 1, 6};
    mergesort(arr, 0, 4);
    printarr(arr, 5);
}

Explanation

• merge: Merges two sorted subarrays into a single sorted subarray.
• mergesort: Implements the Merge Sort algorithm using recursion.
• printarr: A utility function to print the array.
• main: Initializes an array and calls the mergesort function.

Quick Sort

Quick Sort is a highly efficient sorting algorithm and is based on partitioning of the array of data into smaller arrays. A large array is partitioned into two arrays, one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.

Code Example

#include<bits/stdc++.h>
using namespace std;
time_t t;

void printarr(int arr[], int l, int h) {
    for(int i = l; i < h; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

int partion(int arr[], int l, int h) {
    int i = l, j = h, piv = arr[l];
    while(i < j) {
        while(arr[++i] < piv);
        while(arr[--j] > piv);
        if(i < j) {
            swap(arr[i], arr[j]);
        }
        printarr(arr, l, h);
    }
    swap(arr[l], arr[j]);
    return j;
}

int rpartion(int arr[], int l, int h) {
    srand((unsigned)time(&t));
    int mid = (rand() % (h - l)) + l;
    int i = l, j = h, piv = arr[mid];
    while(i < j) {
        while(arr[++i] < piv);
        while(arr[--j] > piv);
        if(i < j) {
            swap(arr[i], arr[j]);
        }
        printarr(arr, l, h);
    }
    swap(arr[mid], arr[j]);
    return j;
}

void quicksort(int arr

[], int l, int h) {
    if(l < h) {
        int mid = rpartion(arr, l, h);
        quicksort(arr, l, mid);
        quicksort(arr, mid + 1, h);
    }
}

int main() {
    int arr[] = {16, 18, 16, 18, 16, 18, 16, 18};
    quicksort(arr, 0, 8);
    printarr(arr, 0, 8);
}

Explanation

• printarr: A utility function to print the array.
• partion: Partitions the array into two parts.
• rpartion: Randomized partition function to improve performance on certain types of data.
• quicksort: Implements the Quick Sort algorithm.
• main: Initializes an array and calls the quicksort function.

Selection Sort

Selection Sort is a simple comparison-based sorting algorithm. It divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Code Example

#include<iostream>
using namespace std;

void sort(int arr[], int n) {
    for(int i = 0; i < n - 1; i++) {
        for(int j = i + 1; j < n; j++) {
            if(arr[i] > arr[j]) swap(arr[i], arr[j]);
        }
    }
}

void printarr(int arr[], int n) {
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
}

int main() {
    int arr[] = {4, 3, 2, 1, 6};
    sort(arr, 5);
    printarr(arr, 5);
    return 0;
}

Explanation

• sort: Implements the Selection Sort algorithm.
• printarr: A utility function to print the array.
• main: Initializes an array and calls the sort function.

Each of these algorithms has its strengths and weaknesses and is suitable for different types of datasets and requirements. Experiment with each to understand their performance and behavior better.