How many flips does the simplest of pancake sorting techniques require?(a) 3n−3 flips(b) 2n-4 flips(c) 2n-3 flips(d) 3n-2 flipsI got this question in class test.My question is based upon Pancake Sort topic in portion Sorting of Data Structures & Algorithms II

How many flips does the simplest of pancake sorting techniques require

1.	How many flips does the simplest of pancake sorting techniques require?(a) 3n−3 flips(b) 2n-4 flips(c) 2n-3 flips(d) 3n-2 flipsI got this question in class test.My question is based upon Pancake Sort topic in portion Sorting of Data Structures & Algorithms II
Answer» CORRECT answer is (c) 2n-3 flips The best I can explain: The minimum number of flips required to sort any stack of n PANCAKES has been shown to lie between 1.087n and 1.636n. using average of that 1.36n and EXTRACTING that for values of n>1. We have 1.36, 2.72, 4.08 etc. This MATCHES best with 2n-3 which is equal to 1, 3, 5, 7, 9, etc. An upper bound of 2n-3 comes by iteratively using the next largest element in its correct place using two flips.

Discussion

No Comment Found

Related InterviewSolutions

What is the basic principle in Rabin Karp algorithm?(a) Hashing(b) Sorting(c) Augmenting(d) Dynamic ProgrammingPlease answer the question asap those who know Rabin Karp algorithm.
What is the worst case time complexity of tree sort (when implemented with a balanced tree)?(a) O(n)(b) O(n log n)(c) O(n^2)(d) O(log n)
Which of the following is a variant of insertion sort?(a) selection sort(b) shell sort(c) odd-even sort(d) stupid sortPlease answer.
Which of the following non-comparison sort can also be considered as a comparison based sort?(a) counting sort(b) MSD radix sot(c) bucket sort(d) pigeonhole sortPlease answer this question of dsa.
Which of the following is not true about radix sort?(a) Radix sort performs better than quick sort when we have log n bits for every digit(b) Radix sort has better cache performance than quick sort(c) Radix sort has higher values of constant factor in asymptotic notation(d) Radix sort takes more space than quick sortRadix sort people please answer.
Which of the following sorting algorithm is not a constituent of introsort?(a) selection sort(b) quicksort(c) insertion sort(d) heap sortintrosort knowledgeable people please answer.
Shell sort is also known as _____________(a) diminishing decrement sort(b) diminishing increment sort(c) partition exchange sort(d) diminishing insertion sortA very nice question close to me from dsa.
Which of the following is not an advantage of tree sort?(a) it has a low space complexity(b) it has good time complexity for balanced BST(c) it is an online sorting algorithm(d) it is stable sorting algorithmI got this question in an online quiz.Question is taken from Sorting in section Sorting of Data Structures & Algorithms II
The worst case time complexity of tree sort remains unaffected when implemented with an unbalanced tree or a balanced tree.(a) True(b) FalseThe question was posed to me during an interview.This interesting question is from Sorting in section Sorting of Data Structures & Algorithms II
Which of the following version of tree sort will have the highest worst case time complexity?(a) using AVL tree as BST(b) using red black tree as BST(c) using splay tree as BST(d) using ordinary BSTThis question was addressed to me in exam.My question is based upon Sorting in portion Sorting of Data Structures & Algorithms II

How many flips does the simplest of pancake sorting techniques require?(a) 3n−3 flips(b) 2n-4 flips(c) 2n-3 flips(d) 3n-2 flipsI got this question in class test.My question is based upon Pancake Sort topic in portion Sorting of Data Structures & Algorithms II

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment