c++快速排序运行时间
我有一个关于快速排序算法的问题。我实现了快速排序算法并播放它。 初始未排序数组中的元素是从一定范围内选择的随机数。 我发现随机数的范围会影响运行时间。例如，从 (1 - 2000) 范围内选择的 1, 000, 000 随机数的运行时间需要 40 秒。而如果从范围（1 - 10,000）中选择 1,000,000 个数字，则需要 9 秒。 但我不知道如何解释。课堂上我们讲到主元值会影响递归树的深度。
对于我的实现，选择数组的最后一个值作为主值。我不使用随机方案来选择枢轴值。
int partition( vector<int> &vec, int p, int r) {
int x = vec[r];
int i = (p-1);
int j = p;
while(1) {
if (vec[j] <= x){
i = (i+1);
int temp = vec[j];
vec[j] = vec[i];
vec[i] = temp;
}
j=j+1;
if (j==r)
break;
}
int temp = vec[i+1];
vec[i+1] = vec[r];
vec[r] = temp;
return i+1;
}
void quicksort ( vector<int> &vec, int p, int r) {
if (p<r){
int q = partition(vec, p, r);
quicksort(vec, p, q-1);
quicksort(vec, q+1, r);
}
}
void random_generator(int num, int * array) {
srand((unsigned)time(0));
int random_integer;
for(int index=0; index< num; index++){
random_integer = (rand()%10000)+1;
*(array+index) = random_integer;
}
}
int main() {
int array_size = 1000000;
int input_array[array_size];
random_generator(array_size, input_array);
vector<int> vec(input_array, input_array+array_size);
clock_t t1, t2;
t1 = clock();
quicksort(vec, 0, (array_size - 1)); // call quick sort
int length = vec.size();
t2 = clock();
float diff = ((float)t2 - (float)t1);
cout << diff << endl;
cout << diff/CLOCKS_PER_SEC <<endl;
}
I have a question about quick sort algorithm. I implement quick sort algorithm and play it.
The elements in initial unsorted array are random numbers chosen from certain range.
I find the range of random number effects the running time. For example, the running time for 1, 000, 000 random number chosen from the range (1 - 2000) takes 40 seconds. While it takes 9 seconds if the 1,000,000 number chosen from the range (1 - 10,000).
But I do not know how to explain it. In class, we talk about the pivot value can effect the depth of recursion tree.
For my implementation, the last value of the array is chosen as pivot value. I do not use randomized scheme to select pivot value.
int partition( vector<int> &vec, int p, int r) {
int x = vec[r];
int i = (p-1);
int j = p;
while(1) {
if (vec[j] <= x){
i = (i+1);
int temp = vec[j];
vec[j] = vec[i];
vec[i] = temp;
}
j=j+1;
if (j==r)
break;
}
int temp = vec[i+1];
vec[i+1] = vec[r];
vec[r] = temp;
return i+1;
}
void quicksort ( vector<int> &vec, int p, int r) {
if (p<r){
int q = partition(vec, p, r);
quicksort(vec, p, q-1);
quicksort(vec, q+1, r);
}
}
void random_generator(int num, int * array) {
srand((unsigned)time(0));
int random_integer;
for(int index=0; index< num; index++){
random_integer = (rand()%10000)+1;
*(array+index) = random_integer;
}
}
int main() {
int array_size = 1000000;
int input_array[array_size];
random_generator(array_size, input_array);
vector<int> vec(input_array, input_array+array_size);
clock_t t1, t2;
t1 = clock();
quicksort(vec, 0, (array_size - 1)); // call quick sort
int length = vec.size();
t2 = clock();
float diff = ((float)t2 - (float)t1);
cout << diff << endl;
cout << diff/CLOCKS_PER_SEC <<endl;
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
最有可能的是它的性能不佳，因为快速排序不能很好地处理大量重复项，并且仍然可能导致交换它们（不保证保留键相等元素的顺序）。您会注意到，对于 10000，每个数字的重复次数为 100；对于 2000，每个数字的重复次数为 100；对于 2000，每个数字的重复次数为 500，而时间因子也大约为 5。
您是否对每个大小至少 5-10 次运行的运行时间进行了平均，得出获得良好起始支点的公平机会吗？
作为比较，您是否检查过 std::sort 和 std::stable_sort 在相同数据集上的执行情况？
最后，对于这种数据分布（除非这是一个快速排序练习），我认为计数排序会更好 - 40K 内存来存储计数，并且运行时间复杂度为 O(n)。
Most likely it's not performing well because quicksort doesn't handle lots of duplicates very well and may still result in swapping them (order of key-equal elements isn't guaranteed to be preserved). You'll notice that the number of duplicates per number is 100 for 10000 or 500 for 2000, while the time factor is also approximately a factor of 5.
Have you averaged the runtimes over at least 5-10 runs at each size to give it a fair shot of getting a good starting pivot?
As a comparison have you checked to see how std::sort and std::stable_sort also perform on the same data sets?
Finally for this distribution of data (unless this is a quicksort exercise) I think counting sort would be much better - 40K memory to store the counts and it runs in O(n).
这可能与输入的排序程度有关。如果输入相当随机，则快速排序的复杂度为 O(n logn)。如果顺序相反，性能可能会降低到 O(n^2)。使用较小的数据范围，您可能会更接近 O(n^2) 行为。
It probably has to do with how well sorted the input is. Quicksort is O(n logn) if the input is reasonably random. If it's in reverse order, performance can degrade to O(n^2). You're probably getting closer to the O(n^2) behavior with the smaller data range.
迟到的答案 - 重复项的影响取决于分区方案。问题中的示例代码是 Lomuto 分区方案的变体，随着重复次数的增加，由于分区变得更糟，它需要更多的时间。在所有元素相等的情况下，Lomuto 在每一级递归中仅将大小减少 1 个元素。
如果使用 Hoare 分区方案（以中间值作为主元），则随着重复项数量的增加，通常需要更少的时间。由于重复，霍尔将不必要地交换等于主元的值，但分区将接近将数组分割为几乎相同大小的部分的理想情况。交换开销在一定程度上被内存缓存掩盖了。链接到 Hoare 分区方案的 Wiki 示例：
https://en.wikipedia.org/wiki/Quicksort #Hoare_partition_scheme
Late answer - the effect of duplicates depends on the partition scheme. The example code in the question is a variation of Lomuto partition scheme, which takes more time as the number of duplicates increases, due to the partitioning getting worse. In the case of all equal elements, Lomuto only reduces the size by 1 element with each level of recursion.
If instead Hoare partition scheme was used (with middle value as pivot), it generally takes less time as the number of duplicates increases. Hoare will needlessly swap values equal to the pivot, due to duplicates, but the partitioning will approach the ideal case of splitting an array in nearly equally sized parts. The swap overhead is somewhat masked by memory cache. Link to Wiki example of Hoare partition scheme:
https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme