# Quicksort infinite loop

Discussion in 'Java' started by Rick, Feb 4, 2007.

1. ### RickGuest

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

Rick, Feb 4, 2007

2. ### Patricia ShanahanGuest

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

Patricia Shanahan, Feb 4, 2007

3. ### Eric SosmanGuest

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
lid

Eric Sosman, Feb 4, 2007
4. ### Daniel PittsGuest

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.

Daniel Pitts, Feb 4, 2007
5. ### RickGuest

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

Rick, Feb 5, 2007
6. ### bugbearGuest

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

bugbear, Feb 5, 2007
7. ### Thomas FritschGuest

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

Thomas Fritsch, Feb 5, 2007