Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Randomized Quick Sort

  1. Aug 11, 2004 #1
    My textbook has the following code as a Quick Sort. It also discusses a randomized quick sort which should have a faster run time, but doesn't show the code for it. What would the code be like? Is only the pivot changed?

    Code (Text):

    void quickSortStep(Sequence& S, int leftBound, int rightBound) {
         if (leftBound >= rightBound) return;           // 0 or 1 elements
         Object pivot = S.atRank(rightBound).element(); // select last as pivot
         int leftIndex = leftBound;                 // will scan rightward
         int rightIndex = rightBound - 1;           // will scan leftward
       while (leftIndex <= rightIndex) {
          while ((leftIndex <= rightIndex) &&           // scan right to larger
                  S.atRank(leftIndex).element() <= pivot)
           leftIndex++;
          while ((rightIndex >= leftIndex) &&           // scan left to smaller
                  S.atRank(rightIndex).element() >= pivot)
            rightIndex--;
          if (leftIndex < rightIndex)               // both elements found
            S.swapElements(S.atRank(leftIndex), S.atRank(rightIndex));
      }                         // until indices cross
                                // pivot at leftIndex
         S.swapElements(S.atRank(leftIndex), S.atRank(rightBound));
        quickSortStep(S, leftBound, leftIndex-1);       // recur on both sides
        quickSortStep(S, leftIndex+1, rightBound);
    }
     


    http://cpp.datastructures.net/source/ch10/CPP/Sort.h-QuickSort.html
     
  2. jcsd
  3. Aug 11, 2004 #2

    dduardo

    User Avatar
    Staff Emeritus

    In a randomized quicksort algorithm, you randomly pick the pivots in order to avoid the worst case scenario of O(n^2).
     
  4. Aug 11, 2004 #3
    so I can just set Object pivot = rand(); ?
     
  5. Aug 11, 2004 #4

    dduardo

    User Avatar
    Staff Emeritus

    The pivot would have to be between your lower and upper bound.

    If your doing a quicksort on an array you could do this to find the position of the random pivot based on the lower bound:

    PIVOT = LOWER + rand()%(UPPER-LOWER + 1)

    0 <= rand()%(UPPER-LOWER) =< UPPER

    I would then switch the value of the PIVOT with the value of LOWER in order to make the rest of the algorithm just like a normal quicksort.

    EXAMPLE:

    BEFORE

    0123456789 <= ARRAY INDICES
    2349871092 <= ARRAY VALUES

    PIVOT = LOWER + rand()%(UPPER-LOWER+1)
    LOWER = 0
    UPPER = 9
    PIVOT = 0 + rand()%(9-0+1) = rand()%10 = 2

    TEMP = ARRAY[LOWER]
    ARRAY[LOWER] = ARRAY[PIVOT]
    ARRAY[PIVOT] = TEMP

    AFTER
    =|----->------|
    0123456789 <= ARRAY INDICES
    4329871092 <= ARRAY VALUES

    The rest is the same as the regular quicksort.
     
    Last edited: Aug 11, 2004
  6. Aug 11, 2004 #5
    A better choice would be to take the median of both enpoints and the middle element and use insertion sort of partitions less then (8,9 or 10) in length.
     
  7. Aug 12, 2004 #6
    so something like this?

    Code (Text):

    void RandQuickSort(int Array[], int l, int r) {

        int piv=l+(rand()%(r-1+1);
        swap(Array[1],Array[piv]);
        int i = l+1;
        int j = r;
        while (1) {
            while(Array[i] <= Array[1] && i<r) ++i;
        while (Array[j] <= Array[l] && j>l) –-j;
        if (i >=j) {
            swap(Array[j],Array[l]);
        return j;
        }
        else Swap(Array[i],Array[j]);
    }
     
    Last edited: Aug 12, 2004
  8. Aug 12, 2004 #7

    dduardo

    User Avatar
    Staff Emeritus

    The real test is if it works. Have you tried compiling it?

    From the looks of it there is somthing wrong with the first line of your function. What's -1+1? Do you mean -l+1
     
  9. Aug 12, 2004 #8
    Yeah I guess it's not working.

    *updated below
     
    Last edited: Aug 12, 2004
  10. Aug 12, 2004 #9

    dduardo

    User Avatar
    Staff Emeritus

    You give up too quickly. For example:

    RandQuickSort(k);

    This line is obviously wrong. Look at your function definition:

    void RandQuickSort(int Array[], int l, int r)

    It has 3 arguments.
     
  11. Aug 12, 2004 #10
    randQuickSort(k, k[0], k[9]); would saying k[0](left) and k[9] (right) signify their positions in the array?

    The error I keep getting is randQuickSort identifier not found.
     
    Last edited: Aug 12, 2004
  12. Aug 12, 2004 #11

    dduardo

    User Avatar
    Staff Emeritus

    1. Why are you using the array values of the lower and upper bound? I would think you would just use the positions themselves.
    2. C/C++ is case sensitive. RandQuickSort != randQuickSort
     
  13. Aug 12, 2004 #12
    Sorry, I thought that calling on the values would have indicated the positions. How would I call on the positions l, r or would I need to declare the two ints in main first?

    Right now I seem to compile without error, some warnings, and there seems to be a memory leak.

    Code (Text):

    #include <iostream>

    using namespace std;

    void randQuickSort(int Array[], int l, int r);

    int main()
    {
        int k[10];
        int r=0;
        for(int i=0; i < 10; i++){
            cin>> k[i];
        }

        cout << "Unsorted:" <<k <<endl;
       
        randQuickSort(k, i, r-1);

        cout<< "Done with sort.\n";
        cout<< "Displaying sorted input:\n";

        for(int j=0; j < 10; j++){
            cout << k[j];
        }
    }

    void swap(int a, int b)
    {
        int temp;
        temp=a;
        a = b;
        b=temp;
    }

    void randQuickSort(int Array[], int l, int r)
    {
        int piv=l+(rand()%(r-l+1));
        swap(Array[1],Array[piv]);
        int i = l+1;
        int j = r;
        while (Array[i] <= Array[j]) {
        while ((Array[i] <= Array[j]) && i <= piv)
            i++;
        while ((Array[j] <= Array[i]) && j >= piv)
            j--;
        if (Array[i] < Array[j])
            swap (i,j);
    }
    swap(l,r);
    randQuickSort(Array, l, i-1);
    randQuickSort(Array, l+1, r);
    }
     
    And why did earlier you suggested this, where would that go under my sort function:
    Code (Text):

    int temp = Array[l];
        Array[l] = Array[piv];
        Array[piv] = temp;
     
     
    Last edited: Aug 12, 2004
  14. Aug 13, 2004 #13

    dduardo

    User Avatar
    Staff Emeritus

    It seems as if you don't know how quicksort works. I recommend you take the example in your book and examine it by running it through a debugger. Step through the code line by line. If you don't know how to use a debugger ask me.

    You should only have to change one line of code to make quicksort randomized.
     
  15. Aug 13, 2004 #14
    I think I'm getting close, now there are no memory errors and it outputs something, but it outputs the order I inputted.

    Code (Text):

    #include <iostream>

    using namespace std;
    void quickSort(int numbers[], int array_size);
    void randQuickSort(int numbers[], int left, int right);

    int main()
    {
        int k[10];                       //array size of 10
        int r=0;
        cout<<"Enter 10 values in unsorted order : \n";
        for(int i=0; i < 10; i++){
            cin>> k[i];                  //user inputs values
        }
     
        randQuickSort(k, i, r-1);         //sort function being used
     
        cout<<"\nThe Sorted order is : \n";

        for(int j=0; j < 10; j++){
            cout <<k[j] <<"";            //sorted order output
        }
        cout<<endl;
    }

    void quickSort(int numbers[], int array_size)
    {
     randQuickSort(numbers, 0, array_size - 1);
    }

    void randQuickSort(int numbers[], int left, int right)
    {
     if(left>=right) return;
     int pivot = numbers[left+rand()%10];               //pivot = left + rand()%(right-left + 1)
     int leftIndex  = left;
     int rightIndex  = right-1;
     while (left <= right)
     {
       while ((numbers[right] >= pivot) && (left < right))
         right--;
       if (left != right)
       {
         numbers[left] = numbers[right];
         left++;
       }
       while ((numbers[left] <= pivot) && (left < right))
         left++;
       if (left != right)
       {
         numbers[right] = numbers[left];
         right--;
       }
     }
     numbers[left] = pivot;
     pivot = left;
     left = leftIndex ;
     right = rightIndex ;
     if (left < pivot)
       randQuickSort(numbers, left, pivot-1);
     if (right > pivot)
       randQuickSort(numbers, pivot+1, right);
    }
     
    I'm sorry to have been a bother to you dduardo, thanks for your patience. I just wanted to get it working completely by tonight.
     
  16. Aug 13, 2004 #15

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    When your function looks like it's doing nothing, it frequently is, in fact, doing nothing. Can you think of any reason why your function might do nothing?
     
  17. Aug 13, 2004 #16

    I thought that would somehow call the positions of the left and right.
     
  18. Aug 13, 2004 #17

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What values are you passing for left and right?
    (Yes, yes, I know you're passing i for left and r-1 for right; what values do they have?)
     
  19. Aug 13, 2004 #18
    I was thinking 0 and 9, but that had the same effect.
     
  20. Aug 13, 2004 #19

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Do you know what values actually got passed?


    Have you used a debugger like dduardo suggested? If you don't have a debugger available, you can achieve a similar effect by sprinkling cout statements all over your code. For instance, as the first line in your function, you could put:

    cout << "Quicksort called: left = " << left << " and right = " << right << endl;
    cout << "Array is:";
    for(i = left; i <= right; ++i) cout << " " << k << endl;


    (I'm assuming that you're intending right to refer to an index inside the array, instead of the first index outside the array)
     
  21. Aug 13, 2004 #20
    I don't know how to use a debugger

    as for the example you posted in only shows whatever I had inputed
    randQuickSort(k, value,value)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Randomized Quick Sort
  1. Sorting techniques (Replies: 6)

  2. Fastest sort method? (Replies: 8)

Loading...