快速排序为常数提供stackoverflow但不是随机数

当我将数组值赋值为rand()或任何常数值时，我感到非常困惑，为什么此C++代码段的行为不同。快速排序为常数提供stackoverflow但不是随机数

const int MIN_SIZE = 10000; 
const int MAX_SIZE = 100000; 

int main() 
{ 
    for(j = MIN_SIZE; j <= MAX_SIZE; j += MIN_SIZE) { 
    int *arrPtr = new int[j]; 
    for(int i = 0; i < j; i++) 
     arrPtr[i] = 1; //When I put rand() here, it works fine but in any constant it gives stack overflow 
    quickSort(arr, 0, j - 1); 
    delete []arrPtr; 
    } 
}

上述基本的代码创建与j在每匝一个动态分配的阵列大小，这得到由MIN_SIZE（10,000）递增，并且分配一些特定整数每个索引。赋值后，它将与我将在下面提供的快速排序算法分类，然后在完成时释放此数组。这整件事重复到MAX_SIZE（100,000）。

这里是我的快速排序代码：

void quickSort(int *arr, int front, int rear) 
{ 
    if (front < rear) 
    { 
     int part = partition(arr, front, rear); 
     quickSort(arr, front, part - 1); 
     quickSort(arr, part + 1, rear); 
    } 
} 

int partition(int *arr, int front, int rear) 
{ 
    int element = arr[rear]; 
    int i = front - 1; 
    for (int j = front; j<rear; ++j) 
    { 
     if (arr[j] <= element) 
     { 
      ++i; 
      long temp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = temp; 
     } 
    } 
    long temp = arr[i + 1]; 
    arr[i + 1] = arr[rear]; 
    arr[rear] = temp; 
    return i + 1; 
}

我试图实现其严格使用最后一个项目为支点快速排序算法。在这种情况下，我面临着一个奇怪的问题：当我使用rand()函数将数组的每个值赋给一个随机数时，一切正常，但是，当我输入一个常数值时，数组的大小会上升到4039（当你操纵MAX_SIZE和MIN_SIZE时）则给出堆栈溢出错误。我真的很困惑，为什么地球上会引起问题，此外，为什么4039？

来源

2016-02-29 Burak.

检查分区的返回值。我想你有一个运行的方式递归，由于分区返回一个错误的值，导致快速排列整个数组一遍又一遍。 –

这功课吗？如果是这样的话，那么在网络和SO上的快速排序会有很多帮助。否则...使用'vector'和内置的'sort'算法。 10次中有9次会比你写的速度快。 –

当数组中的所有元素都相同时，数组已经被排序，并且如果数组已经排序，那么使用quicksort会导致最坏的情况。 [请参阅此解释]（https://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot）。 –

以直接方式实现时，使用最后一个元素作为主元素的快速排序预计会溢出相同元素的堆栈。这是quicksort的工作原理。这是算法中的一个“缺陷”。

看看为什么看看如何创建递归函数调用。

quicksort(arr, 0, 100) - will produce the recursive calls 
    quicksort(arr, 0, 99); and 
    quicksort(arr, 100, 100);

问题是quicksort(arr, 0, 99);将为数组中的每个元素递归。

在你的情况下，你的堆栈满了4039个元素。您的每个通话似乎都有大约8个整数值，这会给您一个关于您的堆栈最大大小的提示。我猜测大约1 MB。

随机整数的情况并非如此，因为递归调用的深度将均匀分布在递归的左边部分和右边部分之间。这种期望的行为使得递归深度方法记录为N.对于MAX_SIZE，这是大约17的深度，而不是100000.这就是快速排序被描述为N log N算法的原因。第一个N来自分区。

来源

2016-02-29 09:55:20

所以我们不应该使用最后一个元素作为支点，它最终会导致堆栈溢出，然后..在某些情况下......但是当我们使用rand（）或一个简单的常量时会有所不同。当我使用rand（）赋值时，我的程序完美无缺地运行，但是，乍一看，我手动分配的这些常量值在我看来是造成问题的原因。然而，我要告诉你关于你是对的最后一个枢轴缺陷。 –

不要为最大间隔递归，只适用于较小间隔（尾递归优化） – mksteve

@Burak。如果数组包含随机值，则数据透视将不是最后一个元素。 –

一个常量数组，带有一个end-pivot并将数组分成两个结果，递归深度为“数组中的元素数”和O（n^2）时间。

有很多方法可以解决这个问题。

首先，将数组分成3个部分。大于，小于，并且等于来分区。平等之间。这可以修复您遇到的拐角案例。它增加了常数因子，但快速排序成本变为O（n lg m），其中m是作为奖励的不同元素的数量。

排序阵列仍然死亡可怕。做一个更好的部分选择器。随机分区使得接近0的可怕行为的概率。采用3（或2k + 1）个元素（可能是随机的）并使用它们的中值是另一种方法。对于确定性良好行为，在O（n）时间内找到30％到70％标记的元素的算法被称为“中值5”（其不仅取5元素的中值）。

另一个技巧是阵列分区，递归上较小分区，并且在大环。这解决了递归深度问题，但不是运行时问题。

接下来，考虑小阵列长度的逃生策略。快速排序（说）8个元素可能会严重不理想与选择排序相比。一旦你有一个逃生策略，你可以优化使用一个快速和肮脏的快速排序（为枢轴选择3个随机元素等）并跟踪递归深度。如果你通过2 * lg（n）的深度，逃脱到可证实的快速排序（5的中位数找到枢轴）。而当你跌落到8以下（调整这个）elememts，切换到选择排序。

最后，当你只是std::sort时，以上所有和更多可能已经完成。所以用它代替。

来源

2016-02-29 10:27:05 Yakk

关于分区步骤的注释。霍尔在'62年的原始快速排序描述了一个更小和更大的分区的分区步骤。分割元素是分割元素。所以三分区划分不是一个“纯”快速排序。 OP所遇到的问题在论文中被评论为“如果绑定的价值很容易出现尴尬的情况......”。 –

如果您总是先递归到较小的一半并且编译器为第二次调用生成尾递归，那么您可以保证堆栈深度为O(log(N))。

void quickSort(int *arr, int front, int rear) 
{ 
    if (front < rear) 
    { 
     int part = partition(arr, front, rear); 
     int a, b, c, d; 
     if (part - front <= rear - part) 
     { 
      a = front; 
      b = part - 1; 
      c = part + 1; 
      d = rear; 
     } 
     else 
     { 
      a = part + 1; 
      b = rear; 
      c = front; 
      d = part - 1; 
     } 
     quickSort(arr, a, b); 
     quickSort(arr, c, d); 
    } 
}

来源

2016-02-29 10:32:03 piotrekg2

快速排序为常数提供stackoverflow但不是随机数

回答

相关问题