0 votes 0 votes Algorithms sorting quick-sort + – kvkumar asked Nov 7, 2017 • retagged Jun 19, 2022 by makhdoom ghaya kvkumar 1.1k views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply prateekdwv commented Nov 7, 2017 i edited by prateekdwv Nov 7, 2017 reply Follow Share Is '$^8C_5$ different arrangements' answer to this question? Could you please confirm. 0 votes 0 votes just_bhavana commented Nov 7, 2017 reply Follow Share shouldn't it be 3!*5! = 720 ? 0 votes 0 votes joshi_nitish commented Nov 7, 2017 reply Follow Share @bhavna, what i think, if a qsn is asking that, in how many ways the initial arrangement is done so that effect of first pass is preserved, then it should be 8! , beacuse 6 is fixed at first position, now no matter how other elements are arranged, the effect of first pass remain intact(i.e elements <60 on left side and >60 on right side)... on the other hand if qsn is asking in how many ways array could look like after first pass of partitioning algo then it should be 5!*3! = 720.. 0 votes 0 votes just_bhavana commented Nov 7, 2017 reply Follow Share @nitish, okay you mean it is asking for input array ? then it should be 8! 0 votes 0 votes joshi_nitish commented Nov 7, 2017 reply Follow Share yes.. 0 votes 0 votes just_bhavana commented Nov 7, 2017 reply Follow Share https://gateoverflow.in/73279/algorithm @nitish, see this, same question I found 0 votes 0 votes just_bhavana commented Nov 7, 2017 reply Follow Share https://stackoverflow.com/questions/34591025/how-many-arrangements-are-possible-for-the-given-input-array-so-that-all-of-them here the answer is given to be $\frac{8!}{5! 3!}$ 0 votes 0 votes joshi_nitish commented Nov 7, 2017 reply Follow Share second qsn ->"stackoverflow" is completely different. it is saying that, what is # of initial arrangment of array that will give exact same output after pass pass of partitioning algo.. for ex: how many initial arrangement will give 1 4 2 5 7 11 8 15 9 // see it is more stricter than what we were computing before, before we were only concern that keys <7 should be on left side and >7 on right side, but now here it is saying that exact same sequence(1 4 2 5 7 11 8 15 9) should occur after first pass// 1 votes 1 votes just_bhavana commented Nov 7, 2017 reply Follow Share yes, got it thanks! 0 votes 0 votes Please log in or register to add a comment.
Best answer 0 votes 0 votes ans 720 kvkumar answered Nov 7, 2017 kvkumar comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Total arrangement 5 possible avadh answered Nov 7, 2017 avadh comment Share Follow See all 0 reply Please log in or register to add a comment.