Installation and Configuration
Programming Methodology

Sorting an Array Using QuickSort Algorithm in C++

This exercise demonstrates how to implement the QuickSort algorithm in C++ to sort an array of integers. QuickSort is a highly efficient sorting algorithm that follows the divide-and-conquer strategy. It selects a pivot element and partitions the array such that all elements less than the pivot are on the left, and those greater are on the right. This process is then recursively applied to the sub-arrays. QuickSort is known for its average-case performance of O(n log n), making it suitable for large datasets. By completing this activity, you will gain a deeper understanding of recursion, partitioning logic, and efficient sorting techniques.

Group

Search and Sort Algorithms in C++

Objective

Create a function called quickSort that takes an array, a starting index, and an ending index as parameters. Implement the partition logic inside a helper function, and recursively call quickSort on the sub-arrays. In the main function, define an array of integers and apply the quickSort function to sort it. Then, display the sorted array.

Implement the QuickSort algorithm.

Example C++ Exercise

 Copy C++ Code 
#include <iostream>   // Include the input-output stream library
using namespace std;

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

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

    for (int j = low; j < high; j++) {
        // If current element is less than or equal to pivot
        if (arr[j] <= pivot) {
            i++;                 // Move the smaller element index forward
            swap(arr[i], arr[j]);  // Swap current element with the element at i
        }
    }

    swap(arr[i + 1], arr[high]);  // Place pivot in the correct position
    return i + 1;  // Return pivot index
}

// QuickSort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // Get the pivot index

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

int main() {
    // Initialize an unsorted array
    int arr[] = {10, 7, 8, 9, 1, 5};
    int size = sizeof(arr) / sizeof(arr[0]);  // Calculate array size

    // Call quickSort on the array
    quickSort(arr, 0, size - 1);

    // Print the sorted array
    cout << "Sorted array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;  // End of program
}

 Output

Sorted array: 1 5 7 8 9 10

Share this C++ Exercise


More C++ Programming Exercises of Search and Sort Algorithms in C++

Explore our set of C++ Programming Exercises! Specifically designed for beginners, these exercises will help you develop a solid understanding of the basics of C++. From variables and data types to control structures and simple functions, each exercise is crafted to challenge you incrementally as you build confidence in coding in C++.