随机快速排序[在一些输入上崩溃]

我删除了代码，因为它是作业。如果你确实需要帮助，你可以看看我与George B（下面）讨论的内容，或者PM Me。随机快速排序[在一些输入上崩溃]

嗨，大家好。这是一项家庭作业。我已经对其他排序算法进行了测试，并且Q.S.是唯一一个在某些随机输入上崩溃的人。

该程序退出长（与其他的东西），但随机地生成输入....

我花几个小时跟踪代码和仍然无法找出任何错误.... QS对于专业人士来说可能是非常容易的，所以我希望能够在这个实现方面接受建议......

任何输入赞赏！

问：什么是“随机”？

答：包括一代的一部分。

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，所以控制台结束）。

输入元件的数量，或负数退出：5 {一些阵列}

选择排序了0秒。合并排序花了0秒。快速排序花了0 秒。堆排序花了0秒。桶排序花了0秒。 { 5排序阵列的输出}

输入元件的数量，或负数退出：6 {一些阵列}

选择排序了0秒。合并排序花了0秒。快速排序花了0 秒。堆排序花了0秒。桶排序花了0秒。

输入元件的数量，或负数退出{5个排序阵列的输出}：8 {阵列} ---控制台结束---

同样，问题在于它经常崩溃，所以这表明访问违规的可能性很高，但是做了10次以上的跟踪，我没有看到问题....（也许我超负荷了我的大脑堆栈 - _ - ）

谢谢。

来源

2010-12-12 CppLearner

一起使用的“随机”和“排序”一词有点混淆。 – jwueller 2010-12-12 23:25:33

你能告诉我们错误是什么吗？ – ALOToverflow 2010-12-12 23:25:43

嗨，是的。我编辑我的帖子的答案和完整的程序...我希望这有助于调试...谢谢....我仍然在追踪...：/ – CppLearner 2010-12-12 23:42:17

提示：

q is unsigned (the result of the partition function) 
so, q-1 is also unsigned 
what if q is zero?

（这是功课，所以你必须弄明白我猜:)）

来源

2010-12-12 23:47:59 George

首先，谢谢你的提示！这是真的......当我做这个QS时，我以前的一个实现也认识到了这个问题。谢谢。但我忘了改变它只是现在......问题是，然而，分区使用无符号long在接口中，即使我明确地int ...该程序仍然崩溃... – CppLearner 2010-12-12 23:55:32

int q = Partition（ A，p，r）; \t \t \t quickSort（A，p，int（q-1））; \t \t \t quickSort（A，int（q + 1），r）; 你能否提供一点见解如何处理？ – CppLearner 2010-12-12 23:56:04

哦实际上-1不存在...我应该补充说，作为返回immedlately ...对不对？ – CppLearner 2010-12-12 23:56:49

跟踪你的算法与阵列。显然，只要列表中有重复的号码，程序就会崩溃。分区的第一个调用将返回2作为r的索引。因此，第二次调用quickSort(A,3,2)将访问不在数组边界内的存储单元。它始终是一个好主意，可以手动对数组进行边界检查并生成可理解的输出，从而更轻松地跟踪和调试程序。

来源

2010-12-12 23:52:47 Pirooz

没错。我要仔细检查条件。谢谢，Pirooz。 – CppLearner 2010-12-13 00:05:48

随机快速排序[在一些输入上崩溃]

回答

相关问题