2 votes 2 votes Is quick sort in-place algorithm? Algorithms algorithms quick-sort sorting + – vaishali jhalani asked Nov 7, 2016 vaishali jhalani 1.0k views answer comment Share Follow See 1 comment See all 1 1 comment reply Pavan Kumar Munnam commented Nov 7, 2016 reply Follow Share 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 votes 0 votes Please log in or register to add a comment.
2 votes 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 See all 8 8 Comments reply vaishali jhalani commented Nov 7, 2016 reply Follow Share What about extra space for stack O(logn)? 1 votes 1 votes Habibkhan commented Nov 7, 2016 reply Follow Share 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 votes 1 votes thor commented Nov 23, 2016 reply Follow Share So, If question is what is space complexity of Quick-sort? what should be answer O(1) or O(logn) 0 votes 0 votes Habibkhan commented Nov 23, 2016 reply Follow Share O(logn) in the worst case using tail call optimisation.. 0 votes 0 votes vaishali jhalani commented Nov 23, 2016 reply Follow Share 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 votes 0 votes Habibkhan commented Nov 23, 2016 reply Follow Share Nope O(logn) else worst case complexity = O(n).. 0 votes 0 votes vaishali jhalani commented Dec 11, 2016 reply Follow Share 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 votes 0 votes Himanshu Kumar Gupta commented Aug 17, 2020 reply Follow Share 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 votes 0 votes Please log in or register to add a comment.