Quicksort infinite loop

[Rick]

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]

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]

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.

 

[Daniel Pitts]

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]

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.

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]

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]

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]