<blockquote>
  <p><strong>Possible Duplicate:</strong><br>
  <a href="https://cstheory.stackexchange.com/questions/10542/when-are-two-algorithms-said-to-be-similar">When are two algorithms said to be &ldquo;similar&rdquo;?</a>  </p>
</blockquote>



<p>Generic Overview of promblem:<br>
I read somewhere once that a quicksort could be done without recursion in O(1) space overhead.   I thought about it for a while, and then coded a version of quicksort that uses O(1)-space overhead (eg: in-place).  However, since it lacks a lot of the metainformation that quicksort normally has available (beginning and ending of each chunk to recurse down), I had to add a pre-step to "format" the data a specific way so that the rest of the quicksort can correctly determine where each chunk begins and ends.  When discussing this algorithm in StackOverflow chat, R.Martinho speculated that this is no longer a quicksort due to the requirement of the prestep.</p>

<p>Overview of Algorithm:<br>
The general idea is that for each chunk of data, the algorithm picks a pivot P from the chunk (the first in my case), and partitions the data on P into two chunks: data less than P and data greater than P.  It then puts the data in the order of [P][less than P][Greater than P]. (So that it can determine where the partitions begin and end without metadata.)  On the next iteration it can scan until it finds the first two elements out of order, which will be P and one element less than P, and scan until it finds an element greater than P.  It then moves P to the end of the chunk, and performs the algorithm on the chunk of data less than P.  Other than the temporary relocation of P, this is basically how quicksort works.</p>

<p>Deviation of Algorithm from Quicksort:<br>
Since the algorithm needs the data to be in a series of "chunks" of [partition][data between this partition and the previous partition], we have to format the data down the right side until we find the maximum element to get it into this series of chunks, before the rest of the algorithm can run.</p>

<p>This algorithm is quite strange, and I am terrible at explanations, but as proof of concept, here's the a link to my C++ code with a naive quicksort, my inplace quicksort, and stdsort: <a href="http://ideone.com/4iCSo" rel="nofollow noreferrer">http://ideone.com/4iCSo</a>  (I acknowledge there's still a lot of optimizing that could be done, and that this algorithm is so slow it is almost completely useless in general)  The meat of the question is: <strong>is this algorithm still a quicksort</strong>?</p>

<p>I'm not clear on the scope of this site, this question might be better suited to <a href="https://cs.stackexchange.com/">https://cs.stackexchange.com/</a> or <a href="https://stackoverflow.com/">https://stackoverflow.com/</a>.</p>

CC BY-SA 3.0
2012-05-09T17:41:04.787Z
It wasn't until afterwords that I realized a 64bit quicksort that only recurses on the small side and iterates the large partition will always use less than ~1260 bytes, making it O(1) space overhead in practice if not theory.
Mooing Duck
CC BY-SA 3.0
2012-05-09T19:08:56.397Z
Why do you care?  If it's a good algorithm, use it.  If it's not, don't.  Why does it matter what it's called?
Jeffε
CC BY-SA 3.0
2012-05-09T20:08:24.560Z
@JɛﬀE: it's not a good algorithm, there's faster alternatives even for low stack usage scenarios.  The reason for the question was [Wikipedia](http://en.wikipedia.org/wiki/Quicksort#Space_complexity) says that quicksort has a lower bound of `O(log(N))` extra space, which I believe I have proven to be incorrect.  But it hinges on whether or not this algorithm is a quicksort implementation or not.
Mooing Duck
CC BY-SA 3.0
2012-05-09T22:59:42.290Z
I do not see any claim about lower bound in the section of the Wikipedia article you linked to.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-09T23:24:27.343Z
"Worst case space complexity O(n) auxiliary (naive)
O(log n) auxiliary" "the entire sort can be done with only O(log n) additional space" "a more complex version which uses an in-place partition algorithm and can achieve the complete sort using O(log n) space..." "To make sure at most O(log N) space is used..." "The in-place version of quicksort has a space complexity of O(log n)" "...requiring at most O(log n) space" "...it uses O(log n) space" "...it would need at least O(n log n) bits of space." "...not-in-place, version of quicksort uses O(n) space..." "...logN additional space..."
Mooing Duck
CC BY-SA 3.0
2012-05-10T00:39:40.127Z
@MooingDuck Tsuyoshi's point is that all the references you list describe an *upper bound* of log n for space.
Suresh Venkat
CC BY-SA 3.0
2012-05-10T02:28:43.260Z
@SureshVenkat: ....oh.  So it is.  Thanks for the clarification!  Either way: Is this a quicksort?
Mooing Duck
CC BY-SA 3.0
2012-05-10T03:59:45.783Z
See [When are two algorithms said to be “similar”?](http://cstheory.stackexchange.com/questions/10542/when-are-two-algorithms-said-to-be-similar).
Kaveh
CC BY-SA 3.0
2012-05-10T15:27:05.310Z
There's no central authority that decides whether an algorithm qualifies as a "quicksort"; although your question is interesting, I don't think it is really answerable.
Peter Shor 
CC BY-SA 3.0
2012-05-10T15:58:17.503Z
@Kaveh: That's perfect actually.  We should probably close this as a duplicate of that.
Mooing Duck
CC BY-SA 3.0
2012-05-10T19:03:05.400Z
@PeterShor there is no central authority *as far as you know*....(insert evil laugh)
Suresh Venkat
<ds.algorithms><sorting>
How much variation is allowed before an algorithm is no longer a quicksort?
Mooing Duck
# How much variation is allowed before an algorithm is no longer a quicksort?

(Asked by: username_0 on 2012-05-09)

> **Possible Duplicate:**  
> [When are two algorithms said to be “similar”?](https://cstheory.stackexchange.com/questions/10542/when-are-two-algorithms-said-to-be-similar)

Generic Overview of promblem:  
I read somewhere once that a quicksort could be done without recursion in O(1) space overhead. I thought about it for a while, and then coded a version of quicksort that uses O(1)-space overhead (eg: in-place). However, since it lacks a lot of the metainformation that quicksort normally has available (beginning and ending of each chunk to recurse down), I had to add a pre-step to "format" the data a specific way so that the rest of the quicksort can correctly determine where each chunk begins and ends. When discussing this algorithm in StackOverflow chat, R.Martinho speculated that this is no longer a quicksort due to the requirement of the prestep.

Overview of Algorithm:  
The general idea is that for each chunk of data, the algorithm picks a pivot P from the chunk (the first in my case), and partitions the data on P into two chunks: data less than P and data greater than P. It then puts the data in the order of [P][less than P][Greater than P]. (So that it can determine where the partitions begin and end without metadata.) On the next iteration it can scan until it finds the first two elements out of order, which will be P and one element less than P, and scan until it finds an element greater than P. It then moves P to the end of the chunk, and performs the algorithm on the chunk of data less than P. Other than the temporary relocation of P, this is basically how quicksort works.

Deviation of Algorithm from Quicksort:  
Since the algorithm needs the data to be in a series of "chunks" of [partition][data between this partition and the previous partition], we have to format the data down the right side until we find the maximum element to get it into this series of chunks, before the rest of the algorithm can run.

This algorithm is quite strange, and I am terrible at explanations, but as proof of concept, here's the a link to my C++ code with a naive quicksort, my inplace quicksort, and stdsort: <http://ideone.com/4iCSo> (I acknowledge there's still a lot of optimizing that could be done, and that this algorithm is so slow it is almost completely useless in general) The meat of the question is: **is this algorithm still a quicksort**?

I'm not clear on the scope of this site, this question might be better suited to <https://cs.stackexchange.com/> or <https://stackoverflow.com/>.

**Tags:** ds.algorithms, sorting

> **Comments:**
> **username_0**: It wasn't until afterwords that I realized a 64bit quicksort that only recurses on the small side and iterates the large partition will always use less than ~1260 bytes, making it O(1) space overhead in practice if not theory.  
> **username_1**: Why do you care?  If it's a good algorithm, use it.  If it's not, don't.  Why does it matter what it's called?  
> **username_0**: @JɛﬀE: it's not a good algorithm, there's faster alternatives even for low stack usage scenarios.  The reason for the question was [Wikipedia](http://en.wikipedia.org/wiki/Quicksort#Space_complexity) says that quicksort has a lower bound of `O(log(N))` extra space, which I believe I have proven to be incorrect.  But it hinges on whether or not this algorithm is a quicksort implementation or not.  
> **username_2**: I do not see any claim about lower bound in the section of the Wikipedia article you linked to.  
> **username_0**: "Worst case space complexity O(n) auxiliary (naive) O(log n) auxiliary" "the entire sort can be done with only O(log n) additional space" "a more complex version which uses an in-place partition algorithm and can achieve the complete sort using O(log n) space..." "To make sure at most O(log N) space is used..." "The in-place version of quicksort has a space complexity of O(log n)" "...requiring at most O(log n) space" "...it uses O(log n) space" "...it would need at least O(n log n) bits of space." "...not-in-place, version of quicksort uses O(n) space..." "...logN additional space..."  
> **username_3**: @MooingDuck Tsuyoshi's point is that all the references you list describe an *upper bound* of log n for space.  
> **username_0**: @SureshVenkat: ....oh.  So it is.  Thanks for the clarification!  Either way: Is this a quicksort?  
> **username_4**: See [When are two algorithms said to be “similar”?](http://cstheory.stackexchange.com/questions/10542/when-are-two-algorithms-said-to-be-similar).  
> **username_5**: There's no central authority that decides whether an algorithm qualifies as a "quicksort"; although your question is interesting, I don't think it is really answerable.  
> **username_0**: @username_4: That's perfect actually.  We should probably close this as a duplicate of that.  
> **username_3**: @PeterShor there is no central authority *as far as you know*....(insert evil laugh)  

---

## 0 answers

