2 2 votes Is quick sort in-place algorithm? Algorithms algorithms quick-sort sorting + – vaishali jhalani 2.1k views answer comment Share Follow Print See 1 comment 1 1 comment reply Pavan Kumar Munnam commented Nov 7, 2016 reply Follow flag Yes, quick sort is in place algorithm . . . As quick sort doesn't require new space it does the sorting in that array it self . . . Where as merge sort is not as it takes extra spaces for all the sub problems 0 0 replyShare Please log in or register to add a comment.
2 2 votes Yes quicksort is an inplace algorithm as it does not require auxiliary array for sorting purpose like in the case of mergesort.. Habibkhan answered Nov 7, 2016 Habibkhan comment Share Follow See all 8 Comments 8 8 Comments reply vaishali jhalani commented Nov 7, 2016 reply Follow flag What about extra space for stack O(logn)? 1 1 replyShare Habibkhan commented Nov 7, 2016 reply Follow flag Stack space is also taken by mergesort..That has to be taken for function calls ..So we are not considering that..We are only considering auxilliary space required for data.. 1 1 replyShare thor commented Nov 23, 2016 reply Follow flag So, If question is what is space complexity of Quick-sort? what should be answer O(1) or O(logn) 0 0 replyShare Habibkhan commented Nov 23, 2016 reply Follow flag O(logn) in the worst case using tail call optimisation.. 0 0 replyShare vaishali jhalani commented Nov 23, 2016 reply Follow flag I think it will be depend upon question... We have to write O(logn) in gneral case... But with comparison to other algo's like merge sort..as habib said we will consider O(1) 0 0 replyShare Habibkhan commented Nov 23, 2016 reply Follow flag Nope O(logn) else worst case complexity = O(n).. 0 0 replyShare vaishali jhalani commented Dec 11, 2016 reply Follow flag It all depends on the definition of "in-place" algorithm. If you define "in-place" as requiring a constant amount of memory, then quicksort is not "in-place" as it requires log(N) memory for the recursion. If you define "in-place" as more human-friendly "does not move the data outside the input structure", then quicksort is again not "in-place". http://stackoverflow.com/questions/22028117/is-quicksort-in-place-or-not 0 0 replyShare Himanshu Kumar Gupta commented Aug 17, 2020 reply Follow flag In-place has more than one definitions. One strict definition is. An in-place algorithm is an algorithm that does not need an extra space and produces an output in the same memory that contains the data by transforming the input ‘in-place’. However, a small constant extra space used for variables is allowed A more broad definition is, In-place means that the algorithm does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation. Usually, this space is O(log n), though sometimes anything in o(n) (Smaller than linear) is allowed [Source : Wikipedia] There are many sorting algorithms that are using in-place approach. Some of them are insertion sort,bubble sort,heap sort,quicksort,shell sort. 0 0 replyShare Please log in or register to add a comment.
