Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / General Programming / Quicksort: what's the deal? Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
fman256

May 21, 2005, 02:08 AM

Every quicksort implementation i've ever found has had a fundemental flaw. They all read the (n+1)th element of the array. Two of them are from books! Can anyone tell me why?

 
nih_co

May 21, 2005, 02:16 AM

oh no, you've just uncovered the vast conspiracy! run before they trace your post.

Anyway, could you post a link or code? That does seem odd that they would all have the same problem. Have you tested them and experienced the error or did you just analyze the code?

I believe you but I have no idea why.

 
fman256

May 21, 2005, 02:25 AM

this is from http://theory.stanford.edu/~amitp/rants/c++-vs-c/
(it's the C(hand coded) under appendix:)

void mysort(T* data, int N)
{
int i, j;
T v, t;

if(N is read befor the i= j) break; t = data; data = data[j]; data[j] = t; } t = data[i-1]; data[i-1] = data[0]; data[0] = t; mysort(data, i-1); mysort(data+i, N-i); } If you want to see the one's from my books i'll show you, but i dont feel like typing them in;) But its basically the same thing happening in them.

 
Patrick Grawehr

May 21, 2005, 04:12 AM

You seem to be right, that code really has this flaw. No idea why this is so, though. Have you really looked at other implementations? You might for instance look at the implementation microsoft provides with VS. Look at Vc7crtsrcqsort.c. The code there is a bit more complicated, but it's very well documented and does not access the after-last element of the array.

 
LastInquisitor

May 21, 2005, 04:20 AM

Perhaps I'm missing something, but I see no flaw at all. The if statements in the functions 3rd. line and in the for-loop's 3rd. line handle the critical N values.

 
fman256

May 21, 2005, 04:28 AM

This one is from "teach yourself...C++" by Al Stevens.

template void Quicksort(T** data, int hi,int lo=0)
{
T *tmp;
while(hi>lo)
{
int i=lo,j=hi;
while(i; data=data[j]; data[j]=tmp; } } tmp=data[lo]; data[lo]=data[j]; data[j]=tmp; if(j-lo>hi-(j+1)) { Quicksort(data,j,lo); lo=j+1; } else { Quicksort(data,hi,j+1); hi=j-1; } } } The problem with this one is obvious if you think about what happens when the array only has 1 element.

 
tokjunior

May 21, 2005, 04:31 AM

Actually, it never reaches the point where i>n. It breaks out of the loop the iteration before that.
Run it through a debugger and have a look.

 
tokjunior

May 21, 2005, 04:32 AM

If the array has one element, hi won't be larger than lo, so it won't even enter the while-statement.

 
fman256

May 21, 2005, 04:41 AM

For a 1 element array, hi is 1 and lo is 0, so it does enter the loop.
And I already tried calling it with hi=elements-1, it wont sort the last element that way.

 
tokjunior

May 21, 2005, 04:46 AM

Ah, true.
But reading trough the source again, i still don't see where it would read past the end of the array.
Have you run it through a debugger?

 
fman256

May 21, 2005, 04:53 AM

this is what happens the first time through the code for a 1 element array

while(hi>lo) //true
{
int i=lo,j=hi; //i=0,j=1
while(i

 
LastInquisitor

May 21, 2005, 05:27 AM

Well, your first snippet doesn't have any flaws. And you are misusing the second one: hi shouldn't be the item count, but the index of the last element. In this case hi=0 and not hi=1.

 
fman256

May 21, 2005, 05:34 AM

Like I said, if i set hi to # of elements-1, the last element dosent get sorted(it stays where it is).
As for the first one, which crashes while trying to access past the end of the array, i rewrote the line:
while(data[++i] < v && i < N) { }
to read:
while(i

 
LastInquisitor

May 21, 2005, 05:44 AM

Ooops, right the second one seems to be shit indeed. Though your first statemens to it ("... if you think about what happens ...") were wrong.

 
fman256

May 21, 2005, 06:34 AM

Yeah, sorry. I'm wrong about what goes wring with the first code, but it still dosent seem to work.

  1.  
  2.  
  3. class   item
  4. {
  5. public:
  6.  int i;
  7.  int    operator>(item &p2)
  8.  {       if(this-array>1 || &p2-array>1) printf("error!n");
  9.          return i>p2.i;  }
  10.  int    operator<(item &p2)
  11.  {       if(this-array>1 || &p2-array>1) printf("error!n");
  12.          return i<p2.i;  }
  13.  
  14. } *array;
  15.  
  16. template<class T> void mysort(T* data, int N)
  17. {
  18.  int i, j;
  19.  T v, t;
  20.  if(N<=1) return;
  21.  i = 0;
  22.  j = N;
  23.  for(;;)
  24.  {
  25.  while(data[++i] < data[0] && i < N) { }
  26.  while(data[--j] > data[0]) { }
  27.  if(i >= j) break;
  28.  t = data[i]; data[i] = data[j]; data[j] = t;
  29.  }
  30.  t = data[i-1]; data[i-1] = data[0]; data[0] = t;
  31.  mysort(data, i-1);
  32.  mysort(data+i, N-i);
  33. }
  34.  
  35. main()
  36. {
  37.         array=new item[5];
  38.         array[0].i=2;
  39.         array[1].i=1;
  40.         mysort(array,2);
  41.  
  42.         int i;
  43.         for(i=0;i<2;i++)
  44.                 printf("%dn",array[i].i);
  45.  
  46.  
  47. }
  48.  
  49.  


output:
error!
1
2

 
This thread contains 15 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.