10 votes 10 votes 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$. Algorithms descriptive isi2011 algorithms sorting + – go_editor asked Jun 3, 2016 go_editor 1.4k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Pritam Dutta commented Nov 5, 2017 reply Follow Share difference between these two? https://gateoverflow.in/505/gate1991_01-vii 1 votes 1 votes sutanay3 commented Jul 31, 2018 reply Follow Share No of comparisons = ceil (log n! ) = ceil (log 24) = 5 4 votes 4 votes vishalshrm539 commented Oct 15, 2018 reply Follow Share Counting sort, zero pairwise comparisions? 0 votes 0 votes Please log in or register to add a comment.
Best answer 11 votes 11 votes It will be merge sort. $a,b,c,d$ $1+1$ comparisons for lowest step $+3$ comparisons for upper one So, total $5$ comparisons Tanushree answered Jun 12, 2016 selected Jun 29, 2018 by junaid ahmad Tanushree comment Share Follow See all 3 Comments See all 3 3 Comments reply meghna commented Jul 16, 2018 reply Follow Share 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(n2) 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(n2) 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. 14 votes 14 votes ashwani kumar sharma commented Aug 7, 2018 reply Follow Share https://gateoverflow.in/505/gate1991_01-vii by this method u will get less comparison than merge sort 0 votes 0 votes mehul vaidya commented Aug 12, 2018 reply Follow Share u get same ansẃer i.e. 5 take car of base of log 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes Requirements : Pair wise sorting algo & min no of comparisons. Ans : Merge sort Pronomita Dey 1 answered Aug 23, 2017 Pronomita Dey 1 comment Share Follow See all 3 Comments See all 3 3 Comments reply ashutoshaay26 commented Aug 26, 2017 reply Follow Share Is it "count of inversion" algorithm ? 0 votes 0 votes Pronomita Dey 1 commented Aug 26, 2017 reply Follow Share yes. http://www.geeksforgeeks.org/counting-inversions/ count of inversions problem can be solved using merge sort. 3 votes 3 votes ashutoshaay26 commented Aug 26, 2017 reply Follow Share Yeah, I did in Stanford algorithm class on coursera, but just confused with twist of the question ! Thanks, Miss. 1 votes 1 votes Please log in or register to add a comment.