I think I am going into an infinite loop with my quicksort
implementation.
Here is my call:
quicksort (list);
And here is my quicksort methods:
static void quicksort (int a[], int lo0, int hi0)
{
int lo = lo0; // low index
int hi = hi0; // high index
int mid = a[(lo + hi) / 2]; // middle index value
// partition
while (lo < hi)
{
while (lo < hi && a[lo] < mid)
{
lo++;
}
while (lo < hi && a[hi] >= mid)
{
hi--;
}
if (lo < hi)
{
int T = a[lo];
a[lo] = a[hi];
a[hi] = T;
}
}
if (hi < lo)
{
int T = hi;
hi = lo;
lo = T;
}
// recursion
quicksort(a, lo0, lo);
quicksort(a, lo == lo0 ? lo + 1 : lo, hi0);
}
public void quicksort(int a[])
{
quicksort(a, 0, a.length - 1);
}
Patricia Shanahan - 04 Feb 2007 22:14 GMT
> I think I am going into an infinite loop with my quicksort
> implementation.
What's your base case? How do you ever return from quicksort without
first calling quicksort?
Patricia
Eric Sosman - 04 Feb 2007 22:22 GMT
> I think I am going into an infinite loop with my quicksort
> implementation.
> [...]
There may be snazzier ways to debug your code, but the
tried and true "print while in progress" method is plenty in
most situations. In your case, I'd suggest printing the lo0
and hi0 arguments each time the method is called; you should
quickly see what's wrong. For fancier output, try to print
the recursion level, too -- you'll need to keep track of it
manually, incrementing at each entry to the method and
decrementing when the method returns -- but it may make the
problem even easier to spot.

Signature
Eric Sosman
esosman@acm-dot-org.invalid
Daniel Pitts - 04 Feb 2007 22:34 GMT
> I think I am going into an infinite loop with my quicksort
> implementation.
[quoted text clipped - 43 lines]
> quicksort(a, 0, a.length - 1);
> }
You may want to return from your "quicksort (int a[], int lo0, int
hi0)" method if hi0 < lo0.
What you are getting isn't just an infinit loop, its actually infinit
recursion. You need to have a break-out condition. Some condition
that prevents further recursion.
Rick - 05 Feb 2007 08:25 GMT
I added the return if hi0 <= lo0, but I the list isn't being sorted
entirely.
static void quicksort (int a[], int lo0, int hi0)
{
if (lo0 >= hi0)
{
return;
}
int lo = lo0; // low index
int hi = hi0; // high index
int mid = a[(lo + hi) / 2]; // middle index value
// partition
while (lo < hi)
{
while (lo < hi && a[lo] < mid)
{
lo++;
}
while (lo < hi && a[hi] >= mid)
{
hi--;
}
if (lo < hi)
{
int T = a[lo];
a[lo] = a[hi];
a[hi] = T;
}
}
if (hi < lo)
{
int T = hi;
hi = lo;
lo = T;
}
// recursion
quicksort(a, lo0, lo);
quicksort(a, lo == lo0 ? lo + 1 : lo, hi0);
}
> > I think I am going into an infinite loop with my quicksort
> > implementation.
[quoted text clipped - 50 lines]
> recursion. You need to have a break-out condition. Some condition
> that prevents further recursion.
Thomas Fritsch - 05 Feb 2007 10:39 GMT
> I added the return if hi0 <= lo0, but I the list isn't being sorted
> entirely.
[snip]
> int lo = lo0; // low index
> int hi = hi0; // high index
>
> int mid = a[(lo + hi) / 2]; // middle index value
The code line above doesn't do what the comment says.
Is the code wrong, or is the comment wrong?
[snip]

Signature
Thomas
bugbear - 05 Feb 2007 10:04 GMT
> I think I am going into an infinite loop with my quicksort
> implementation.
I would recommend reading a good (detailed) analysis
of quicksort rather than obsessing over lines of code.
I find Robert Sedgewick excellent.
With a good understanding under your belt,
the code is easy.
Hoping the code will provide
insight into the alogorithm rarely
work (IMHO).
BugBear