c - 程序执行终止于代码块

Question

我编写了一个程序来测量快速排序的执行时间，并使用代码块来编译和运行它。当我输入一组随机数字时，我的程序对于任何大小的数据都运行良好。但是，当我尝试输入按升序/降序排序的数字集时，我的程序因大数据集 (>35000) 而终止，表示程序已停止工作。

同样的代码在 Linux 上运行良好。但是在 Linux 上，我无法使用 QueryPerformanceCounter() 来测量时间。所以我必须在 Windows 上使用代码块。

#include<stdio.h>
#include<windows.h>
double PCFreq = 0.0;
__int64 CounterStart = 0;

void StartCounter()
{
    LARGE_INTEGER li;
    if(!QueryPerformanceFrequency(&li))
    printf("QueryPerformanceFrequency failed!\n");

    PCFreq = (double)li.QuadPart;

    QueryPerformanceCounter(&li);
    CounterStart = li.QuadPart;
}
double GetCounter()
{
    LARGE_INTEGER li;
    QueryPerformanceCounter(&li);
    return (double)(li.QuadPart-CounterStart)/PCFreq;
}
int part(int a[],int low,int high)
{
    int pivot,i,j,temp;
    pivot=low;
    i=low+1;
    j=high;
    while(i<=j)
    {
        while(a[i]<=a[pivot])
            i++;
        while(a[j]>a[pivot])
            j--;
        if(i<j)
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
    temp=a[j];
    a[j]=a[pivot];
    a[pivot]=temp;
    return j;
}
void QuickSort(int a[],int first,int last)
{
    int q;
    if(first<last)
    {
        q=part(a,first,last);
        QuickSort(a,first,q-1);
        QuickSort(a,q+1,last);
    }
}

int main()
{
    int n,a[100000],i;
    printf("Enter the size of array:");
    scanf("%d",&n);
    for(i=0;i<n;i++)
        //a[i]=rand()%100000;   //average case (random data)
        a[i]=i;                 //ascending sorted input
        //a[i]=n-1-i;           //descending sorted input
    /*
    printf("The UNsorted array is:\n");
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    printf("\n\n");
    */

    StartCounter();
    QuickSort(a,0,n-1);
    printf("Sorting time %lf micro seconds\n",GetCounter()*1000000.0);

    /*
    printf("\nThe sorted array is:\n");
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
    */
    return 0;
}

我收到以下错误

Answer 1

如果我在 Linux 上使用 clock(3)(足以进行快速测试的分辨率)，它可以达到并包括 100000 的固定限制。为了避免这个固定限制，我在下面的草图中使用了 malloc() 来动态保留内存(对结果没有影响，我只是想把它放在堆上而不是堆栈上)

#include <time.h>
#include <stdlib.h>
    // ALL CHECKS OMMITTED!
int main()
{
    int n,*a,i;
    clock_t start, stop;
    printf("Enter the size of array:");
    scanf("%d",&n);
    a = malloc(sizeof(int) * n);

    for(i=0;i<n;i++)
        //a[i]=rand()%100000;   //average case (random data)
        a[i]=i;                 //ascending sorted input
        //a[i]=n-1-i;           //descending sorted input
    /*
    printf("The UNsorted array is:\n");
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    printf("\n\n");
    */

    start = clock();
    QuickSort(a,0,n-1);
    stop = clock();
    printf("Sorting time %f seconds\n", (double)(stop- start)/CLOCKS_PER_SEC);
    /*
    printf("\nThe sorted array is:\n");
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
    */
    free(a);
    return 0;
}

升序数组条目:100,000 个条目和 100 万个条目需要 11 秒......一个段错误位于

QuickSort (a=0x7ffff7ee3010, first=174677, last=199999)

(可重复) 我认为递归只是有点太深了(这里的堆栈大小:8 兆，符合 180,00 次调用，带有两个整数和一个指针以及一些开销)。

所以:这里实际上没有错。

编辑 为了证明它确实是堆栈，让我们增加它:

#include <time.h>
#include <stdlib.h>
#include <sys/resource.h>
    // ALL CHECKS OMMITTED!
int main()
{
  int n, *a, i;
  clock_t start, stop;
  // 256 MB
  const rlim_t bigger_stack = 256L * 1024L * 1024L;
  struct rlimit rlim;
  int ret_set, ret_get;

  ret_get = getrlimit(RLIMIT_STACK, &rlim);
  fprintf(stderr, "get %d %d %d\n", ret_get, (int) rlim.rlim_max,
      (int) bigger_stack);
  if (ret_get == 0) {
    if (rlim.rlim_cur < bigger_stack) {
      rlim.rlim_cur = bigger_stack;
      ret_set = setrlimit(RLIMIT_STACK, &rlim);
      if (ret_set != 0) {
    fprintf(stderr, "getrlimit %d, setrlimit %d\n", ret_get, ret_set);
      }
    }
  }



  printf("Enter the size of array:");
  scanf("%d", &n);
  a = malloc(sizeof(int) * n);

  for (i = 0; i < n; i++)
    //a[i]=rand()%100000;   //average case (random data)
    a[i] = i;           //ascending sorted input
  //a[i]=n-1-i;           //descending sorted input
  /*
   * printf("The UNsorted array is:\n");
   * for(i=0;i<n;i++)
   * printf("%d ",a[i]);
   * printf("\n\n");
   */

  start = clock();
  QuickSort(a, 0, n - 1);
  stop = clock();
  printf("Sorting time %f seconds\n", (double) (stop - start) / CLOCKS_PER_SEC);
  /*
   * printf("\nThe sorted array is:\n");
   * for(i=0;i<n;i++)
   * printf("%d ",a[i]);
   * printf("\n");
   */
  free(a);
  return 0;
}

检查了 200,000 个元素:工作于 ca。 47 秒。