Program Structure

The Quick Sort algorithm is a highly efficient sorting algorithm and is based on the divide-and-conquer principle. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

The main components of the Quick Sort implementation are:

• Partition Function: This function takes the last element as the pivot, places it in its correct position in the sorted array, and places all smaller (smaller than the pivot) to the left and all larger elements to the right of the pivot.
• Quick Sort Function: This function recursively sorts the sub-arrays formed by the partitioning.
• Main Function: This is the entry point of the program, which initializes the array and calls the Quick Sort function.

Code Implementation

#include 
using namespace std;

// Function to partition the array
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // pivot
    int i = (low - 1); // Index of smaller element

    for (int j = low; j < high; j++) {
        // If current element is smaller than or equal to pivot
        if (arr[j] <= pivot) {
            i++; // increment index of smaller element
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

// Function to implement Quick Sort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi is partitioning index, arr[pi] is now at right place
        int pi = partition(arr, low, high);

        // Recursively sort elements before partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Main function
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Unsorted array: ";
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    printArray(arr, n);
    return 0;
}
    

Documentation

• partition(int arr[], int low, int high): Partitions the array and returns the index of the pivot.
• quickSort(int arr[], int low, int high): Recursively sorts the array using the Quick Sort algorithm.
• printArray(int arr[], int size): Utility function to print the elements of the array.
• main(): The main entry point of the program, initializes the array, and calls the sorting functions.

How to Compile and Run

To compile and run this program:

1. Open your terminal or command prompt.
2. Navigate to the directory containing your source file.
3. Compile the program using: g++ quicksort.cpp -o quicksort
4. Run the program using: ./quicksort