The Gateway to Computer Science Excellence
+18 votes

What is the number of swaps required to sort $n$ elements using selection sort, in the worst case?

  1. $\Theta(n)$

  2. $\Theta(n \log  n)$

  3. $\Theta(n^2)$

  4. $\Theta(n^2 \log  n)$

in Algorithms by Veteran (52.2k points)
edited by | 1.9k views

Selection sort:


2 Answers

+23 votes
Best answer

The answer is A.

we have $1$ swap in each loop and hence $n$ swaps at max for $1$ to $n$. Therefore the worst case number of swaps is $\Theta(n)$

by Boss (19.9k points)
edited by
Best case: $0$ swaps. for eg $1,2,3,4,5,6$

Worst case: $n-1$ swaps for eg $6,5,2,1,4,3$

@reena ma'am, it depends on implementation, but in its basic form, even in best case selection sort requires 1 swap in each pass.

A minor correction, in worst case , selection sort does n-1 swaps.
+1 vote

option a

by Boss (36.7k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,371 users