我目前正在研究一种快速排序算法,该算法接受随机双精度数、整数、字符和浮点数。目前正在测试双打,我得到了
(process 27368) exited with code -1073740791
。我确实知道这是一个段错误,但我没有发现我所拥有的问题。代码是 C++ 的。这是:
// Code for generating random doubles
vector<double> generateDouble(int size, double min, double max)
{
srand(time(0));
vector<double> array(size);
for (int index = 0; index < size; ++index)
{
double r = (((double)rand() / (double)RAND_MAX) * (max - min)) + min;
array[index] = r;
}
return array;
}
// here is the getIter() function
int Sorting::getIter() const
{
return iter;
}
void Sorting::quickSort()
{
int first = 0;
int last = listData.size() - 1;
quickSort(listData, first, last);
}
void Sorting::quickSort(vector<double>& list, int first, int last)
{
if (first < last)
{
int index = partition(list, first, last);
quickSort(list, first, index - 1);
quickSort(list, index + 1, last); // Corrected index
}
}
int Sorting::partition(vector<double>& list, int first, int last)
{
double pivot = list[last - 1];
int i = first - 1; // Initialize i with first instead of (first - 1)
for (int j = first; j < last; j++)
{
if (list[j] < pivot)
{
// Increment i before swapping
i++;
swap(list[i], list[j]);
}
iter++;
}
// Swap pivot with the element at (i + 1)
swap(list[i], list[last - 1]);
return i;
}
// how I am calling it in main
Sorting quickDSort(dd);
time.startTimer();
quickDSort.quickSort();
time.stopTimer();
cout << "(quick sort) Double Iterations: " << quickDSort.getIter() << endl;
cout << time.getSeconds() << endl;
我已经被困了一段时间,不知道该怎么办。谢谢。
我需要代码来获取
vector<double>
并对其进行排序。目前,它不会打印对数字进行排序所需的次数。
在代码中看到与您实际执行的操作无关的注释很奇怪。 举个例子,
// Swap pivot with the element at (i + 1)
swap(list[i], list[last - 1]);
...您不
与(i + 1)
处的元素交换,实际上您
应该。 其次,当前子数组中的最后一个元素不在
last-1
处,而是在
last
处。所以这个索引也是错误的,无论是在上面引用的代码中,还是在 partition
函数的开头。这是您的 partition
函数,并纠正了这些错误:
int partition(vector<double>& list, int first, int last)
{
double pivot = list[last]; // Should be last, not last-1
int i = first - 1;
for (int j = first; j < last; j++)
{
if (list[j] < pivot)
{
i++;
swap(list[i], list[j]);
}
}
i++; // Must increment
swap(list[i], list[last]); // Should be last, not last-1
return i;
}