Skip to lab content

UNIT 05 · Sorting and Searching

Selection sort in descending order

EXERCISE 05DC173 sample runs

THE SYLLABUS QUESTION

What you need to solve

Write a C program that sorts the given array of integers using selection sort in descending order.
Input format & conventions

Array size n (1–100), followed by n integers between -1,000,000 and 1,000,000.

UNDERSTAND THE IDEA

Explanation

Descending order requires selecting the maximum from the remaining unsorted suffix. Swap that maximum into the next output position.

Unlike bubble sort, selection sort first identifies a target index and then performs at most one swap per pass.

PLAN BEFORE CODING

Algorithm

  1. Read the array.
  2. For position i, assume a[i] is the remaining maximum.
  3. Scan the suffix and record the index of a larger value.
  4. Swap that maximum into position i.
  5. Repeat and display descending order.

SEE THE CONTROL FLOW

Flowchart

Follow the arrows from Start. Diamonds ask a question; labeled arrows show the answer. A returning arrow repeats a loop. Function internals are grouped where needed; later input checks follow the rules in the program.

Flowchart for Selection sort in descending order: input, decisions, processing, output and loop paths

On a phone, scroll sideways to read the diagram at full size. Open full-size flowchart ↗

C17

Complete C program

Download .c
#include <stdio.h>
#define MAX_SIZE 100

int readArray(int a[], int *n) {
    if (scanf("%d", n) != 1 || *n < 1 || *n > MAX_SIZE) return 0;
    for (int i = 0; i < *n; ++i)
        if (scanf("%d", &a[i]) != 1 || a[i] < -1000000 || a[i] > 1000000) return 0;
    return 1;
}

void printArray(const int a[], int n) {
    for (int i = 0; i < n; ++i) printf("%s%d", i == 0 ? "" : " ", a[i]);
    putchar('\n');
}

void selectionSortDescending(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        int maxIndex = i;
        for (int j = i + 1; j < n; ++j)
            if (a[j] > a[maxIndex]) maxIndex = j;
        if (maxIndex != i) {
            int temp = a[i]; a[i] = a[maxIndex]; a[maxIndex] = temp;
        }
    }
}

int main(void) {
    int a[MAX_SIZE], n;
    if (!readArray(a, &n)) { puts("Invalid input."); return 1; }
    selectionSortDescending(a, n);
    printf("Descending: "); printArray(a, n);
    return 0;
}
Open in compiler ↗

Code loads into the existing compiler. Enter the sample input there; sign-in and execution rules stay the same.

Compile and run locally
gcc -std=c17 selection-sort-descending.c -o lab
./lab

On Windows, run .\lab.exe after compiling with GCC. The interest program requires the math library where applicable.

FOLLOW THE VALUES

Dry run

Step / stateOperationResult
Start5 1 4 2Maximum 5 stays at position 1
Pass 25 4 1 2Move maximum of suffix (4) to position 2
Pass 35 4 2 1Move 2 ahead of 1

CHECK THE BEHAVIOR

Sample input & output

Each output below was produced by compiling and running this exact program. Input values are entered in the stated order; the examples do not print input prompts.

Sample 1

INPUT 
4
5 1 4 2
OUTPUT
Descending: 5 4 2 1

Sample 2

INPUT 
5
3 -1 3 0 -2
OUTPUT
Descending: 3 3 0 -1 -2

Sample 3

INPUT 
1
7
OUTPUT
Descending: 7

Common mistakes

  • For descending order, select the maximum rather than the minimum.
  • Remember to update the selected index, not just a temporary value.

WHY THIS GROWTH RATE?

Time and space complexity

Time O(n²) in best and worst cases; O(1) additional space.

For each output position, the program scans the entire remaining suffix to find its maximum. The scans contain (n − 1) + (n − 2) + … + 1 comparisons = n(n − 1)/2.

These scans still happen when the input is already sorted, because the algorithm does not stop early. Both best-case and worst-case time are O(n²). At most one swap is needed per position; swaps add only O(n) work. Sorting in place with counters and one temporary value gives O(1) auxiliary space.

Big-O describes how work grows as the stated input quantity grows; fixed factors and lower-order terms are omitted. The analysis treats fixed-width arithmetic as constant cost and the published limits as practical safety bounds.