The Gateway to Computer Science Excellence
+1 vote
232 views
Is quick sort in-place algorithm?
in Algorithms by Active (4.7k points) | 232 views
0
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

1 Answer

+2 votes
Yes quicksort is an inplace algorithm as it does not require auxiliary array for sorting purpose like in the case of mergesort..
by Veteran (102k points)
+1
What about extra space for stack O(logn)?
+1
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..
0
So, If question is what is space complexity of Quick-sort? what should be answer O(1) or O(logn)
0
O(logn) in the worst case using tail call optimisation..
0
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
Nope O(logn) else worst case complexity = O(n)..
0

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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,439 comments
100,708 users