The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+17 votes

Which one of the following is the tightest upper bound that represents the number of swaps required to sort $n$ numbers using selection sort?

- $O(\log n$)
- $O(n$)
- $O(n \log n$)
- $O(n^{2}$)

+24 votes

Best answer

0

Ok. Thanks Sir... The book from where I read has given wrong algorithm, saying it to be Selection Sort.. As per that algorithm, number of swaps are also O(n^{2}).

0

for(i=0;i<n-1;i++) { min_idx=i; for(j=i+i;j<n;j++) { if(a[j]<a[min_idx]) min_idx=j; } swap(a[i],a[min_idx]); // only 1 swap each iteration for a total of n-1 iterations }

0

@Ayush Upadhyaya In this algorithm , the first loop should be

for(i=0;i<n-2;i++)

as for the lase element we don't need any comparison.

0

@Ayush Upadhyaya typing mistake at j=i+1

**edit** i want to say that it should be i+1 but typed as i+i

0

@Nandkishor3939-$i \lt n-1$ will ensure last value at which loop runs is $n-2$ only.

@Gurdeep Saini-Why j should not be $i+1$ ? :O

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 586
- Exam Queries 572
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,132 questions

53,252 answers

184,792 comments

70,509 users