Quick Sort in C++

Quick Sort is a highly efficient sorting algorithm that provides a fast and reliable way to sort elements in an array. Developed by Tony Hoare in 1959, Quick Sort is widely used due to its simplicity and remarkable performance. In this article, we will explore the Quick Sort algorithm in detail, step by step, along with a C++ implementation.

Quick Sort Algorithm

Quick Sort follows the divide-and-conquer paradigm, which means it divides the problem into smaller sub-problems, solves them independently, and combines the solutions to obtain the final sorted array. The basic idea behind Quick Sort is to select a pivot element, partition the array into two sub-arrays based on the pivot, and recursively sort the sub-arrays until the entire array is sorted.

Quick Sort in C++ Implementation

To implement Quick Sort in C++, we need to define a function that takes an array, the starting index, and the ending index as parameters. Let’s call this function quickSort.

#include <iostream>

//  swap two values
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

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);
    }
}


int main() {
    int arr[] = { 64, 25,4,56,1,4,1,34,56,9,3,412,78,9, 12, 22, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    
    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    
    return 0;
}

Explanation of the Quick Sort in C++ Code

1. The swap function is a utility function used to swap two elements in the array.
2. The partition function selects the pivot element (in this case, the last element) and rearranges the array such that all elements smaller than the pivot are placed before it, and all greater elements are placed after it. It returns the index of the pivot element.
3. The quickSort function recursively calls itself to sort the sub-arrays. It uses the partition function to divide the array into sub-arrays and sort them individually.
4. In the main function, we initialize an array and calculate its size. We then call quickSort with the array, starting index 0, and ending index n – 1.
5. Finally, we print the sorted array using a loop.

Quick Sort is a powerful and efficient sorting algorithm that offers an excellent solution for sorting arrays in C++. By following the divide-and-conquer strategy, Quick Sort breaks down the problem into smaller sub-problems and sorts them recursively.

• Quick Sort in Java