The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+16 votes

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

- Quick sort
- Insertion sort
- Selection sort
- Heap sort

Shouldn't this be Insertion Sort?

As in Insertion Sort, we "technically" don't swap, but shift elements to place the element under consideration in proper place

As in Insertion Sort, we "technically" don't swap, but shift elements to place the element under consideration in proper place

In insertion sort (implementation like Cormen) we should use the term Movement or Shifting.

Number of swapping: We cant say it is zero. Swappings are done indirectly. (Just check initially 2nd element is swapped with first, other swaps are done indirectly)

It should not be asked actually. Because we do not swap anything directly.

Why it is asked in GATE again in ISRO?

I think if they are asking about swapping in insertion sort, then they are following that approach of insertion sort where swapping is done.

See this https://cs.stackexchange.com/questions/21455/how-can-i-quantify-the-number-of-swaps-required-for-insertion-sort

This approach where swapping is done is more popular as insertion sort.. See wiki.

In wiki, they also have written insertion sort with approach2(Cormen) & recursive one. They also have written 2nd approach is little bit faster. But they have analysed the complexity based on 1st approach..

Number of swapping: We cant say it is zero. Swappings are done indirectly. (Just check initially 2nd element is swapped with first, other swaps are done indirectly)

It should not be asked actually. Because we do not swap anything directly.

Why it is asked in GATE again in ISRO?

I think if they are asking about swapping in insertion sort, then they are following that approach of insertion sort where swapping is done.

See this https://cs.stackexchange.com/questions/21455/how-can-i-quantify-the-number-of-swaps-required-for-insertion-sort

This approach where swapping is done is more popular as insertion sort.. See wiki.

In wiki, they also have written insertion sort with approach2(Cormen) & recursive one. They also have written 2nd approach is little bit faster. But they have analysed the complexity based on 1st approach..

In case of Insertion sort ,

best case is O(n) swaps , when the array is already sorted .

worst case O(n^{2}) swaps

source:wikipedia

@Bikram sir.. as per the 1st approach where swapping is done.. Best case O(n) swap.. Worst case O(n sq) swap.

As per 2nd approach (like Cormen).. best case 0 movements.. Worst case n(n-1)/2 movements.. :)

As per 2nd approach (like Cormen).. best case 0 movements.. Worst case n(n-1)/2 movements.. :)

Swaps in approach 1 & movements in approach 2 in worst case are O(n sq).. but in best case swaps for approach 1 is O(n) where as no movements are done in approach 2. By the way key replaces the number with itself.. But it is not movement I guess..

+19 votes

Best answer

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 )

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 )

Please compare number of swaps in selection sort with other sorting techniques given in above question.

Number of swaps : Worst case scenario

- Quick sort = O(n
^{2}) - Insertion sort = О(
*n*^{2}) - Selection sort = O(n)
- Heap sort = O(n logn)

@Ahwan

In case of selection sort , number of swaps require :

**Best case**: No swaps required as all elements are properly arranged

**Worst case**: n-1 swaps required

Reference:

another source :

While selection sort is preferable to insertion sort in terms of number of writes

(Θ(

n) swaps versus Ο(n^{2}) swaps),

That means selection sort has O(n) swaps while insertion sort have O(n^{2}) swaps in worst case.

Reference :

https://en.wikipedia.org/wiki/Selection_sort#Comparison_to_other_sorting_algorithms

@bikram sir in selection sort, in best case also the number of swaps are O(n). In best case 1st smallest element will be A[1] itself and if we don't do any modification in the standard algorithm definition given in cormen then A[1] will be swapped with itself. Hence in each iteration element will be swapped with itself.

@vineet

In Best case , number of swaps are O(n) or 0 swaps , it really depends on the implementation .

And swapping with itself at first position only count as 0 swaps , as all elements are properly arranged .

What i read is in Best case number of swaps is 0 but it depends how selection sort is done..

for this gate question , no doubt answer is selection sort ..

You may read this answer , to get some idea https://stackoverflow.com/questions/26688765/what-are-the-number-of-swaps-required-in-selection-sort-for-each-case

yes sir it depends on implementation but, if we don't modify i.e if we write this check-> if(min!=j) then swap(A[min],A[j]) then there will be no swaps in best case. but if don't check and directly swap then in best also there will be O(n) swaps. But what i think is that algorithm without check should be considered as standard algorithm because in cormen it is simply mentioned "find first smallest element and swap it with A[1]......." now if A[1] itself is first smallest then also there should be swap even though it is not necessary.

partition (arr[], low, high) { // pivot (Element to be placed at right position) pivot = arr[high]; i = (low - 1) // Index of smaller elementfor (j = low; j <= high- 1; j++)// no. of iterations=high-1-low+1{ // If current element is smaller than or // equal to pivot if (arr[j] <= pivot) { i++; // increment index of smaller elementswap arr[i] and arr[j]} }swap arr[i + 1] and arr[high]) // +1 swapreturn (i + 1) }

To understand my doubt please refer to the code above.

In the 1st level high=n and low=1. For the worst case of swapping, for each iteration there should be swapping. Hence total no. of swappings would be high-1-low+1=n-1-1+0=n-2 and outside the loop there is another swapping. Total swapping would be = n-1 in the 1st level. No. of swaps=O(n).

At 2nd level, if the pivot divides the array into equal halves then no. of swapping in this way is (low=1,high=(n/2)-1) so total swaps= (n/2)-1-1+1+1=n/2 and as there is another array set where low=n/2+1 and high=n so swaps=n/2 and hence total swaps=n.

If pivot element is placed at the end (for sorted array) then, low=1, high=n-1 so swaps= high-1-low+1+1=(n-1)-1-1+1+1=n-1.

We can assume that at each level the no. of swaps is O(n).

No. of levels= logn.

Total no. of swaps = nlogn.

How will it be n^2 @Bikram Sir ?

+5 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

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

+3 votes

**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.

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,231 answers

114,269 comments

38,800 users