Test by Bikram | Mock GATE | Test 2 | Question: 17

Question

• A Multinational software vendor needs to choose two sorting algorithm implementations $S1$ and $S2$ to built a software for it's offshore clients.
• $S1$ will be used in situations where item exchanges cost nothing but item comparisons remain expensive. Conversely, $S2$ will be used in situations where item comparisons cost nothing but item exchanges remain expensive.

• Suppose the vendor can only use the insertion, selection, or bubble sorts for these implementations,  and suppose the vendor only cares about average-case asymptotic algorithmic complexity.

Which algorithm should the vendor use for each implementation?

• A.   Bubble sort for $S1$ and insertion sort for $S2$.
• B.   Insertion sort for $S1$ and bubble sort for $S2$.
• C.   Selection sort for $S1$ and insertion sort for $S2$.
• D.   Insertion sort for $S1$ and selection sort for $S2$.

Comments

pls provide explanation for this

---

@bikram sir plz explain little bit here i got confused

---

@rajan

Here we consider only average-case asymptotic algorithmic complexity. So here we have to compare average case running time of these 3 sorting algorithms.

For comparison insertion sort is better and for exchange selection sort .

see my answer below..

---

Selection sort is the best in case of number of swaps. It performs at most one swap per element.

Insertion sort takes $\frac{n^2}{4}$ comparisons in average case.

Answer 1

Question says AVERAGE CASE time complexity only to consider .

Selection sort uses about (N² / 2 ) comparisons and N exchanges on average.

Insertion sort uses about ( N²/4) comparisons and (N² / 8) exchanges on average.

Bubble sort uses about (N² / 2) comparisons and ( N² / 2) exchanges on average.

So if exchanges cost nothing and only comparisons count, then insertion sort way better than the others.

If exchanges count but comparisons cost nothing, then selection sort beats the others  asymptotically.

Hence they need to use Insertion sort for S1 and Selection sort for S2.

Comments

can you provide some reference to this exchanges and comparison

caz in my notes I have something different

---

@Supremo

you can check with Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne .

Answer 2

Selection Sort for (S2) as we know has least number of items exchanges (order of N) ,Exchange happens only once while pushing the maximum towards end in every iteration . So we can use Selection sort where the item exchanges are expensive.

Insertion sort for (S1), is good when we know the comparisions are costly because it just tends to compare only the element at the end of sorted subarray. In the best case as we know it might even lead to O(n) comparisions.

Comments

@Bikram.

I got the comparisons part.

But why are you taking  "shifting" operation in insertion sort as "exchanges"? Shifting is different from exchanging right? So, there are 0 exchanges in insertion sort, right?

---

@Gokhale

This question demans exchanging ..

 I took both same because In most programming languages, creating space to temporarily store a variable is simply using another position on the stack and is essentially free. If your array elements are complex structures and you're unfortunate enough to be using a language where assignment involves copying the entire structure in memory, then shifting will be cheaper than swapping. But in either case, the big-O analysis will be the same; the overhead shows up as coefficients, not as increased asymptotic complexity.

so both shifting and swapping have O(n² )  Average case performance.[1]

shifting is moving all elements by one position.

Swapping is exchanging the elements at two distinct indexes.

Reference:

[1] http://stackoverflow.com/questions/20224900/what-is-the-difference-between-swapping-and-shifting

---

@Bikram. 

I understand that there wont be any difference in average case time complexity. But I would have really appreciated if the sentence was:

insertion sort implemented by swapping

With this you leave no doubt.

For eg. No of multiplexers required in direct mapped cache.

Now, some might use decoder and get less no of multiplexers. Some might get the o/p with more number of multiplexers.

Point is there should be no space for ambiguity.