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 Insertion Sort algorithm.

Insertion Sort is a simple and elegant sorting algorithm often taught in introductory computer science courses. The idea behind it is to continually insert an element from the unsorted section of the array into the sorted section until the entire array is sorted.

2. Program Overview

Our C++ program is structured as:

1. insertionSort(): The central function that applies Insertion Sort to sort the array.

2. printArray(): A utility function to display the array's elements.

3. main(): The main function that triggers the program.

3. Code Program

#include<iostream>
using namespace std;

// Function to perform insertion sort in descending order
void insertionSort(int arr[], int n) {
    int key, j;
    for (int i = 1; i < n; i++) {
        key = arr[i]; // The element to be compared
        j = i - 1;
        
        // Move elements of arr[0..i-1] that are less than key
        // to one position ahead of their current position
        while (j >= 0 && arr[j] < key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // Position the key in its correct spot
    }
}

// Utility 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[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Original array: \n";
    printArray(arr, n);

    insertionSort(arr, n);

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

Output:

Original array:
64 25 12 22 11 
Sorted array in descending order: 
64 25 22 12 11

4. Step By Step Explanation

1. insertionSort(): Starting from the second element (indexed at 1), we continuously insert elements from the unsorted part to the sorted section. For descending order, if the 'key' element is larger than the preceding ones, we shift those elements to the right to place the 'key' in its rightful position.

2. printArray(): A simple utility to display the array's status. Useful for presenting the pre and post-sort state of the array.

3. main(): This drives the program. It sets up a test array, displays it, runs the insertion sort, and then showcases the sorted array.

Insertion Sort's simplicity can be its advantage when dealing with small arrays or almost sorted data. But for large datasets, more advanced algorithms like QuickSort or MergeSort might be a better fit due to their superior time complexities.

Related C++ Programs on Sorting Algorithms

Related C++ Programs with Output and Step-By-Step Explanation:

Java Guides

Search This Blog

Insertion Sort in Descending Order in C++