- **Java**
(*http://www.velocityreviews.com/forums/f30-java.html*)

- - **Quicksort infinite loop**
(*http://www.velocityreviews.com/forums/t390606-quicksort-infinite-loop.html*)

Quicksort infinite loopI 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); } |

Re: Quicksort infinite loopRick 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 |

Re: Quicksort infinite loopRick 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 |

Re: Quicksort infinite loopRick 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. |

Re: Quicksort infinite loopI 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. |

Re: Quicksort infinite loopRick 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 |

Re: Quicksort infinite loopRick 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. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.