Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / February 2007

Tip: Looking for answers? Try searching our database.

Quicksort infinite loop

Thread view: 
Rick - 04 Feb 2007 22:05 GMT
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


Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.