Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Java (http://www.velocityreviews.com/forums/f30-java.html)
-   -   Quicksort infinite loop (http://www.velocityreviews.com/forums/t390606-quicksort-infinite-loop.html)

 Rick 02-04-2007 10:05 PM

Quicksort infinite loop

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 02-04-2007 10:14 PM

Re: Quicksort infinite loop

Rick wrote:
> 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 02-04-2007 10:22 PM

Re: Quicksort infinite loop

Rick wrote:
> 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.

--
Eric Sosman
esosman@acm-dot-org.invalid

 Daniel Pitts 02-04-2007 10:34 PM

Re: Quicksort infinite loop

Rick wrote:
> 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);
> }

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 02-05-2007 08:25 AM

Re: Quicksort infinite loop

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);
}

On Feb 4, 2:34 pm, "Daniel Pitts" <googlegrou...@coloraura.com> wrote:
> Rick wrote:
> > 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);
> > }

>
> 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.

 bugbear 02-05-2007 10:04 AM

Re: Quicksort infinite loop

Rick wrote:
> 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

 Thomas Fritsch 02-05-2007 10:39 AM

Re: Quicksort infinite loop

Rick wrote:
> 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]

--
Thomas

 All times are GMT. The time now is 12:28 AM.