1 votes 1 votes What is the number of Comparison to sort below arrays using quick sort using first element as pivot ? Please show steps . A1=4,1,5,3,2 A2=1,2,3,4,5 Algorithms quick-sort + – hem chandra joshi asked Dec 2, 2017 hem chandra joshi 3.7k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Shubhanshu commented Dec 3, 2017 i edited by Shubhanshu Dec 3, 2017 reply Follow Share For 1st Number of Comparison is 6. For 2nd Number Comparison is 10. 0 votes 0 votes hem chandra joshi commented Dec 3, 2017 reply Follow Share for both? explain step? 0 votes 0 votes Shubhanshu commented Dec 3, 2017 reply Follow Share For 1st one A1 = 4 1 5 3 2 After partition:- 2 1 3 4 5 Two subarrays are still to be sort those are A = 2 1 3 and B = 5 but till here num of comparisions are 4 Sorting A:- A = 2 1 3 After partition:- 1 2 3 Two subarrays are still to be sort those are C = 1 and D = 3 but till here num of comp = 2 Sorting B, C and D will take 0 comparision because they are single elements. Hence total number of Comparisions are 4 + 2 = 6 For 2nd one:- A2 = 1 2 3 4 5 After partition only one array to be sort which is B = 2 3 4 5 till here num of comp = 4 sorting B = 2 3 4 5:- After partition only one array to be sort which is C = 3 4 5 till here num of comp = 3 sorting C = 3 4 5:- After partition only one array to be sort which is D = 4 5 till here num of comp = 2 sorting D = 4 5:- After partition only one array to be sort which is E = 5 till here num of comp = 1 sorting E = 5 will take 0 comparisions because it is single element array so num of comp = 0 Total number of comparision is = 4 + 3 + 2 + 1 + 0 = 10. 3 votes 3 votes nikhil_cs commented Jan 25, 2018 reply Follow Share @shubhanshu,, At every step number of comparison will be size of current array minus one?? 0 votes 0 votes Shubhanshu commented Jan 25, 2018 reply Follow Share Yes. 0 votes 0 votes Himanshu Kumar Gupta commented Aug 17, 2020 reply Follow Share @shubhanshu can you give reference to prove your point because i am unable to get it 0 votes 0 votes Please log in or register to add a comment.