Program execution terminates in Code Blocks

Question

I have written a program to measure execution time of quick sort and am using Code Blocks to compile and run it. When I input random set of numbers my program runs well for any size of data. But when I try to input ascending/descending sorted set of numbers, my program terminates for large data set (>35000) saying program stopped working.

This same code runs well on linux. But on linux I am not able to measure time using QueryPerformanceCounter(). So I have to use Code Blocks on 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;
}

I am getting following error

Answer 1

If I use clock(3) (sufficient resolution for a quick test) on Linux it works up to and including the fixed limit of 100000. To avoid that fixed limit I used malloc() to reserve the memory dynamically in the following sketch (doesn't make a difference in the outcome, I just wanted to put it on the heap instead of the stack)

#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;
}

Ascending array entries: 11 seconds for 100,000 entries and for a million…a segfaulta at

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

(repeatable) I think the recursion is just a wee bit too deep (stack size here: 8 megs which goes accord for 180,00 calls with two ints and a pointer and some overhead).

So: nothing actually wrong here.

EDIT To show that it is indeed the stack lets increase it:

#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;
}

Checked with 200,000 elements: works in ca. 47 seconds.