Implementation of Quick Sort Algorithm in C++

Quick Sort is a popular and efficient algorithm used for sorting arrays or lists. It follows a “divide and conquer” strategy, breaking down the sorting problem into smaller, more manageable pieces. In this article, we’ll guide you through implementing the Quick Sort algorithm using the C++ programming language. We’ll cover the basic implementation, sorting in reverse order, and how to sort custom objects, all explained in a simple and easy-to-understand way.

Prerequisites:

Core Idea Recap

Before we dive into the C++ code, let’s quickly recap the main steps of Quick Sort:

  1. Choose a Pivot: Select an element from the array (the pivot). A common choice is the last element.
  2. Partition: Rearrange the array such that all elements smaller than the pivot come before it, and all elements larger come after it. The pivot element ends up in its final sorted position.
  3. Recurse: Apply the Quick Sort algorithm recursively to the two sub-arrays: the one before the pivot and the one after the pivot.
  4. Base Case: The recursion stops when a sub-array has zero or one element (as it’s already considered sorted).

Basic Quick Sort Implementation (Recursive)

Let’s implement Quick Sort in C++ using recursion. We’ll need two functions: one for the main recursive logic (quickSort) and one for the partitioning step (partition). We’ll use std::vector for our array and choose the last element as the pivot in our partition function for simplicity.

The partition Function

This function takes the vector (or sub-vector), the low index (start of the sub-vector), and the high index (end of the sub-vector) as input. It rearranges the elements around the pivot and returns the final index of the pivot.

#include <vector>
#include <utility> // Required for std::swap

// Function to partition the array and return the pivot index
int partition(std::vector<int>& arr, int low, int high) {
  // Choose the last element as the pivot
  int pivot = arr[high];
  
  // i stores the index of the last element that was smaller than the pivot
  // Initialize i to be one position before the start of the sub-array
  int i = low - 1; 

  // Iterate through the sub-array from low up to (but not including) high
  for (int j = low; j < high; ++j) {
    // If the current element is less than or equal to the pivot
    if (arr[j] <= pivot) {
      // Increment i (move the boundary for smaller elements)
      i++;
      // Swap the element at index i with the current element at index j
      // This moves the smaller element arr[j] to the "smaller" side
      std::swap(arr[i], arr[j]);
    }
  }

  // After the loop, the correct position for the pivot is i + 1
  // Swap the pivot (which is at arr[high]) with the element at arr[i + 1]
  std::swap(arr[i + 1], arr[high]);
  
  // Return the index where the pivot is now located
  return i + 1;
}

Explanation:

  • #include <vector>: Includes the necessary header for using std::vector.
  • #include <utility>: Includes the header for std::swap.
  • pivot = arr[high]: Selects the last element as the pivot.
  • i = low - 1: i tracks the boundary. Everything at or before index i is less than or equal to the pivot.
  • for (int j = low; j < high; ++j): This loop iterates through the elements we need to compare against the pivot.
  • if (arr[j] <= pivot): If an element arr[j] is smaller than or equal to the pivot, we increment i and swap arr[i] with arr[j] to move the smaller element towards the beginning.
  • std::swap(arr[i + 1], arr[high]): Finally, the pivot (originally at arr[high]) is swapped into its correct sorted position, which is i + 1.
  • return i + 1: The function returns the index where the pivot was placed.

The quickSort Function

This function implements the main recursive logic. It calls partition and then recursively calls itself on the two resulting sub-arrays.

// The main Quick Sort function
void quickSort(std::vector<int>& arr, int low, int high) {
  // Base case: If low is less than high, there are at least two elements
  // If low >= high, the sub-array has 0 or 1 element, which is already sorted
  if (low < high) {
    // Partition the array and get the pivot's final index (pi)
    int pi = partition(arr, low, high);

    // Recursively call quickSort on the sub-array before the pivot
    // Sort elements from low up to pi - 1
    quickSort(arr, low, pi - 1);

    // Recursively call quickSort on the sub-array after the pivot
    // Sort elements from pi + 1 up to high
    quickSort(arr, pi + 1, high);
  }
}

Explanation:

  • if (low < high): This is the crucial check. If low is not less than high, it means the segment of the array we’re looking at has 0 or 1 element, so it doesn’t need sorting (this is the base case for the recursion).
  • pi = partition(arr, low, high): Calls the partition function to rearrange the segment from low to high and gets the pivot’s final position.
  • quickSort(arr, low, pi - 1): Recursively sorts the part of the array before the pivot.
  • quickSort(arr, pi + 1, high): Recursively sorts the part of the array after the pivot.

Putting It Together

Here’s a complete C++ program demonstrating the basic Quick Sort:

#include <iostream>
#include <vector>
#include <utility> // For std::swap

// Partition function (as defined above)
int partition(std::vector<int>& arr, int low, int high) {
  int pivot = arr[high];
  int i = low - 1; 
  for (int j = low; j < high; ++j) {
    if (arr[j] <= pivot) {
      i++;
      std::swap(arr[i], arr[j]);
    }
  }
  std::swap(arr[i + 1], arr[high]);
  return i + 1;
}

// Quick Sort function (as defined above)
void quickSort(std::vector<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);
  }
}

// Utility function to print the vector
void printVector(const std::vector<int>& arr) {
  for (int val : arr) {
    std::cout << val << " ";
  }
  std::cout << std::endl;
}

int main() {
  // Example vector to sort
  std::vector<int> arr = {10, 7, 8, 9, 1, 5};
  int n = arr.size();

  std::cout << "Original vector: ";
  printVector(arr);

  // Call quickSort on the entire vector
  // low = 0 (start index), high = n-1 (end index)
  quickSort(arr, 0, n - 1);

  std::cout << "Sorted vector: ";
  printVector(arr);

  return 0;
}

Output:

Original vector: 10 7 8 9 1 5 
Sorted vector: 1 5 7 8 9 10

Sorting in Descending Order

To sort the vector in descending order (largest to smallest), you only need to change the comparison logic inside the partition function. Instead of arr[j] <= pivot, use arr[j] >= pivot.

// Partition function modified for descending order
int partition_desc(std::vector<int>& arr, int low, int high) {
  int pivot = arr[high];
  int i = low - 1;
  for (int j = low; j < high; ++j) {
    // Change comparison to >= for descending sort
    if (arr[j] >= pivot) { 
      i++;
      std::swap(arr[i], arr[j]);
    }
  }
  std::swap(arr[i + 1], arr[high]);
  return i + 1;
}

// Quick Sort function modified to use the descending partition
void quickSort_desc(std::vector<int>& arr, int low, int high) {
  if (low < high) {
    // Use the descending partition function
    int pi = partition_desc(arr, low, high); 
    quickSort_desc(arr, low, pi - 1);
    quickSort_desc(arr, pi + 1, high);
  }
}

// --- In main() ---
// std::vector<int> arr_desc = {10, 7, 8, 9, 1, 5};
// std::cout << "\nOriginal vector for descending sort: ";
// printVector(arr_desc);
// quickSort_desc(arr_desc, 0, arr_desc.size() - 1);
// std::cout << "Sorted vector (descending): ";
// printVector(arr_desc);

Output (for descending sort):

Original vector for descending sort: 10 7 8 9 1 5 
Sorted vector (descending): 10 9 8 7 5 1

Sorting Custom Objects

Quick Sort can easily sort custom objects, like sorting a list of students by their age or name. You can achieve this by providing a custom comparison logic. C++ offers powerful ways to do this, such as using lambda expressions.

Let’s define a simple Student class and modify our quickSort and partition functions to accept a comparison function.

#include <iostream>
#include <vector>
#include <string>
#include <utility>   // For std::swap
#include <functional> // For std::function

// Define a simple Student class
class Student {
public:
  std::string name;
  int age;

  Student(std::string n, int a) : name(n), age(a) {}

  // Overload the << operator for easy printing
  friend std::ostream& operator<<(std::ostream& os, const Student& s) {
    os << "(" << s.name << ", " << s.age << ")";
    return os;
  }
};

// Template partition function accepting a comparison function
template<typename T>
int partition_custom(std::vector<T>& arr, int low, int high, std::function<bool(const T&, const T&)> compare) {
  T pivot = arr[high];
  int i = low - 1;
  for (int j = low; j < high; ++j) {
    // Use the custom comparison function: compare(element, pivot)
    // We expect compare(a, b) to return true if a should come before b
    if (compare(arr[j], pivot)) { 
      i++;
      std::swap(arr[i], arr[j]);
    }
  }
  std::swap(arr[i + 1], arr[high]);
  return i + 1;
}

// Template quickSort function accepting a comparison function
template<typename T>
void quickSort_custom(std::vector<T>& arr, int low, int high, std::function<bool(const T&, const T&)> compare) {
  if (low < high) {
    int pi = partition_custom(arr, low, high, compare);
    quickSort_custom(arr, low, pi - 1, compare);
    quickSort_custom(arr, pi + 1, high, compare);
  }
}

// Utility function to print a vector of any type T (requires << operator)
template<typename T>
void printVectorCustom(const std::vector<T>& arr) {
  for (const auto& val : arr) {
    std::cout << val << " ";
  }
  std::cout << std::endl;
}


int main() {
  // Example vector of Student objects
  std::vector<Student> students = {
    Student("Alice", 22),
    Student("Bob", 20),
    Student("Charlie", 25),
    Student("David", 22)
  };
  int n_students = students.size();

  std::cout << "\nOriginal student list: ";
  printVectorCustom(students);

  // Sort by age (ascending) using a lambda expression
  // The lambda returns true if s1's age is less than or equal to s2's age
  quickSort_custom(students, 0, n_students - 1, 
                   [](const Student& s1, const Student& s2) {
                     return s1.age <= s2.age; 
                   });
  
  std::cout << "Sorted student list by age: ";
  printVectorCustom(students);
  // Note: Quick sort is not stable, so the relative order of Alice and David might change.

  // Sort by name (ascending) using a lambda expression
  quickSort_custom(students, 0, n_students - 1,
                   [](const Student& s1, const Student& s2) {
                     return s1.name <= s2.name;
                   });

  std::cout << "Sorted student list by name: ";
  printVectorCustom(students);

  return 0;
}

Explanation:

  1. We define a Student class.
  2. We overload the << operator for Student to make printing easier.
  3. We use C++ templates (template<typename T>) to make our partition_custom and quickSort_custom functions generic – they can work with vectors of any type T.
  4. Both functions now accept an extra argument: std::function<bool(const T&, const T&)> compare. This is a way to pass any function (including lambdas) that takes two T objects and returns true if the first should come before or be equal to the second in the sorted order.
  5. Inside partition_custom, we use if (compare(arr[j], pivot)) to decide whether to swap.
  6. In main, we create a vector of Student objects.
  7. We call quickSort_custom, passing a lambda expression as the comparison function.
    • For sorting by age: [](const Student& s1, const Student& s2) { return s1.age <= s2.age; }
    • For sorting by name: [](const Student& s1, const Student& s2) { return s1.name <= s2.name; }

This approach makes the Quick Sort implementation highly reusable and adaptable for various data types and sorting criteria.

What’s Next?

Now that you’ve seen how to implement Quick Sort in C++, you can explore further: