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.5k
- Engineering Mathematics 6.9k
- Digital Logic 2.7k
- Programming & DS 4.8k
- Algorithms 4.1k
- Theory of Computation 5.2k
- Compiler Design 2k
- Databases 3.9k
- CO & Architecture 3.4k
- Computer Networks 3.9k
- Non GATE 1.4k
- Others 1.5k
- Admissions 516
- Exam Queries 525
- Tier 1 Placement Questions 23
- Job Queries 67
- Projects 18

46,966 questions

51,289 answers

177,259 comments

66,643 users