---
title: "Efficiency of straight selection sort"
subject: "Data Structure and Algorithm"
chapter: 7
key: "semester_4/data_structure_and_algorithm:selection-sort-efficiency"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/selection-sort-efficiency
site: BCT Engineering
---

# Efficiency of straight selection sort

Data Structure and Algorithm · Chapter 7: Sorting

- Asked in: 2068 Bhadra, 2 marks
- Video: [L-3.8: Selection Sort | Time Complexity(Best, Avg & Worst) Analysis | Stable or Not | Inplace or Not](https://www.youtube.com/watch?v=Lrd1QaKyok4) — Gate Smashers
- 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-efficiency
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7

## Question

Calculate efficiency of straight selection sort.

## Short answer

Straight selection sort performs (n^2 - n)/2 comparisons, always O(n^2). Best, average, and worst case are O(n^2), with O(1) extra space.

## Answer

Straight selection sort finds the smallest element of the unsorted part in each pass and swaps it into its place.

For *n* elements, pass 1 makes n−1 comparisons, pass 2 makes n−2, ..., and the last pass makes 1:

(n−1) + (n−2) + ... + 1 = n(n−1)/2 = (n² − n)/2

So the number of comparisons is about n²/2 in every case (best, average and worst), because the whole unsorted part is always scanned. Swaps are at most n−1.

**Answer: time complexity is O(n²) in all cases; extra space is O(1).**

## Check yourself

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

1. How many comparisons does pass 1 make for n elements?
   A. n
   B. n - 1
   C. n/2
   D. 1
   Answer: B. The first pass scans n-1 remaining elements. (Key point: Comparison count)

2. What is the total number of comparisons?
   A. n(n-1)/2
   B. n log n
   C. n
   D. 2n
   Answer: A. (n-1)+(n-2)+...+1 = n(n-1)/2. (Key point: Total)

3. Why is selection sort O(n^2) even in the best case?
   A. It uses recursion
   B. It always scans the whole unsorted part
   C. It swaps every element
   D. It needs extra memory
   Answer: B. The scan does not depend on input order. (Key point: All cases)

## 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
- [Selection sort with trace](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aselection-sort-explain-trace) — Data Structure and Algorithm, chapter 7
- [Efficiency of quick sort](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aquick-sort-efficiency) — Data Structure and Algorithm, chapter 7, asked 2×

## Related in other subjects

- [Ampere's law, field of straight wire](https://www.bctengineer.com/question.md?key=semester_1%2Fengineering_physics%3Aampere-law-straight-wire-field) — Engineering Physics, chapter 8, asked 5×
- [Camber elevations, straight and parabolic](https://www.bctengineer.com/question.md?key=semester_6%2Ftransportation_engineering_i%3An-65c-camber-320) — Transportation Engineering I, chapter 3
- [Max height of straight draft tube (Francis)](https://www.bctengineer.com/question.md?key=semester_7%2Fhydropower_engineering%3Afrancis-draft-tube-max-height-11760kw) — Hydropower Engineering, chapter 7