快速排序比较计数间歇性结果
quicksort comparison count intermittent results
SOLUTION 该解决方案对我的代码来说是独一无二的——我将 srand(time(NULL));
放在了循环中,而它本应放在循环外
我正在尝试计算快速排序算法中的比较次数。我有一个递归版本工作正常,但它一直出现段错误,因为我使用的是大数组大小——运行 out of stack space.
所以现在我得出了一种迭代方法,并且它有效。也就是说,除了我的比较次数计数器。
它正在返回间歇性结果,例如...
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
您在选择随机枢轴的循环内调用 srand(time(NULL))。此函数必须调用一次以初始化随机数生成器的状态。
生成器需要一个通过调用 srand() 设置的起始种子。然后,给定种子,对 rand() 的每次后续调用都会以可重现的序列为您提供一个随机数。
从相同的种子开始,您将获得相同的随机序列。
问题是您在循环中设置了种子并且种子是相同的数字,因此您将始终获得相同的 "random" 值。发生这种情况是因为 time(NULL) 是以秒为单位从当前时间获取的,这意味着随机数在同一秒内是相同的。
你必须把它放在循环之前:do {
这里对正在发生的事情有一个很好的解释:Problems when calling srand(time(NULL)) inside rollDice function
还有这里:srand() — why call it only once?
SOLUTION 该解决方案对我的代码来说是独一无二的——我将 srand(time(NULL));
放在了循环中,而它本应放在循环外
我正在尝试计算快速排序算法中的比较次数。我有一个递归版本工作正常,但它一直出现段错误,因为我使用的是大数组大小——运行 out of stack space.
所以现在我得出了一种迭代方法,并且它有效。也就是说,除了我的比较次数计数器。
它正在返回间歇性结果,例如...
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
您在选择随机枢轴的循环内调用 srand(time(NULL))。此函数必须调用一次以初始化随机数生成器的状态。 生成器需要一个通过调用 srand() 设置的起始种子。然后,给定种子,对 rand() 的每次后续调用都会以可重现的序列为您提供一个随机数。 从相同的种子开始,您将获得相同的随机序列。
问题是您在循环中设置了种子并且种子是相同的数字,因此您将始终获得相同的 "random" 值。发生这种情况是因为 time(NULL) 是以秒为单位从当前时间获取的,这意味着随机数在同一秒内是相同的。
你必须把它放在循环之前:do {
这里对正在发生的事情有一个很好的解释:Problems when calling srand(time(NULL)) inside rollDice function
还有这里:srand() — why call it only once?