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

Selection Sort is a straightforward sorting algorithm, and while it's not the most efficient method for large datasets, its underlying concept is clear and instructive for beginners. The idea revolves around repeatedly identifying the largest (in descending order) element from the unsorted portion of the list and positioning it at the beginning of this section.

2. Program Overview

The C++ program contains:

1. swap(): A function to interchange two elements.

2. selectionSort(): The primary function that uses Selection Sort to sort the array.

3. printArray(): A function to display the contents of the array.

4. main(): The driving function to run the program.

3. Code Program

#include<iostream>
using namespace std;

// Utility function to swap two elements
void swap(int &x, int &y) {
    int temp = x;
    x = y;
    y = temp;
}

// Main function to perform selection sort in descending order
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int max_idx = i; // Find the maximum element in the unsorted array
        for (int j = i+1; j < n; j++) {
            if (arr[j] > arr[max_idx]) {
                max_idx = j;
            }
        }
        // Swap the found maximum element with the first element of the unsorted segment
        swap(arr[max_idx], arr[i]);
    }
}

// Function to print an 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);

    selectionSort(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. swap(): This utility exchanges two elements. It's invoked in our selection sort function when the current maximum is located.

2. selectionSort(): The main logic resides here. In each iteration, the function identifies the largest element from the yet-unsorted segment and swaps it with the starting position of this segment.

3. printArray(): This function visually outputs the array components, aiding in witnessing the before-and-after effects of the sorting.

4. main(): The pivotal function sets up a sample array, presents it, executes the selection sort, and then prints the sorted array.

Although Selection Sort is relatively easy to understand, it is not optimized for performance, especially for vast datasets. With a consistent time complexity of O(n^2) across various cases, it's beneficial to employ more effective sorting techniques like QuickSort or MergeSort for significant data.

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++