Selection Sort in Descending Order in C

1. Introduction

Selection Sort is a straightforward comparison-based sorting algorithm. It operates by dividing the input list into two parts: a sorted section and an unsorted section. The main idea is to repeatedly select the largest (for descending order) element from the unsorted subarray and swap it with the first unsorted element. This moves the boundary between the sorted and unsorted subarrays one element to the right.

2. Program Overview

The structure of the program is as follows:

1. swap: A utility function to interchange two integer values.

2. selectionSortDesc: The primary function that implements the Selection Sort algorithm in descending order.

3. printArray: A function to print out the content of the array.

4. main: The primary function where the program execution starts.

3. Code Program

#include <stdio.h>

// Utility function to swap two integer values
void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// Implementation of selectionSortDesc to sort in descending order
void selectionSortDesc(int arr[], int n) {
    int i, j, max_idx;

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

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

// Main function to test the selectionSortDesc function
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSortDesc(arr, n);
    printf("Sorted array in descending order: \n");
    printArray(arr, n);
    return 0;
}

Output:

Sorted array in descending order:
64 25 22 12 11

4. Step By Step Explanation

The selectionSortDesc function operates in the following step-by-step manner:

1. Start from the first element. Look for the largest element within the entire array. Once found, swap this element with the first position in the list.

2. Move to the second element. Now, search for the largest element from the second position up to the last. Once located, swap this element with the second position.

3. Continue this process. Each time, the "maximum" element from the unsorted subarray is selected and moved to its appropriate location in the sorted subarray.

4. By iterating through this process, by the end, the array will be sorted in descending order.

The key here is in the selection: for descending order, we consistently select the largest available element from the unsorted section of our array.

Related C Programs on Sorting Algorithms

1. Bubble Sort in Ascending Order in C
2. Bubble Sort in Descending Order in C
3. Selection Sort in Ascending Order in C
4. Selection Sort in Descending Order in C
5. Insertion Sort in Ascending Order in C
6. Insertion Sort in Descending Order in C
7. Merge Sort in Ascending Order in C
8. Merge Sort in Descending Order in C
9. Quick Sort in Ascending Order in C
10. Quick Sort in Descending Order in C
11. Heap Sort in Ascending Order in C
12. Heap Sort in Descending Order in C