Selection Sort: flowchart, algorithm and program

This program reads n numbers into an array and sorts them in ascending order using selection sort. On each pass it finds the smallest value in the unsorted part and swaps it into its correct position.

▶ Watch the dry run step by step →

Algorithm

  1. Step 1: Start.
  2. Step 2: Read n.
  3. Step 3: Set i = 0.
  4. Step 4: If i < n, go to step 5; otherwise go to step 7.
  5. Step 5: Read a[i].
  6. Step 6: Set i = i + 1. Go to step 4.
  7. Step 7: Set i = 0.
  8. Step 8: If i < n - 1, go to step 9; otherwise go to step 16.
  9. Step 9: Set min = i, j = i + 1.
  10. Step 10: If j < n, go to step 11; otherwise go to step 14.
  11. Step 11: If a[j] < a[min], go to step 12; otherwise go to step 13.
  12. Step 12: Set min = j.
  13. Step 13: Set j = j + 1. Go to step 10.
  14. Step 14: Swap a[i] and a[min] using temp.
  15. Step 15: Set i = i + 1. Go to step 8.
  16. Step 16: Set i = 0.
  17. Step 17: If i < n, go to step 18; otherwise go to step 20.
  18. Step 18: Print a[i].
  19. Step 19: Set i = i + 1. Go to step 17.
  20. Step 20: Stop.

Pseudocode

BEGIN
    READ n
    i ← 0
    WHILE i < n DO
        READ a[i]
        i ← i + 1
    END WHILE
    i ← 0
    WHILE i < n - 1 DO
        min ← i, j ← i + 1
        WHILE j < n DO
            IF a[j] < a[min] THEN
                min ← j
            END IF
            j ← j + 1
        END WHILE
        Swap a[i] and a[min] using temp
        i ← i + 1
    END WHILE
    i ← 0
    WHILE i < n DO
        PRINT a[i]
        i ← i + 1
    END WHILE
END

Program in C, Python and Java

Selection Sort program in C

#include <stdio.h>

int main() {
    int n, i, j, min, temp;
    int a[100];

    printf("Enter n: ");
    scanf("%d", &n);

    printf("Enter %d numbers: ", n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }

    printf("Sorted array: ");
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

Selection Sort program in Python

n = int(input("Enter n: "))
a = list(map(int, input("Enter " + str(n) + " numbers: ").split()))

for i in range(n - 1):
    min = i
    for j in range(i + 1, n):
        if a[j] < a[min]:
            min = j
    temp = a[i]
    a[i] = a[min]
    a[min] = temp

print("Sorted array:", end=" ")
for i in range(n):
    print(a[i], end=" ")
print()

Selection Sort program in Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter n: ");
        int n = sc.nextInt();
        int[] a = new int[n];

        System.out.print("Enter " + n + " numbers: ");
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        for (int i = 0; i < n - 1; i++) {
            int min = i;
            for (int j = i + 1; j < n; j++) {
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }

        System.out.print("Sorted array: ");
        for (int i = 0; i < n; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}

Sample input: n = 5, numbers = 64 25 12 22 11
Output: Sorted array: 11 12 22 25 64

How it works

  • The outer loop runs i from 0 to n - 2. Everything before index i is already sorted, so each pass fixes one more position.
  • At the start of each pass, min = i. It holds the index of the smallest value found so far in the unsorted part.
  • The inner loop runs j from i + 1 to n - 1. If a[j] < a[min], we set min = j, so by the end min points to the smallest element of a[i..n-1].
  • After the inner loop, we swap a[i] and a[min] using temp. The smallest remaining value now sits at index i.
  • For 64 25 12 22 11: pass 0 swaps 64 and 11 to get 11 25 12 22 64, pass 1 swaps 25 and 12 to get 11 12 25 22 64, pass 2 swaps 25 and 22 to get 11 12 22 25 64, and pass 3 finds nothing to move. The result is 11 12 22 25 64.

Dry run (trace table)

StepLineBoxniaminjtempOutput
13Start
28Read n5Enter n: Enter 5 numbers:
311i = 050
411i < n?50
512Read a[i]50[64]
611i = i + 151[64]
711i < n?51[64]
812Read a[i]51[64,25]
911i = i + 152[64,25]
1011i < n?52[64,25]
1112Read a[i]52[64,25,12]
1211i = i + 153[64,25,12]
1311i < n?53[64,25,12]
1412Read a[i]53[64,25,12,22]
1511i = i + 154[64,25,12,22]
1611i < n?54[64,25,12,22]
1712Read a[i]54[64,25,12,22,11]
1811i = i + 155[64,25,12,22,11]
1911i < n?55[64,25,12,22,11]
2015i = 050[64,25,12,22,11]

Time and space complexity

Time: O(n²) · Space: O(1). The nested loops compare every pair of elements (about n²/2 comparisons) and sorting is done in place with only a few extra variables.

Common mistakes

  • Swapping inside the inner loop every time a smaller value is found. That turns it into a different, messier algorithm. Track the index in min and swap only once per pass, after the inner loop.
  • Storing the minimum value instead of its index. Without the index, you can't tell which position to swap with a[i].
  • Starting the inner loop at j = i instead of i + 1, or running the outer loop to n instead of n - 1. The code still works, but it does needless extra comparisons.

Viva questions

Q1. What is the basic idea of selection sort as implemented in this program?

For each position i, it finds the smallest element in the unsorted part (i to n-1) and swaps it into position i. After each pass, the sorted part at the front grows by one element.

Q2. Why do you set min = i at the start of each outer loop pass (line 16)?

We start by assuming the element at position i is the smallest. The inner loop then compares the rest against a[min] and updates min if it finds anything smaller.

Q3. Why does the inner loop start at j = i + 1 and not at 0?

Positions 0 to i-1 are already sorted and in their final places. Position i is the one we assumed to be the minimum, so only the elements after it need checking.

Q4. Why does the outer loop run only up to i < n - 1 and not i < n?

When i reaches n-1 only one element is left, and it must already be the largest and in the right place. Another pass would do nothing.

Q5. What is the purpose of the temp variable in lines 22-24?

It holds a[i] while we copy a[min] into a[i]. Without it, the original a[i] would be overwritten and lost, so the swap would fail.

Q6. What happens if n is 1, n is 0, or all the elements are equal?

For n = 1 or n = 0 the outer loop never runs, so the array is printed unchanged. With equal elements, a[j] < a[min] is never true, so min stays i and each swap is a self-swap that changes nothing.

Q7. What is the time complexity of this selection sort in the best, average and worst case? How many swaps does it make?

It is O(n^2) in every case, because the inner loop always scans the whole unsorted part (about n(n-1)/2 comparisons) even if the array is already sorted. It makes at most n-1 swaps, which is O(n).

Q8. What would change if you wanted descending order? And is this sort stable?

Change the condition on line 18 to a[j] > a[min], so you pick the maximum each time. This version is not stable, because the long-distance swap can move an equal element past another equal element and change their original order.

Q9. What is the risk in declaring int a[100], and how would you handle it?

If the user enters n greater than 100, scanf writes past the end of the array, which is undefined behaviour. You should check that n is between 1 and 100 before reading, or size the array dynamically.

Frequently asked questions

What is the time complexity of selection sort?

It is O(n^2) in the best, average, and worst cases, because the inner loop always scans the whole unsorted part. It does at most n - 1 swaps, which is few compared to bubble sort.

Why does the outer loop stop at n - 2 (i < n - 1)?

When only one element is left, it is already in its correct place, so a pass for the last index would do nothing. Stopping at n - 2 saves that useless pass.

Is selection sort stable?

No, the usual swap-based version is not stable. Swapping a[i] with a[min] can jump an element over an equal one and change their original order.

More programs

← All programs

Try AI Flowchart free →