The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
811 views

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.
asked in Algorithms by Veteran (68.8k points)
edited by | 811 views

3 Answers

+23 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.
answered by Veteran (11.1k points)
selected by

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
+2 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).

answered by Boss (5.2k points)
–1 vote
Ans - 7 swaps
answered by Loyal (4.8k points)
someone has used bubble sort to give answer as 47 swaps. Is it correct? and if yes how?
To be honest for this question particularly we have to use Quick sort three way partitioning algorithm.which i haven't learned. I used program to find the number of swaps.But if you want learn this  three-way partitioning. the best source i found is sir Robert Sedgewick course.

make sure you follow : "The array needs to be sorted using swap operations, elements which are swapped needs to be adjacent only".

Quick sort = adjacent elements sort only? 

It is CSE GATE 2000 Question Number 17
check it out.

 



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,443 questions
39,188 answers
108,808 comments
36,563 users