in Algorithms edited by
10,755 views
42 votes
42 votes

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.
in Algorithms edited by
10.8k views

4 Comments

$\textbf{Just for knowledge – }$

If we remove the constraint of the $\textit{adjacent swap}$, then this problem can be solved in $O(n)$ with $O(1)$ extra space i.e, $\textit{inplace}$.

Here is the code:

class Solution {
public:
    void Sort(vector<int>& a) {
        int i=0,j=a.size()-1,k=i;
        while(k<=j){
            if(a[k]==0) swap(a[i++],a[k++]);
            else if(a[k]==1) k++;
            else if(a[k]==2) swap(a[j--],a[k]);
        }
    }
};

 

0
0

yes we can solve it with count sort or selection sort also,if they didn’t have mentioned about adjacent swapping right,in O(n)  swaps.

0
0

@jatinmittal199510 Just for extra information…. it wouldn't be stable.

0
0
BY SELECTION SORT
0
0

6 Answers

46 votes
46 votes
Best answer
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.
edited by

4 Comments

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 

0
0
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?
0
0
In insertion sort, we $\textbf{shift}$ and then move the key at its appropriate position.
0
0
41 votes
41 votes

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(n2).

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(n2).

4 Comments

0
0
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).
0
0

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

0
0
7 votes
7 votes

$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]$

1 vote
1 vote

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$

Related questions