GATE 2013 CS (CS1) – Question 16

Algorithms · Searching, Sorting and Hashing · 1 mark · Multiple choice

What is the tightest upper bound on swaps used by selection sort on n numbers?

$O(\log n)$
$O(n)$
$O(n\log n)$
$O(n^2)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $O(n)$

Explanation

Selection sort selects a minimum for each successive position and performs at most one swap per pass. There are n−1 passes, giving O(n) swaps, B, despite its Θ(n²) comparisons.

More Searching, Sorting and Hashing questions

GATE 2010 CS (CS1) Q62 – A ten-slot hash table uses h(k)=k mod 10 and linear probing. Its occupied slots are 2:42,…
GATE 2010 CS (CS1) Q63 – A ten-slot hash table uses h(k)=k mod 10 and linear probing. Its occupied slots are 2:42,…
GATE 2015 CS (CS2) Q50 – Which integer hash function distributes keys i=0,…,2020 most uniformly over buckets 0,…,9?
GATE 2015 CS (CS3) Q22 – A hash table with 25 slots stores 2000 elements. Find its load factor α.
GATE 2021 CS (CS2) Q18 – Find the worst-case number of arithmetic operations in recursive binary search on a sorted…
GATE 2026 CS (CS1) Q24 – Consider a hash table P[0, 1, , 10] that is initially empty. The hash table is maintained…

All Searching, Sorting and Hashing questions →