Sort an Array in Descending Order in C++

In this article, we will discuss six different ways to sort an array in descending order in C++.

Table Of Contents

There are commonly used 5 algorithms that can be used for sorting an array in descending order.

Suppose we have an array of numbers like this,

int arr[] = {8, -901, 89, 0, 18, 791, -87};

We want to sort this array in descending order. After sorting, the content should be like,

791 89 18 8 0 -87 -901

Sort Array in Descending Order in C++ using STL’s std::sort()

The sort() function mainly accepts three arguments. First one is the starting address position and second one is the last address position of the array which need to be sorted. The third optional argument can be passed to determine the sorting order. Like in this case we can pass greater<>() for descending order. By default sort() will sort the array in ascending order but if we pass the greater<>() as comparator then it will sort the elements in descending order.

Example

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
    int arr[] = {8, -901, 89, 0, 18, 791, -87};
    size_t len = sizeof(arr)/sizeof(arr[0]);

    // Calling sort() function from STL passing starting and
    // ending address of array and greater<>() in third argument.
    sort(arr, arr + len, greater<>());

    // Printing Output
    cout<<"The descendingly sorted array is: ";
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout<<endl;
}

Output

The descendingly sorted array is: 791 89 18 8 0 -87 -901

It sorted the Array in descending order.

Sort Array in Descending Order using Bubble Sort

This is the simplest algorithm to sort array in descending order. In each step one element form the last of array is set in position.
bubble_sort() is the function in which bubble sort is implemented.

Time Complexity: O(n^2)
Space Complexity: O(1)

Example

#include <iostream>

using namespace std;

//Bubble Sort Algorithm
void bubble_sort(int* arr, size_t len)
{
    int temp;
    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j + 1 < len - i; j++)
        {
            // Swaping the elements if first one is
            // smaller than second one.
            if (arr[j] < arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// Driver Code
int main()
{
    int arr[] = {8, -901, 89, 0, 18, 791, -87};
    size_t len = sizeof(arr)/sizeof(arr[0]);

    // Calling bubble_sort function with given array
    bubble_sort(arr, len);

    // Printing Output
    cout<<"The descendingly sorted array is: ";
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout<<endl;
}

Output

The descendingly sorted array is: 791 89 18 8 0 -87 -901

It sorted the Array in descending order.

Sort Array in Descending Order using Insertion Sort

In this algorithm we will assume one subarray as sorted and go on adding elements to that array. Initially only single element of array is assumed to be sorted. The insertion_sort() is the function in which insertion sort is implemented.

Time Complexity: O(n^2)
Space Complexity: O(1)

Example

#include <iostream>

using namespace std;

void insertion_sort(int* arr, size_t len)
{
    int temp;
    // Assuming one element as sorted and
    // inserting other elements to it
    for (int i = 1; i < len; i++)
    {
        temp = arr[i];
        // Finding the sorted position for selected
        // element in sorted array and placing it into place.
        for (int j = i - 1; j >= 0; j--)
        {
            if (temp < arr[j])
            {
                arr[j + 1] = temp;
                break;
            }
            else if (temp >= arr[j])
            {
                arr[j + 1] = arr[j];
                if (j == 0)
                {
                    arr[j] = temp;
                }
            }
        }
    }
}

int main()
{
    int arr[] = {8, -901, 89, 0, 18, 791, -87};
    size_t len = sizeof(arr)/sizeof(arr[0]);

    // Calling insertion_sort function with given array
    insertion_sort(arr, len);

    // Printing Output
    cout << "The descendingly sorted Array is: ";
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout<<endl;
}

Output

The descendingly sorted Array is: 791 89 18 8 0 -87 -901

It sorted the Array in descending order.

Sorting Array in Descending Order using Selection Sort

In selection sort we will virtually divide the array into two parts viz sorted and unsorted. Sorted subarray will be in beginning of array and we will select largest element from the unsorted subarray and we will add it to the sorted array.

Time Complexity: O(n^2)
Space Complexity: O(1)

Example

#include <iostream>

using namespace std;

void selection_sort(int* arr, int len)
{
    int max, temp;

    // Iterating for each element except first element.
    for (int i = 0; i < len - 1; i++)
    {
        max = arr[i];
        // Finding the maximum element from unsorted array
        // and adding to sorted array.
        for (int j = i; j < len; j++)
        {
            if (max < arr[j])
            {
                max = arr[j];
                temp = j;
            }
        }
        arr[temp] = arr[i];
        arr[i] = max;
    }
}

int main()
{
    int arr[] = {8, -901, 89, 0, 18, 791, -87};
    size_t len = sizeof(arr)/sizeof(arr[0]);

    // Calling selection_sort function with given array
    selection_sort(arr, len);

    // Printing Output
    cout << "The descendingly sorted Array is: ";
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout<<endl;
}

Output

The descendingly sorted Array is: 791 89 18 8 0 -87 -901

It sorted the Array in descending order.

Sorting Array in Descending Order Merge Sort

Merge Sort works on Divide and Conquer algorithm technique. This algorithm consists of two main functions generally named as merge_sort() and merge(). The merge_sort() function will continuously divide the array into smaller and smaller parts. The merge() function will merge all the subarrays according to descending order, finally constructing the main array.

Time Complexity: O(nlog(n))
Space Complexity: O(n)

Example

#include <iostream>

using namespace std;

void merge_sort(int *arr, int start, int last);
void merge(int *arr, int start, int last);

int main()
{
    int arr[] = {8, -901, 89, 0, 18, 791, -87};
    size_t len = sizeof(arr)/sizeof(arr[0]);

    // Calling the merge_sort function which recursively divides array into half
    merge_sort(arr, 0, len-1);

    // Printing Output
    cout << "The descendingly sorted Array is: ";
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout<<endl;
}


// This function divides array recursively.
void merge_sort(int *arr, int start, int last)
{
    if (start < last)
    {
        int mid = (start + last) / 2;
        merge_sort(arr, start, mid);  // Recurssion
        merge_sort(arr, mid + 1, last); // Recurssion
        merge(arr, start, last);
    }
}

// This function merges two sorted subarray into one in descending order
void merge(int *arr, int start, int last)
{
    // Creating temporary array to store sorted array
    int temp[(last - start) + 1];
    int pos = 0;
    int i = start,j=(start + last)/2 + 1;

    // Filling the array in descending order
    while(i<(start + last)/2 + 1 && j<=last)
    {
        if(arr[i] < arr[j])
        {
            temp[pos]=arr[j];
            j++;
        }
        else
        {
            temp[pos]=arr[i];
            i++;
        }
        pos++;
    }

    if(j>last)
    {
        while(i<((start + last)/2 + 1))
        {
            temp[pos]=arr[i];
            i++;
            pos++;
        }
    }
    else
    {
        while(j <= last)
        {
            temp[pos]=arr[j];
            j++;
            pos++;
        }
    }

    // Storing temp in array
    for(int i=0; i<(last - start + 1); i++)
    {
        arr[start + i] = temp[i];
    }
}

Output

The descendingly sorted Array is: 791 89 18 8 0 -87 -901

It sorted the Array in descending order.

Sort Array in Descending Order using Quick Sort

This algorithm follows divide and conquer approach for sorting an array. Firstly in this algorithm we need to decide the pivot for quick sort to perform. It consists of a quick_sort() function which is called recursively.

Time Complexity: O(n^2)
Space Complexity: O(log(n))

Example

#include <iostream>

using namespace std;

void quick_sort(int *arr, int start, int last);

int main()
{
    int arr[] = {8, -901, 89, 0, 18, 791, -87};
    size_t len = sizeof(arr)/sizeof(arr[0]);

    // Calling the quick_sort function
    quick_sort(arr, 0, len-1);

    // Printing Output
    cout << "The descendingly sorted Array is: ";
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout<<endl;
}

void quick_sort(int *arr, int start, int last)
{
    if (start < last)
    {
        int i = start, temp, j = last, pivot = arr[start];

        // Placing the element from pivot to its sorted position.
        while (j >= i)
        {
            while (arr[i] >= pivot)
                i++;
            while (arr[j] < pivot)
                j--;
            if (i < j)
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        temp = pivot;
        arr[start] = arr[j];
        arr[j] = temp;

        quick_sort(arr, j + 1, last);  // Recurssion
        quick_sort(arr, start, j - 1);  // Recurssion
    }
}

Output

The descendingly sorted Array is: 791 89 18 8 0 -87 -901

It sorted the Array in descending order.

Summary

We have seen that how to sort array in descending order with help of five different algorithms and using STL function sort(). Each algorithm had its own Time and Space complexity.