Implementing Various Sorting Algorithms

In the field of competitive programming, sorting algorithms play a crucial role in optimizing code execution and solving various problems efficiently. In this article, we will discuss the implementation of popular sorting algorithms such as selection sort, insertion sort, merge sort, and quicksort using the C++ programming language.

Selection Sort

Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the array and placing it at the beginning. The algorithm divides the array into two parts: the sorted part at the left end and the unsorted part at the right end.

Here is the C++ implementation for selection sort:

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

Insertion Sort

Insertion sort is a comparison-based sorting algorithm that builds the final sorted array one item at a time. It works by repeatedly shifting the elements that are greater than the current value to be sorted to one position ahead.

Here is the C++ implementation for insertion sort:

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

Merge Sort

Merge sort is a divide and conquer algorithm that divides the array into two halves, sorts them independently, and then merges the sorted halves. It follows the principle of recursion.

Here is the C++ implementation for merge sort:

void merge(int arr[], int left, int middle, int right) {
    int n1 = middle - left + 1;
    int n2 = right - middle;
    
    int L[n1], R[n2];
    
    for (int i = 0; i < n1; i++)
        L[i] = arr[left+i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[middle+1+j];
    
    int i = 0, j = 0, k = left;
    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(int arr[], int left, int right) {
    if (left < right) {
        int middle = left + (right - left) / 2;
        mergeSort(arr, left, middle);
        mergeSort(arr, middle+1, right);
        merge(arr, left, middle, right);
    }
}

Quicksort

Quicksort is another efficient divide and conquer sorting algorithm. It works by selecting a pivot element, partitioning the array around the pivot, and recursively sorting the sub-arrays.

Here is the C++ implementation for quicksort:

int partition(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(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);
    }
}

These are just a few examples of sorting algorithms commonly used in competitive programming. Each algorithm has its own strengths and weaknesses, making them suitable for specific scenarios. Implementing these algorithms in C++ will give you a solid foundation for solving diverse problems efficiently.