Like Tree2Likes
  • 1 Post By Salem
  • 1 Post By antred

Quicksort infinite loop

This is a discussion on Quicksort infinite loop within the C++ Programming forums, part of the General Programming Boards category; I am trying to implement quicksort as a sorting algorithm. However, I seem to get an infinite loop. Tried my ...

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    102

    Quicksort infinite loop

    I am trying to implement quicksort as a sorting algorithm. However, I seem to get an infinite loop. Tried my best to figure it out but couldn't. Any help appreciated. Here is the code.
    Code:
    template <typename E>
    void TestQucikSort<E>::quickSort(E temparr [], size_t l, size_t r) const {		
    		if(r-l > 1) {
    			E pivot = temparr[(l+r)/2];
    			size_t i = l, j = r;
    			while(i <= j) {
    				while(pivot > temparr[i]) ++i;
    				while(temparr[j] > pivot) --j;
    				if(i <= r) {
    					std::swap(temparr[i],temparr[j]);
    					++i;
    					--j;
    				}
    			}
    			quickSort(temparr,l,j);
    			quickSort(temparr,i,r);
    		}
    }
    Last edited by Dontgiveup; 06-08-2012 at 10:48 PM.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,540
    Where's the rest of your test program?

    Do you have a debugger? Have you tried using it?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    102
    the rest of the program is pretty long and the problem seems to be with this function. For example if I try to sort an array with values 666, 4711, and 4294967295, I get an infinite loop. Oh and I don't have a debugger, very new to programming, so don't know a lot about that.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,540
    How hard can it be to just mock up a test program?
    Code:
    int main ( ) {
      int test[] = { 4711, 4294967295, 666 };
      TestQucikSort<int>::quickSort(test, 0, 2);
    }
    Create a new project with just a main(), your template and whatever header files needed to make it compile.

    > Oh and I don't have a debugger, very new to programming, so don't know a lot about that.
    Which compiler/IDE do you have.

    If you can't use a debugger, at least put something like
    cout << "qsort << l << " " << r << endl;
    at the start of the function.

    If it's gone into endless recursion, you'll soon see it.
    antred likes this.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User antred's Avatar
    Join Date
    Apr 2012
    Location
    Germany
    Posts
    244
    Finding out how to use your debugger should be one of the first things to do when learning how to program. Initially you don't have to master every single feature your debugger provides, but at least learn how to single-step through your code, set breakpoints and inspect the values of variables. Trust me, it will save you SOOOO much trouble down the road.
    Salem likes this.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    I see some problems:
    1. If none of the values are less than the pivot and none of them are greater than the pivot, then i and j will not be changed by the inner while loops and the outer while loop will thus loop forever. This would happen when there were say two equal items to sort.

    2. Pay attention to your boundary conditions. Is r supposed to be one-past-the-last-item, or the index of the actual last item? If the later, then (r-l > 1) implies that there are two or more items. So exactly two items wont be sorted at all. Note that the "one-past-the-last-item" rule matches what the SC++L does, which turns out to require fewer places where you have to add or subtract 1 here and there.

    Those might not be your current problem, but they are certainly something that you need to fix.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 10-14-2011, 11:33 PM
  2. infinite loop
    By scudshouse in forum C Programming
    Replies: 3
    Last Post: 09-12-2005, 07:30 AM
  3. stays in loop, but it's not an infinite loop (C++)
    By Berticus in forum C++ Programming
    Replies: 8
    Last Post: 07-19-2005, 11:17 AM
  4. infinite loop
    By dukemarlon in forum C++ Programming
    Replies: 11
    Last Post: 11-26-2002, 08:00 AM
  5. MS VS and the infinite while loop
    By WebSnozz in forum C++ Programming
    Replies: 3
    Last Post: 01-31-2002, 07:50 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21