我删除了代码,因为这是家庭作业。如果您确实需要帮助,可以查看我与 George B 的讨论(如下),或者私信我。
大家好。这是家庭作业。我已经针对其他排序算法和 Q.S. 对其进行了测试。是唯一一个在某些随机输入上崩溃的。
程序退出时间很长(还有其他东西),但输入是随机生成的....
我花了几个小时跟踪代码,但仍然无法找出任何错误.... Q.S.对于专业人士来说可能很容易,所以我希望收到有关此实现的建议....
欢迎任何意见!
问:什么是“随机”?
A:包含了一部分生成
void randomArray(unsigned long*& A, unsigned long size)
{
//Note that RAND_MAX is a little small for some compilers (2^16-1).
//In order to test our algorithms on large arrays without huge
//numbers of duplicates, we'll set the high-order and low-order
//parts of the return value with two random values.
A = new unsigned long[size];
for(unsigned long i=0; i<size; i++)
A[i] = (rand()<<16) | (rand());
//Another note: initially, if you want to test your program out with smaller
//arrays and small numbers, just reduce A[i] mod k for some small value k as in the following:
//A[i] = rand() % 16;
//this may help you debug at first.
}
问:什么样的错误?
好吧,我没有遇到编译错误。没有Q.S.,我可以毫无问题地运行其他四种排序算法(我可以连续运行排序)。激活Q.S后,运行程序一两三次,甚至第一次运行,程序就结束了(我用的是Eclipse,所以控制台就结束了)。
enter the number of elements, or a negative number to quit: 5 {some arrays}
selection sort took 0 seconds. merge sort took 0 seconds. quick sort took 0 seconds. heap sort took 0 seconds. bucket sort took 0 seconds. {output of 5 sorted arrays}
enter the number of elements, or a negative number to quit: 6 {some arrays}
selection sort took 0 seconds. merge sort took 0 seconds. quick sort took 0 seconds. heap sort took 0 seconds. bucket sort took 0 seconds.
{output of 5 sorted arrays}
enter the number of elements, or a negative number to quit: 8 {arrays} --- console ends---
同样,问题是它经常崩溃,所以这表明访问冲突的可能性很高,但是进行了 10 次以上的跟踪我没有看到问题....(也许我重载了我的大脑堆栈 -_- )
谢谢。
最佳答案
提示:
q is unsigned (the result of the partition function)
so, q-1 is also unsigned
what if q is zero?
(这是家庭作业,所以我猜你必须弄明白 :) )
关于c++ - 随机快速排序 [某些输入崩溃],我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4424709/