1

Possible Duplicate:
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/.

Community
  • 1
Mooing Duck
  • 119
  • 3
  • 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 May 09 '12 at 17:41
  • 5
    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ε May 09 '12 at 19:08
  • @JɛffE: it's not a good algorithm, there's faster alternatives even for low stack usage scenarios. The reason for the question was Wikipedia 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 May 09 '12 at 20:08
  • I do not see any claim about lower bound in the section of the Wikipedia article you linked to. – Tsuyoshi Ito May 09 '12 at 22:59
  • "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 May 09 '12 at 23:24
  • 2
    @MooingDuck Tsuyoshi's point is that all the references you list describe an upper bound of log n for space. – Suresh Venkat May 10 '12 at 00:39
  • @SureshVenkat: ....oh. So it is. Thanks for the clarification! Either way: Is this a quicksort? – Mooing Duck May 10 '12 at 02:28
  • 1
    See When are two algorithms said to be “similar”?. – Kaveh May 10 '12 at 03:59
  • 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 May 10 '12 at 15:27
  • @Kaveh: That's perfect actually. We should probably close this as a duplicate of that. – Mooing Duck May 10 '12 at 15:58
  • 4
    @PeterShor there is no central authority as far as you know....(insert evil laugh) – Suresh Venkat May 10 '12 at 19:03

0 Answers0