QUESTION 25 · Sorting

What is selected during each ascending selection-sort pass?

2 marks

Answer

The minimum value in the remaining unsorted part.

It is swapped into the next final position at the left.
The usual swapping version is not stable.

Explain selection sort and write a C program for ascending order.

5 marks

Answer in brief

Selection sort repeatedly chooses the smallest remaining value and places it at the beginning of the unsorted part.

Algorithm

Start the next final position at i = 0.
Assume a[i] is the smallest remaining value.
Scan indices i + 1 through n - 1 and remember the index of a smaller value when found.
Swap the chosen minimum into position i, then advance i.

Worked trace

For 5, 1 and 4, the first scan finds 1 at index 1. Swapping it with index 0 gives 1, 5, 4. The next scan finds 4 as the minimum of the remaining two values. The result becomes 1, 4, 5.

Why it works

Each completed pass fixes the next smallest value in the next leftmost position. The values before i are already in their correct sorted places, so the scan only examines the remaining part.

Time complexity

The first pass makes n - 1 comparisons, the next n - 2, and so on. The total is n(n - 1)/2, giving O(n²) comparisons in best, average and worst cases for this version. Already sorted input still requires those scans. At most n - 1 swaps are needed.

Space and stability

The algorithm uses O(1) auxiliary space. The usual distant-swap implementation is not stable. For labelled equal values 2A, 2B, 1, swapping the final 1 with 2A produces 1, 2B, 2A; the equal 2s have changed relative order. To sort descending instead, select the largest remaining value with a suitable comparison.

C program and output

Download .c Open compiler

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
void sort(int a[], int n)
{
    for (int i = 0; i < n - 1; ++i) {
        int smallest = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[smallest]) { smallest = j; }
        }
        if (smallest != i) {
            int temporary = a[i]; a[i] = a[smallest]; a[smallest] = temporary;
        }
    }
}

int main(void)
{
    int n, a[20];
    if (scanf("%d", &n) != 1 || n < 1 || n > 20) {
        puts("Unsupported input"); return 1;
    }
    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &a[i]) != 1 || a[i] < -10000 || a[i] > 10000) {
            puts("Unsupported input"); return 1;
        }
    }
    sort(a, n);
    for (int i = 0; i < n; ++i) {
        if (i > 0) { putchar(' '); }
        printf("%d", a[i]);
    }
    putchar('\n');
    return 0;
}

Sample input and output

Input

3
5 1 4

Output

1 4 5