25,187 views
39 votes
39 votes

Which one of the following in place sorting algorithms needs the minimum number of swaps?

  1. Quick sort
  2. Insertion sort
  3. Selection sort
  4. Heap sort

4 Answers

Best answer
33 votes
33 votes

Correct Option: C - Selection sort.

Because in selection the maximum swaps which can take place are $O(n)$

Because we pick up an element an find the minimum (in case of forward sorting) from the next index till the end of array and than perform the swap

Hence, $O(n)$ whereas in all other algos the swaps are greater ( considering Worst-Case scenario )

edited by
9 votes
9 votes

Let's try to analyse the number of swaps in each of the given sorting algorithms. Quick sort – Worst Case input for maximum number of swaps will be already sorted array in decreasing order. Recurrence for Total number of swaps in this case : T(n) = T(n-1) + O(n) // O(n) swaps will occur in alternate calls to partition algorithm. = O(n2) Insertion sort - Worst Case input for maximum number of swaps will be already sorted array in ascending order.When a new element is inserted into an already sorted array of k size, it can lead to k swaps (in case it is the smallest of all) in worst case. For n-1 iterations of insertion sort, total swaps will be O(n2). Selection sort – There is no Worst case input for selection sort. Since it searches for the index of kth minimum element in kth iteration and then in one swap, it places that element into its orrect position. For n-1 iterations of selection sort, it can have O(n) swaps. Heap sort – Total number of swaps in Heap sort can be O(nlogn) as after performing Build-heap which may require O(n) swaps, it performs n-1 extract-min operations resulting into O(nlogn) swaps.

4 votes
4 votes
Number of swaps
Quick sort = $\Theta (nlogn)$
Insertion sort =  $\Theta (n^{2})$
Selction sort = no swaps required since we are shifting elements in the array and not swapping
Heap sort =  $\Theta (nlogn)$

Option C
0 votes
0 votes

Number of swaps : Worst case scenario 

  1. Quick sort = O(n2)
  2. Insertion sort = О(n2) 
  3. Selection sort = O(n)
  4. Heap sort = O(n logn) 
Answer:

Related questions

44 votes
44 votes
4 answers
1
Rucha Shelke asked Sep 26, 2014
53,248 views
The median of $n$ elements can be found in $O(n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?$\T...
59 votes
59 votes
7 answers
2
Rucha Shelke asked Sep 16, 2014
31,357 views
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:QueueStackHeapB-Tree
15 votes
15 votes
2 answers
3
33 votes
33 votes
7 answers
4