Thread: question about Quick Sort

  1. #1
    Liberty4all
    Guest

    question about Quick Sort

    Hello all.

    I'm sure you all are familiar with the quick sort algoritem, but I'm still gonna post it in short:
    Code:
    IF left < right THEN
       BEGIN
           pivot := partition (list, left, right);
           Quicksort (list, left, pivot-1);
           Quicksort (list, pivot + 1, right);
    END
    In the partition function, the norm is to usually pick the first number in the array as the pivot, right? But if you choose the last one as the pivot, the loop can become endless. How does that happen?

    Thanks in advance

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Did this become a pascal board? Why wasn't I informed?

  3. #3
    liberty4all
    Guest
    Originally posted by master5001
    Did this become a pascal board? Why wasn't I informed?
    Man it's just psedo code, why does it matter if it's in pascal, c or whatever? It's not the point of the question either... but just for you:
    Code:
      if ( left > right )
        {
        pivot = partition( list, left, right );
        quicksort( list, left, pivot-1 );
        quicksort( list, pivot+1, right );
        }
      }

  4. #4
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Errr... one of my quicksort algorithms uses the last number in each subarray as the pivot, and it works just fine, no endless loops. Post your partition code so we can have a look.

  5. #5
    liberty4all
    Guest
    Ok, the (psedo) code is as followed:
    Code:
    Partition(A,p,r)
    {
         x=A[p];
         i=p-1;
         j=r+1;
         while TRUE{
              do repeat j=j-1
              until A[j]<=x;
    
              do repeat i=i+1
              until A[i]>=x;
     
              if i<j
                  swap(A[i],A[j]);
              else
                 return j;
             }
    }
    I am told that if A[r] (the last item) is selected as the pivot it could result in an endless loop, but I realy don't see how...

  6. #6
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Actually, the way you have it written, shouldn't it get an infinite loop everytime your pivot has a duplicate? If you try to find the pivot on something like:
    Code:
    7 6 4 9 8 2 7
    will run indefinately regardless of whether the pivot is at the beginning or the end. I don't have time to check it, but I think one of those <= or >= needs to lose the "or equal". Check to see what happens with my above numbers depending on which "=" you take off and which end you use as the pivot, and you'll probably find your answer. Sorry, don't know the answer off the top of my head, my quicksorts are done a little differently so I had to figure out how yours worked first

  7. #7
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Originally posted by liberty4all
    Man it's just psedo code, why does it matter if it's in pascal, c or whatever? It's not the point of the question either...
    You didn't need to re-write the code. If I didn't give you a hard time then someone else would have. Actually, now that I think about it if you really want a skilled programmer's help then you should post code written in some other language. A well rounded programmer is at least familiar with all popular languages.

  8. #8
    liberty4all
    Guest
    Originally posted by PJYelton
    Actually, the way you have it written, shouldn't it get an infinite loop everytime your pivot has a duplicate? If you try to find the pivot on something like:
    Code:
    7 6 4 9 8 2 7
    will run indefinately regardless of whether the pivot is at the beginning or the end.
    I tried your input and it worked fine, after running partition once the array looked like this:
    Code:
    7 6 4 2 8 9 7
    Four numbers smaller or equal to 7 and three numbers bigger or equal to 7. I didn't write the code I posted before, that's the code I was given and I'm supposed to figure out how by selecting the pivot as the last item it can lead to an infinite loop.

  9. #9
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Okay, I see where the error is now, your quicksort algorithm had an error, it should be this:
    Code:
      if ( left > right )
        {
        pivot = partition( list, left, right );
        quicksort( list, left, pivot);
        quicksort( list, pivot+1, right );
        }
      }
    You only do +1 and -1 with quicksort algorithms that place the pivot in between the two partitions. That being said, do this algorithm on something small like array={4,5} and you'll see that the quicksort loops infininetly if you choose 5 as the pivot, since 5 keeps getting swapped with itself, returning a partition of size 2 and a partition of size 0, thus starting over again. If you want to do the last number of the pivot, you need to change the quicksort to:
    Code:
      if ( left > right )
        {
        pivot = partition( list, left, right );
        quicksort( list, left, pivot-1);
        quicksort( list, pivot, right );
        }
      }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. nonrecursive quick sort
    By Micko in forum C Programming
    Replies: 8
    Last Post: 12-29-2004, 05:50 PM
  2. Help On A Quick Sort Program
    By nick4 in forum C++ Programming
    Replies: 11
    Last Post: 12-06-2004, 10:51 AM
  3. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  4. Questions on basic Quick Sort
    By Weng in forum C++ Programming
    Replies: 4
    Last Post: 12-16-2003, 10:06 AM
  5. Quick question: exit();
    By Cheeze-It in forum C Programming
    Replies: 6
    Last Post: 08-15-2001, 05:46 PM