Quick Sort in Descending Order in C++

1. Introduction

In this blog post, we will learn how to write a C++ program to sort an array of integers in Descending Order using the Quick Sort algorithm.

Quick Sort is one of the most efficient sorting algorithms. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays based on whether they are greater than or less than the pivot. The sub-arrays are then recursively sorted. 

2. Program Overview

1. partition(): Function that takes the last element as a pivot, places the pivot at its correct position in the sorted array, and places all elements greater on the left and all smaller elements on the right.

2. quickSort(): The main recursive function that implements QuickSort.

3. printArray(): Utility function to print the array.

4. main(): Driver function to test the above.

3. Code Program

#include<iostream>
using namespace std;

// Function to partition the array such that elements greater than the pivot will be on the left and smaller on the right
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // Taking last element as pivot
    int i = (low - 1);  // Index for greater element

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

// Function to implement QuickSort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // Getting pivot element's correct position
        quickSort(arr, low, pi - 1);  // Recursively sorting elements before and after partition
        quickSort(arr, pi + 1, high);
    }
}

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

// Driver function
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Original array is: \n";
    printArray(arr, n);
    
    quickSort(arr, 0, n - 1);
    
    cout << "Sorted array in descending order is: \n";
    printArray(arr, n);
    return 0;
}

Output:

Original array is:
10 7 8 9 1 5 
Sorted array in descending order is: 
10 9 8 7 5 1 

4. Step By Step Explanation

1. partition(): This function is responsible for placing the pivot element in its correct position (all greater elements on the left and smaller elements on the right). In our descending order variant, the loop inside this function checks if the current element is greater than or equal to the pivot, and if so, swaps it.

2. quickSort(): This function is the main player, recursively calling itself to sort the two partitions obtained after the partition() function.

3. printArray(): This is a simple utility function to print the contents of the array.

4. main(): Here, we test our QuickSort function on a sample array and print before and after sorting.

The logic of QuickSort remains consistent, whether for ascending or descending order. The only major change is in the partition logic.

Related C++ Programs on Sorting Algorithms

• Bubble Sort in Ascending Order in C++
• Bubble Sort in Descending Order in C++
• Selection Sort in Ascending Order in C++
• Selection Sort in Descending Order in C++
• Insertion Sort in Ascending Order in C++
• Insertion Sort in Descending Order in C++
• Merge Sort in Ascending Order in C++
• Merge Sort in Descending Order in C++
• Quick Sort in Ascending Order in C++
• Quick Sort in Descending Order in C++
• Heap Sort in Ascending Order in C++
• Heap Sort in Descending Order in C++