сравнение быстрой сортировки подсчитывать прерывистый результаты

Question

РЕШЕНИЕ решение является уникальным для моего кода - я поместил srand(time(NULL)); внутри цикла, когда он должен был быть размещен вне

---

Я пытаюсь подсчитать количество сравнение в алгоритме быстрой сортировки. У меня была рекурсивная версия, работающая нормально, но она сохраняла seg-сбои, потому что я использовал большие размеры массива - закончил пространство стека.

Итак, теперь я привел к итеративному подходу, и он работает. То есть, за исключением моего счетчика для количества сравнений.

Это возвращение неустойчивые результаты, такие как ...

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 

мой код для итеративного быстрой сортировки является ...

#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; 
} 

за запрос, я добавил функцию, которая вызывает быстрое сортировать (Примечание: quick_count инициализируется нулем в качестве глобальной переменной - используется в качестве экстерном)

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 

Answer 1

Вы вызываете srand (time (NULL)) внутри цикла, который выбирает случайный стержень. Эту функцию нужно вызвать один раз, чтобы инициализировать состояние генератора случайных чисел. Генератору требуется начальное семя, которое задается вызовом srand(). Затем, учитывая семя, каждый последующий вызов rand() даст вам случайное число в воспроизводимой последовательности. Начиная с того же семени, вы получите такую ​​же случайную последовательность.

Проблема в том, что вы устанавливаете семя в цикле, а семя такое же, чтобы вы всегда получали одно и то же «случайное» значение. Это происходит потому, что время (NULL) берется из текущего времени в секундах, что означает, что случайное число одинаково в той же секунде.

Вы должны поставить его перед циклом: Do {

Здесь есть хорошее объяснение того, что происходит: Problems when calling srand(time(NULL)) inside rollDice function

А также здесь: srand() — why call it only once?