quicksort comparison count intermittent results

Question

SOLUTION the solution is unique to my code -- I placed srand(time(NULL)); inside the loop when it should've been placed outside

I'm trying to count the number of comparisons in a quick sort algorithm. I had a recursive version working fine, but it kept seg faulting because I was using large array sizes -- running out of stack space.

So now I've resulted to an iterative approach, and it works. That is, except for my counter for the number of comparisons.

It's returning intermittent results such as...

unsorted: [9][8][7][6][5][4][3][2][1][0]
sorted: [0][1][2][3][4][5][6][7][8][9]
Numer of comparisons: 22

unsorted: [9][8][7][6][5][4][3][2][1][0]
sorted: [0][1][2][3][4][5][6][7][8][9]
Numer of comparisons: 19749794

unsorted: [9][8][7][6][5][4][3][2][1][0]
sorted: [0][1][2][3][4][5][6][7][8][9]
Numer of comparisons: 6088231

my code for the iterative quick sort is...

#include <time.h>
#define BUFLEN 6400

extern int buf[BUFLEN];
extern int quick_count; //comparison count

struct stack {
    int stk[BUFLEN];
    int top;
};

struct stack s;

void push(int x);
int pop();

void iterative_quick_sort (int buf[], int n) {
    int left_ptr, right_ptr, pivot_index, pivot, temp, l, r;
    if (n < 2) //case the partitioning has reached the atomic element
        return;
    r = n - 1;
    l = 0;
    s.top = -1;
    loop: do{
      srand(time(NULL));
      if ((r - l) == 0)
        pivot_index = 1;
      else {
        pivot_index = rand() % (r - l);
        pivot_index += l;
      }
      pivot = buf[pivot_index]; //pivot holds the value of the pivot element
      left_ptr = l;
      right_ptr = r;
      if ((r - l) != 0 || (r - l) != 1){
        while (1) {
            while (buf[left_ptr] < pivot){ //loop and increment left_ptr until an element on the left side is larger than the pivot
              left_ptr++;
            } //now left_ptr holds the index of the value that needs to be swapped with an element from the right side
            while (pivot < buf[right_ptr]){ //loop and increment right_ptr until an element on the right side is smaller than the pivot
              right_ptr--;
            } //now right_ptr holds the index of the value that needs to be swapped with an element from the left side
            quick_count++;
            if (left_ptr >= right_ptr)
                break; //once the pivots reach or overlap each other, break the loop
            //perform swap with temporary variable temp
            temp = buf[left_ptr];
            buf[left_ptr] = buf[right_ptr];
            buf[right_ptr] = temp;
        }
      }

      if (l == (n - 2))
        break;
      else if ((r - l) >= 2){
        //goto loop with left side values
        push(r);
        r = pivot_index + 1;
        goto loop;
      }
      else {
        //goto loop with right side values
        l = r;
        r = pop();
        goto loop;
      }
  }while(1);
}

//cite http://www.sanfoundry.com/c-program-stack-implementation/
void push (int x){
    s.top = s.top + 1;
    s.stk[s.top] = x;
}

int pop(){
    int x = s.stk[s.top];
    s.top = s.top - 1;
    return x;
}

per request, I've added the function that calls quick sort (Note: quick_count is initialized to zero as a global variable -- used as an extern)

int unsorted_quick[] = {9,8,7,6,5,4,3,2,1,0}; //n = 10
//print unsorted_quick
  printf("\nSecond, we sort the following array by using the quick sort algorithm\n");
  for (i = 0; i < 10; i++){
    printf("[%d]", unsorted_quick[i]);
  }
  printf("\n");

  //fill buf with the unsorted quick array
  for (i = 0; i < 10; i++){
    buf[i] = unsorted_quick[i];
  }

  iterative_quick_sort(buf, 10); //call quick_sort()

  //print sorted
  for (i = 0; i < 10; i++){
    printf("[%d]", buf[i]);
  }
  printf("\nNumber of comparisons: %d\n", quick_count);  //print count

I cannot see any code here which prints "sorted:", "unsorted:", or "Numer of comparisons:" ... – A concrete example would be helpful. — Martin R, Dec 01 '15 at 13:44
where do you initialise quick_count? Inside the function is not initialised. — terence hill, Dec 01 '15 at 13:45
@MartinR The printing occurs in the main function (count is a global) — kendall, Dec 01 '15 at 13:49
Then show the main function, the input data, what you already did to *debug* the problem etc etc ... — Martin R, Dec 01 '15 at 13:50
quicksort shoud not run out of stack space if correctly implemented: you should always recurse on the smaller half and loop on the larger half. This way you limit the number of recursive calls to log2(n). — chqrlie, Dec 01 '15 at 13:53
@chqrlie I don't follow. All the recursive implementations I've seen recurse on both halves. What do you mean smaller and larger halves? — kendall, Dec 01 '15 at 13:54
@MartinR done -- as for debugging, when I debug I always get the correct answer (note that I've debugged it at least 5 times now, maybe 6th is a charm?) — kendall, Dec 01 '15 at 13:55
You have seen only naive implementations. Any industry strength implementation must only recurse on the smaller half or use a non recursive implementation. Read this paper to understand how to kill qsort and therefore to crash a naive recursive implementation: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf . Your approach with a random choice of pivot is interesting to try and avoid this. — chqrlie, Dec 01 '15 at 14:00
I think that this "srand(time(NULL))" should be outside the loop: do — terence hill, Dec 01 '15 at 14:03
@terencehill that was it! wow, I would've never thought. Do you know why? — kendall, Dec 01 '15 at 14:13

score 1 · Accepted Answer · edited May 23 '17 at 11:44

You are calling srand(time(NULL)) inside the loop that choose the random pivot. This function must be called once to initialise the state of the random number generator. The generator needs a starting seed which is set by calling srand(). Then, given the seed, each subsequent call to rand() will give you a random number in a reproducible sequence. Starting from the same seed you will get the same random sequence.

The problem is that you set the seed in the loop and the seed is the same number so you will always get the same "random" value. This happens because time(NULL) is taken from current time in seconds which means that the random number it's the same in the same second.

You must put it before the loop: do {

Here there is a nice explanation of what is happening: Problems when calling srand(time(NULL)) inside rollDice function

And also here: srand() — why call it only once?

quicksort comparison count intermittent results

1 Answers1