ISI2011-PCB-A-2a

Question

Give a strategy to sort four given distinct integers $a, b, c, d$ in increasing order that minimizes the number of pairwise comparisons needed to sort any permutation of $a, b, c, d$.

Comments

difference between these two? https://gateoverflow.in/505/gate1991_01-vii

---

No of comparisons = ceil (log n! )

                                 =  ceil (log 24)

                                   = 5

---

Counting sort, zero pairwise comparisions?

Answer 1

It will be merge sort.

$a,b,c,d$

$1+1$ comparisons for lowest step

$+3$ comparisons for upper one

So, total $5$ comparisons

 

Comments

We can also decide the strategy by the line "to sort any permutation of a,b,c,d".

No to quick sort: Since any involves increasing/ decreasing sequence also, So quick sort fails ,as it includes its worst case of O(n²) comparisons when array is sorted, So eliminate Quick Sort.

No to Insertion sort: We can eliminate Insertion sort also since Insertion sort gives best case only when array is sorted or almost sorted.Otherwise it gives O(n²) comparisons. So remove this choice.

No to heap sort: Given an array with a normal distribution, Merge sort and Heap sort will both run in O(n log(n)). But Merge sort will execute faster than heap sort and also it is stable. To put it simply, partitioning is faster than maintaining the heap

so we are left with Merge sort, which passes the test here, and that too in O(nlogn) for all possible permutations.

---

 https://gateoverflow.in/505/gate1991_01-vii

by this method u will get less comparison than merge sort

---

u get same ansẃer i.e. 5 take car of base of log

Answer 2

Requirements :  Pair wise sorting algo & min no of comparisons.
Ans : Merge sort

Comments

Is it "count of inversion" algorithm ?

---

yes. http://www.geeksforgeeks.org/counting-inversions/

count of inversions problem can be solved using merge sort.

---

Yeah, I did in Stanford algorithm class on coursera, but just confused with twist of the question !

Thanks, Miss.