Thread: Randomized Quicksort problem

  1. #1
    Registered User
    Join Date
    Apr 2012
    Posts
    12

    Randomized Quicksort problem

    I am trying to make a randomized quicksort. I have try a lot of quicksorts varieties to see if i can work on others but still i cannot make it to run properly. My quicksort sorts an array of structs based on an id. It is the same (i think) like an ordinary array, except from the refference to the struct. The code is based on a standar quicksort code that works with the left element of the array as pivot and i just swap the randomized pivot element with the left, so it will work just the same. But sometimes the results are correct and others are wrong.

    Code:
    typedef struct Student{
        int id;            
        char name[20];    
        char surname[20]; 
    } Student;
    
    typedef struct Students{    
    Student *arr; 
        int size;            
        int sorted; //1 if by surname, name, 2 if by ID
    } Students;
    
    void sortID(Students *st){
         quickSort(st->arr,0 , st->size-1);
         st->sorted = 2;
    }
         
    int pivotSelect(int left, int right){
        
        srand(time(NULL));
        int pivot = left + rand()%(right-left + 1);
        return pivot;
    }
         
    int partition (Student *A, int left, int right, int pivotIndex){
        swap(&A[left],&A[pivotIndex]);
        
        int lc = left + 1;
        int rc = right;
        while (lc < rc) {
              while ( A[lc].id<=A[left].id  && lc<right)
                    lc++;
              while (A[rc].id>A[left].id)
                    rc--;
              if (lc < rc) 
                    swap(&A[lc], &A[rc]);
        }
        swap (&A[left], &A[rc]);
        return rc;
    }
    
    void quickSort(Student *A, int left, int right) {
         if (left >= right) return;
         int pivotIndex = pivotSelect(left,right);
         int p = partition(A, idCmp, left, right, pivotIndex);
         quickSort(A, left, p-1);
         quickSort(A, p+1, right); 
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Does your code always work when you change pivotSelect to just return left?

    By the way, you should move the srand call to near the start of your main function. There is no point seeding the PRNG for each time you want to call rand.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I'd word it a bit more strongly than that... calling srand(time(NULL)) more than once in your program is a bug. Re-seeding like that destroys the randomness. Why? Largely because whilst the absolute time that your program starts executing is fairly random, the relative time differences whilst your program is running are fairly predictable.
    Move that line to the top of main.

    Next, a good way to solve the problem is to find the simplest possible case that does not work, then debug that case.
    First, check does it work correctly for zero items?
    Does it work correctly for one item?
    Does it work correctly for two items already in order?
    Does it work correctly for two items out of order?
    Does it work for three items in any order?
    What about four?
    Five?

    Also, for debuging purposes you'll find that it's best to temporarily change that srand call that you've by now moved to the start of main, to something like srand(12345); That way rand will produce the same sequence of numbers each time, which means that once you get the wrong result you run the program again and step through it slowly to see where it goes wrong.
    Afterwards change it back to seeing based on time(NULL).
    Last edited by iMalc; 04-06-2012 at 11:37 PM.
    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. Randomized multiple choice
    By Chucker in forum C Programming
    Replies: 5
    Last Post: 02-20-2012, 07:27 PM
  2. Quicksort-1000000-lines problem
    By gwmexod in forum C Programming
    Replies: 9
    Last Post: 06-15-2006, 03:01 AM
  3. Quicksort problem, now with clear code
    By rvanbeusichem in forum C Programming
    Replies: 1
    Last Post: 11-25-2004, 01:54 PM
  4. quicksort problem
    By spinner in forum C Programming
    Replies: 9
    Last Post: 05-04-2003, 02:02 PM
  5. Quicksort problem
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 04-17-2002, 08:23 AM