C++ Program For Selection Sort In Descending Order

Understanding how to sort data is fundamental in computer science, enabling efficient organization and retrieval. In this article, you will learn how to implement the selection sort algorithm in C++ to arrange elements in descending order.

Problem Statement

Efficiently organizing data is crucial in many applications, from database management to displaying search results. The challenge is to sort a given array of numbers using the selection sort algorithm so that the largest elements appear first, progressing towards the smallest elements at the end. This requires a stable and predictable sorting mechanism that can handle various array sizes.

Example

Consider an unsorted array: [64, 25, 12, 22, 11]

After applying selection sort in descending order, the array should become: [64, 25, 22, 12, 11]

Background & Knowledge Prerequisites

To understand and implement selection sort in C++, readers should be familiar with:

• C++ Basics: Fundamental syntax, data types (e.g., int), and variable declaration.
• Arrays: How to declare, initialize, and access elements in a one-dimensional array.
• Loops: for loops for iterating through arrays and controlling program flow.
• Conditional Statements: if statements for comparisons and decision-making.
• Functions: How to define and call functions to modularize code.

Use Cases or Case Studies

Sorting data in descending order is useful in various practical scenarios:

• Leaderboards: Displaying game scores from highest to lowest.
• Product Listings: Showing items by price, from most expensive to least expensive.
• Search Results: Ranking relevant results with the highest relevance score appearing first.
• Financial Reports: Organizing transactions or account balances from largest to smallest.
• Performance Metrics: Listing employees or systems by their performance metrics, highest first.

Solution Approaches

Selection Sort for Descending Order

Selection sort works by repeatedly finding the maximum element from the unsorted part of the array and putting it at the beginning of the unsorted part. For descending order, this means finding the largest element and swapping it with the element at the current position, effectively moving the largest elements to the front of the array.

// Selection Sort Descending
#include <iostream>
#include <vector> // Using vector for dynamic array, can be adapted for static arrays
#include <algorithm> // For std::swap

// Function to print the array
void printArray(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    // Step 1: Initialize an unsorted array
    std::vector<int> arr = {64, 25, 12, 22, 11};
    int n = arr.size();

    std::cout << "Original array: ";
    printArray(arr);

    // Step 2: Implement Selection Sort for descending order
    // Iterate through the array from the first element to the second-to-last
    for (int i = 0; i < n - 1; ++i) {
        // Assume the current element is the maximum
        int max_idx = i;

        // Find the index of the actual maximum element in the unsorted part (from i+1 to n-1)
        for (int j = i + 1; j < n; ++j) {
            // If we find an element greater than the current maximum, update max_idx
            if (arr[j] > arr[max_idx]) {
                max_idx = j;
            }
        }

        // Step 3: Swap the found maximum element with the element at the current position 'i'
        // This places the largest element in its correct position (beginning of the unsorted part)
        if (max_idx != i) {
            std::swap(arr[i], arr[max_idx]);
        }

        std::cout << "Array after pass " << i + 1 << ": ";
        printArray(arr);
    }

    // Step 4: Display the sorted array
    std::cout << "Sorted array (descending): ";
    printArray(arr);

    return 0;
}

Run

Sample Output:

Original array: 64 25 12 22 11 
Array after pass 1: 64 25 12 22 11 
Array after pass 2: 64 25 22 12 11 
Array after pass 3: 64 25 22 12 11 
Array after pass 4: 64 25 22 12 11 
Sorted array (descending): 64 25 22 12 11

Stepwise Explanation:

1. Initialization: The code starts with an unsorted std::vector and determines its size n. A helper function printArray is defined to display the array's current state.
2. Outer Loop: The outer for loop runs from i = 0 to n - 2. This i represents the current position where we want to place the next largest element.
3. Inner Loop (Finding Maximum): For each i, the inner for loop (from j = i + 1 to n - 1) iterates through the *unsorted* part of the array to find the index of the maximum element (max_idx).

• It initially assumes arr[i] is the maximum (max_idx = i).
• If any arr[j] is greater than arr[max_idx], max_idx is updated to j.

1. Swapping: After the inner loop completes, max_idx holds the index of the largest element in the unsorted subarray arr[i...n-1].

• If max_idx is different from i (meaning a larger element was found), std::swap is used to exchange arr[i] with arr[max_idx]. This places the largest element found into its correct descending order position at arr[i].

1. Iteration: The outer loop then increments i, moving to the next position to find the next largest element from the remaining unsorted portion.
2. Output: After all passes, the array arr will be sorted in descending order, and the final result is printed.

Conclusion

Selection sort offers a straightforward approach to arranging data. By repeatedly identifying the largest element in the unsorted section and moving it to its correct position, this algorithm effectively sorts arrays in descending order. While simple to implement, its quadratic time complexity makes it more suitable for smaller datasets or educational purposes.

Summary

• Algorithm: Selection sort identifies the maximum element in the unsorted portion of an array and places it at the correct position.
• Descending Order: For descending sort, the largest element is swapped with the element at the current position, building the sorted array from left to right with the biggest values first.
• Process: An outer loop iterates through positions; an inner loop finds the maximum in the remaining unsorted part; a swap places the maximum.
• Efficiency: Selection sort has a time complexity of O(n^2), making it less efficient for large datasets compared to algorithms like merge sort or quicksort.
• Implementation: Easily implemented using nested loops and a swap operation in C++.