GATE CSE 2000 | Question: 17

Question

An array contains four occurrences of $0$, five occurrences of $1$, and three occurrences of $2$ in any order. The array is to be sorted using swap operations (elements that are swapped need to be adjacent).

1.  What is the minimum number of swaps needed to sort such an array in the worst case?
2.  Give an ordering of  elements in the above array so that the minimum number of swaps needed to sort the array is maximum.

Comments

---

Adding context to @jatinmittal199510

The Dutch National Flag (DNF) algorithm sorts an array of {0,1,2} in O(n) time, O(1) space, using three pointers:

 

i → boundary for 0s (start)

j → boundary for 2s (end)

k → current index

Rules:

If a[k] == 0 → swap with a[i], move i, k.

If a[k] == 1 → just move k.

If a[k] == 2 → swap with a[j], move j.

Works in one pass with normal swaps.

 

If restricted to adjacent swaps only, worst  case becomes O(n²).

---

For insertion sort :

Number of shifts = Number of inversions

For each shift, we perform 1 assignment operation

 

For bubble sort :

Number of swaps = Number of inversions

For each swap, we perform 3 assignment operations

(Many students here have confusion between shifting and swapping)

Answer 1

Since swaps are needed to be of adjacent elements only, the algorithm is actually Bubble sort.

In bubble sort, all smaller elements to right of an element are required to be swapped. So, if have ordering

$[2,2,2,1,1,1,1,1,0,0,0,0]$, then we need total $47$ swaps, and this will be the worst case.

So, it answers actually both parts.

Comments

we have to apply "Bubble sort" because as per question element that is swapped need to be adjacent.

array [ 2,2,2,1,1,1,1,1,0,0,0,0]   total 12 elements, as we know that bubble is stable in nature so repeated element order will not change.

pass 1> swap (9) ,pass 2 >sawp (9) ,pass 3>sawp (9)

pass 4> swap(4),pass 5>swap(4),pass 6>swap(4),pass 7>swap(4),pass 8>swap(4)

pass 9> sawp(0),pass10>swap(0),pass 11>swap(0)   

total swap = 47 

---

yes @ Prateek

Thanks :)

---

It can also be done with insertion sort.

pass 1 - swap(3), pass2- swap(3),pass3-swap(3), pass4-swap(3),pass5-swap(3), pass6-swap(8) ,pass7-swap(8), pass9-swap(8) ,pass10-swap(8)

---

insertion sort doesn't always give *adjacent swaps*

@srestha

---

@ Prateek kumar

I could not understand how u have counted number of swaps.. Can u please explain in more detail

---

insertion sort also gives adjacent swaps???

---

The total no. of inversions present in the array = 47 , so can we say that no. of inversions = total no. of swaps required in case of bubble sort? I know for insertion sort its true.

---

insertion sort also has adjacent swaps always????

if not then please explain???

---

According to me adjacent swap means to put an element to its correct position you always have to swap that element with its adjacent element. In bubble sort in every iteration there is one element which gets sorted and to sort it in its correct position we swap it with it's adjacent element. Where in insertion sort we don't actually swap that element with everyone ,but we swap all greater elements to the right side and then we put original element on its right place.

---

if in the question they ask for no. of the pass then answer will be 9 or 11?

---

Why can't Insertion Sort be used here, bcoz it also swaps adjacent elements only, at least thats what I know? Can anybody give an example of insertion sort not using adjacent swaps.

---

@ Swapnil Naik do you mean to say that in case of insertion sort ,we take an element(suppose we call it key) and compare with not only with its adjacent one rather with all those present to the left of it and which are greater than it ,they are shifted to right and not swapped and then we find the correct position of key we place it 

but in bubble sort ,adjacent swaps takes place ,am i correct or wrong?

 

---

@codingo1234 what I think is in Insertion sort when we traverse to the left of the key in the list, we swap each time we find an element greater than the key as we maintain a single pointer to traverse left and sorting happens in place. Shifting right would replace the key and key would be lost and to preserve it we will need extra space to store key which is not the way insertion sort works.

---

And that extra space would be constant ,so how does it violate inplace property of insertion sort,?

---

My bad! Space complexity would remain constant. Thanks a lot. Got it, In insertion sort key is not swapped but placed at the correct position, hence bubble sort. Thanks @codingo1234 

---

If its asked maximum numbers of swap in the best case and adjacent swap is not necessary then can we use selection sort with 9 Swaps?

---

In insertion sort, we $\textbf{shift}$ and then move the key at its appropriate position.

---

They aren't talking about any named algo in the question. We can take the worst case and see that it'd optimally require 47 swaps to put all elements in their correct place if only adjacent swaps are allowed. In fact, such mechanism of swap can be implemented by any other algorithm too, for example, insertion sort.

---

we can count number of inversions here which will come out to be 47.

Answer 2

Reference : https://discuss.codechef.com/questions/64884/wprob-editorial

The number of swaps an algorithm performs is equal to the number of inversions present in the input array.

The question is somewhat directly taken from the exercise of coremen

I'll solve this later first question :P

(a) Minimum number of swaps in worst case

   This would occur when all the elements in the array would be present in descending order.

So, Number of inversions for 2=(9*3)=27

     Number of inversions for 1 = (4*5)=20

     0 would have no inversions.

So, total inversions=47

2

2

2

1

1

1

1

1

0

0

0

0

(b) The above configuration of the array will give the maximum number of swaps to sort the array.

---

Now coming to coremen exercise

We know insertion sort works by placing the unsorted element in it's correct position within sorted elements.

The running time of insertion sort depends on the number of inversions present in the array.

Assuming array has n distinct elements.

Case A : Array is sorted in ascending order

In this case, number of Inversions would be 0, so 0 swaps, however, a total of n-1 comparisons will still be made.

So, best case complexity comes out to be O(n).

Case B: Array is sorted in descending order

Total inversions come out to be 

(n-1)+(n-2)+(n-3)+.......1 = $\frac{n(n-1)}{2}$  =  O(n²).

This will be exactly equal to the number of swaps and comparisons insertion sort will perform in this case.

So, worst case complexity comes out to be O(n²).

Comments

https://gateoverflow.in/975

---

if time is not an issue .

then selection sort is the best I think.because the number of swaps in selection sort is always theta(n).

---

@Ayush Upadhyaya, I think there is no swap in Insertion sort. There is only left or right shift depending on sorting. Question asks for adjacent swaps which take place in Bubble sort.

Answer 3

$a)$ Bubble sort

Source : https://en.wikipedia.org/wiki/Bubble_sort

 

$[2,2,\fbox{2},\underbrace{1,1,1,1,1,0,0,0,0}]$

$\downarrow$ After $9$ swaps

$[2,2,1,1,1,1,1,0,0,0,0,2]$

$\downarrow$ Similarly After $18$ swaps

$[1,1,1,1,\fbox{1},\underbrace{0,0,0,0},2,2,2]$

$\downarrow$ After $4$ swaps

$[1,1,1,1,0,0,0,0,1,2,2,2]$

$\downarrow$ Similarly After $16$ swaps

$[0,0,0,0,1,1,1,1,1,2,2,2]$

$9+9+9+4+4+4+4+4=47$ Swaps

---

$b)$

$[2,2,2,1,1,1,1,1,0,0,0,0]$

Comments

Best Answer.

Answer 4

elements that are swapped need to be adjacent

This screams bubble sort. The worst case would be when the input is sorted in descending order.

$\left \{ 2,2,2,1,1,1,1,1,0,0,0,0 \right \}$

 

No of swaps = Number of inversions.

For all three of the 2's, all others are inversions => $15+12$

For all five of the 1's => $20$ (count just with 0, because 2 already covered)

For all the 0's, inversions are already covered.

Total inversions = $20+15+12=47$

Hence, swaps required = $47$

Answer 5

finding the Minimum Inversion can be done we intersect the minimum line 

Image Preview below this link

https://gateoverflow.in/?qa=blob&qa_blobid=15406243736014909230

Answer 6

Notes : 

 

•  If a problem mentions minimizing swaps, the answer is likely Selection Sort .
•  If a problem mentions nearly sorted data or small number of inversions , the answer is Insertion Sort.
•  If the complexity must be $O(n^2)$ regardless of the input, you are dealing with Selection Sort

 

Feature	Bubble Sort	Insertion Sort	Selection Sort
Logic	Adjacent Swaps	Shifting for Key	Finding Global Min
Best Case Time	$O(n)$	$O(n)$	$O(n^2)$
Worst Case Time	$O(n^2)$	$O(n^2)$	$O(n^2)$
Max Swaps	$n(n-1)/2$	$0$ (uses shifts)	$n - 1$
Adaptive?	Yes (with flag)	Yes	No
Stable?	Yes	Yes	No