C Program For Selection Sort In Descending Order

In this article, you will learn how to implement the selection sort algorithm in C to arrange an array of numbers in descending order. This method is straightforward and provides a clear understanding of comparison-based sorting.

Problem Statement

Efficiently arranging a collection of numerical data in descending order is a common requirement in various programming tasks. For instance, you might need to display product prices from highest to lowest, rank students by their scores, or process sensor readings from most recent to oldest. The challenge lies in developing an algorithm that systematically places the largest elements at the beginning of the array.

Example

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

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

Background & Knowledge Prerequisites

To understand and implement selection sort, a basic grasp of the following C programming concepts is essential:

• Arrays: Storing collections of data of the same type.
• Loops: for loops for iterating through arrays.
• Conditional Statements: if statements for comparisons.
• Functions: Defining and calling functions (e.g., for sorting and printing).
• Variable Declaration: Understanding data types and variable scope.

Use Cases or Case Studies

Sorting data in descending order using algorithms like selection sort is applicable in numerous scenarios:

• Leaderboards: Displaying game scores from highest to lowest.
• Financial Reports: Arranging transaction amounts or stock prices with the largest values first.
• Product Catalogs: Showing product listings by price, rating, or popularity in descending order.
• Data Analysis: Identifying the top performers or largest values in a dataset quickly.
• Scheduling: Prioritizing tasks based on urgency or importance, with the most critical tasks appearing first.

Solution Approaches

This section details the implementation of the Selection Sort algorithm to sort an array in descending order.

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.

One-line summary

Iteratively finds the largest remaining element and swaps it into its correct position at the current start of the unsorted subarray.

Code Example

// Selection Sort in Descending Order
#include <stdio.h>

// Function to swap two elements
void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// Function to perform selection sort in descending order
void selectionSortDescending(int arr[], int n) {
    int i, j, max_idx;

    // One by one move boundary of unsorted subarray
    for (i = 0; i < n - 1; i++) {
        // Find the maximum element in unsorted array
        max_idx = i;
        for (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 subarray
        swap(&arr[max_idx], &arr[i]);
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");
}

int main() {
    // Step 1: Initialize an array and its size
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Print the original array
    printf("Original array: ");
    printArray(arr, n);

    // Step 3: Call selection sort function to sort in descending order
    selectionSortDescending(arr, n);

    // Step 4: Print the sorted array
    printf("Sorted array (descending): ");
    printArray(arr, n);

    return 0;
}

Run

Sample Output

Original array: 64 25 12 22 11 
Sorted array (descending): 64 25 22 12 11

Stepwise Explanation

1. swap Function: This helper function takes two integer pointers and exchanges their values. It's a standard utility for many sorting algorithms.
2. selectionSortDescending Function:

• It iterates from the first element (i = 0) up to the second-to-last element (n - 1). The outer loop defines the current position where the largest element from the *remaining unsorted portion* should be placed.
• Inside the outer loop, max_idx is initialized to i, assuming the current element is the maximum.
• An inner loop (j = i + 1 to n) then scans the rest of the unsorted array to find the *actual* largest element. If arr[j] is greater than arr[max_idx], max_idx is updated to j.
• After the inner loop completes, max_idx holds the index of the largest element in the unsorted subarray arr[i...n-1].
• The swap function is then called to exchange the element at arr[max_idx] with the element at arr[i]. This places the largest found element into its correct descending order position.

1. printArray Function: A simple utility to display the contents of an array.
2. main Function:

• An example array arr is initialized.
• The size n of the array is calculated.
• The original array is printed.
• The selectionSortDescending function is called to sort the array.
• The sorted array is then printed, demonstrating the descending order.

Conclusion

Selection sort is a simple, in-place comparison sort that is intuitive to understand and implement. By repeatedly finding the maximum element in the unsorted portion and moving it to the correct position, it effectively sorts an array in descending order. While its time complexity of O(n^2) makes it less efficient for very large datasets compared to algorithms like merge sort or quicksort, it remains a valuable concept for learning fundamental sorting principles.

Summary

• Selection Sort: An in-place comparison sorting algorithm.
• Descending Order Logic: Finds the maximum element in the unsorted subarray and places it at the current position.
• Time Complexity: O(n^2) in all cases (best, average, worst).
• Space Complexity: O(1) as it sorts the array in place without requiring additional storage.
• Use Cases: Suitable for small datasets or educational purposes due to its simplicity.