---
title: "Selection sort with trace"
subject: "Data Structure and Algorithm"
chapter: 7
key: "semester_4/data_structure_and_algorithm:selection-sort-explain-trace"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/selection-sort-explain-trace
site: BCT Engineering
---

# Selection sort with trace

Data Structure and Algorithm · Chapter 7: Sorting

- Asked in: 2074 Bhadra, 10 marks
- Video: [Introduction to Selection Sort](https://www.youtube.com/watch?v=Z3dCjzhjAWA) — Lalitha Natraj
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/selection-sort-explain-trace
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7

## Question

Explain selection sort. Sort data sequence 40 90 20 -10 30 5 60 100 80 using selection sort method.

## Short answer

Selection sort finds the smallest element in the unsorted part and swaps it to the front. Sorting 40, 90, 20, -10, 30, 5, 60, 100, 80: after each pass, the array becomes -10, 5, 20, 30, 40, 60, 80, 90, 100. The final sorted sequence is -10, 5, 20, 30, 40, 60, 80, 90, 100.

## Answer

**Selection sort** repeatedly selects the smallest element from the unsorted part and exchanges it with the first element of that part. After pass *i*, the first *i* positions hold the *i* smallest elements in their final places.

#### Algorithm
```text
SelectionSort(a[0..n-1])
for i = 0 to n-2
    min = i
    for j = i+1 to n-1
        if a[j] < a[min]: min = j
    swap a[i], a[min]
```
```c
void selection_sort(int a[], int n) {
    int i, j, min, t;
    for (i = 0; i < n - 1; i++) {
        min = i;                              /* index of smallest so far */
        for (j = i + 1; j < n; j++)
            if (a[j] < a[min]) min = j;
        t = a[i]; a[i] = a[min]; a[min] = t;  /* exchange */
    }
}
```

#### Trace for 40 90 20 −10 30 5 60 100 80 (n = 9, 8 passes)
| Pass | Smallest found | Swap | Array after pass |
|---|---|---|---|
| 0 | – | – | 40 90 20 −10 30 5 60 100 80 |
| 1 | −10 | a[0] ↔ a[3] | −10 90 20 40 30 5 60 100 80 |
| 2 | 5 | a[1] ↔ a[5] | −10 5 20 40 30 90 60 100 80 |
| 3 | 20 | already in place | −10 5 20 40 30 90 60 100 80 |
| 4 | 30 | a[3] ↔ a[4] | −10 5 20 30 40 90 60 100 80 |
| 5 | 40 | already in place | −10 5 20 30 40 90 60 100 80 |
| 6 | 60 | a[5] ↔ a[6] | −10 5 20 30 40 60 90 100 80 |
| 7 | 80 | a[6] ↔ a[8] | −10 5 20 30 40 60 80 100 90 |
| 8 | 90 | a[7] ↔ a[8] | −10 5 20 30 40 60 80 90 100 |

**Sorted: −10, 5, 20, 30, 40, 60, 80, 90, 100**

#### Complexity
- Comparisons: (n−1) + (n−2) + ... + 1 = n(n−1)/2 in every case, so time is O(n²) (best, average and worst).
- At most n − 1 swaps, which is good when writes are costly.
- In-place (O(1) space) and not stable.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does selection sort do in each pass?
   A. Swaps adjacent out-of-order pairs
   B. Finds the smallest of the unsorted part and exchanges it with its first element
   C. Inserts the next element into a sorted prefix
   D. Splits the array in halves
   Answer: B. After pass i, the first i positions hold the i smallest elements. (Key point: Idea)

2. How many comparisons does selection sort make in total?
   A. n(n-1)/2 in every case
   B. n-1 in the best case
   C. n log n
   D. Depends on input order
   Answer: A. (n-1)+(n-2)+...+1 = n(n-1)/2 always. (Key point: Comparisons)

3. In the first pass on 40 90 20 -10 30 5 60 100 80, what is swapped?
   A. 40 with 5
   B. 40 with -10
   C. 90 with 20
   D. -10 with 5
   Answer: B. -10 is the smallest and at index 3, so a[0] and a[3] swap. (Key point: Trace)

4. Which is true of selection sort?
   A. Stable and best case O(n)
   B. At most n-1 swaps, in-place, not stable
   C. O(n log n) worst case
   D. Needs O(n) extra space
   Answer: B. At most n-1 swaps, which helps when writes are costly. (Key point: Properties)

## Related in Data Structure and Algorithm

- [Straight selection sort on 33, 90, 45, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aselection-sort-trace-33-90) — Data Structure and Algorithm, chapter 7
- [AVL tree for 10 20 30 50 45 40 8 5 3](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-10-20-30) — Data Structure and Algorithm, chapter 6
- [AVL tree for 10, 20, 30, 35, 50, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-10-20-30-35) — Data Structure and Algorithm, chapter 6
- [Merge sort algorithm and trace](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-algorithm-trace) — Data Structure and Algorithm, chapter 7
- [Efficiency of straight selection sort](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aselection-sort-efficiency) — Data Structure and Algorithm, chapter 7
- [Radix sort on 32, 45, 60, 83, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aradix-sort-32-45-60) — Data Structure and Algorithm, chapter 7

## Related in other subjects

- [Conductor selection, 100 MW 70 km 132 kV](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Aconductor-selection-100mw-70km-132kv) — Transmission and Distribution System Design, chapter 4
- [Arch 100 m: rolling UDL 60 m, section at 30 m](https://www.bctengineer.com/question.md?key=semester_4%2Ftheory_of_structures_i%3Aarch-100m-rolling-udl-60m-25) — Theory of Structures I, chapter 6
- [Conductor selection, 100 MW 80 km, no corona](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Aconductor-selection-100mw-80km-corona) — Transmission and Distribution System Design, chapter 4
- [Microwave link: 90 km, 10 GHz, 40 dB antennas](https://www.bctengineer.com/question.md?key=semester_6%2Fpropagation_and_antenna%3Amicrowave-link-90km-10ghz) — Propagation and Antenna, chapter 5