Quicksort infinite loop

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

  1. Rick

    Rick Guest

    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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. Rick

    Eric Sosman Guest

    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
    #3
  4. Rick

    Daniel Pitts Guest

    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
    #4
  5. Rick

    Rick Guest

    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
    #5
  6. Rick

    bugbear Guest

    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
    #6
  7. 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
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Vedran Vukotic

    infinite loop unexpectly dies

    Vedran Vukotic, Mar 2, 2006, in forum: Perl
    Replies:
    0
    Views:
    4,481
    Vedran Vukotic
    Mar 2, 2006
  2. Alexander Bosch

    Infinite loop when using Server.Transfer

    Alexander Bosch, Oct 28, 2004, in forum: ASP .Net
    Replies:
    11
    Views:
    898
    Steven Cheng[MSFT]
    Nov 10, 2004
  3. Alexander Bosch

    Infinite loop when using Server.Transfer

    Alexander Bosch, Oct 31, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    556
    Steven Cheng[MSFT]
    Nov 1, 2004
  4. Replies:
    5
    Views:
    614
    benben
    Jan 31, 2006
  5. Isaac Won
    Replies:
    9
    Views:
    407
    Ulrich Eckhardt
    Mar 4, 2013
Loading...

Share This Page