Sorting 2 millions numbers in C++

Question

im trying to write a code compare the time between sorting algorithms in c++. My code works perfectly when the numbers of integers is 100000 and 500000. However, when i increase the number into 2000000, it crashed. After googling, i tried to put my numbers in the heap by declaring an array:

int* array = new int[N];

I've tested and this array can contain that 2 millions integers but my code still crashed when im trying to put them in to my sorting algorithms.Here is the code:

    #include <string>
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <iostream>
    #include <fstream>
    #include <iomanip>

    #define N  2000000

 using namespace std;

void HeapDown(int a[] , int k, int N1) 
{ 
 int j; 
 int temp;
 while (2*k <= N1) 
 { 
  j = 2*k; 
  if (j < N1 && (a[j] < a[j+1])) j++; 
    if (!(a[k]<a[j])) break;  
    temp = a[k];
    a[k]=a[j];
    a[j]=temp;
  k = j ; 
 } 
} 

#define pq(A) a[l-1+A] 
void heapsort(int a[], int l, int r) 
{ 
 int temp;
  int k, N2 = r-l+1; 
 for (k = N2/2; k >= 1; k--) 
   HeapDown(&pq(0), k, N2); 
 while (N2 > 1) 
  { 

    temp = pq(1);
    pq(1)=pq(N2);
    pq(N2)=temp; 
    HeapDown(&pq(0), 1,--N2); 
  } 
  cout << "The sequence was sorted by heap sort" << endl; 
} 

int main(){

    int i;
    static int a[N];
    clock_t start;
    clock_t end;
    int* array = new int[N];

/* Generate random numbers and put them in the text file  */
//  ofstream myfile;
//      myfile.open ("2000000.txt");
//      
//  for (i=0; i < N; i++){
//      a[i] = 1000*(1.0*rand()/RAND_MAX);
//  //  printf("%3d ",a[i]);
//      myfile << a[i] << endl;
//      
//      }
//      cout << "done!" << endl;
//  myfile.close();
/*                                                      */


/******************* Open file and add the numbers into array **************************/   
    string line;
  ifstream myfile2 ("2000000.txt");
  if (myfile2.is_open())
  {
    i = 0;
    while ( getline (myfile2,line) )
    {
 //     a[i] = atoi(line.c_str());
        array[i] = atoi(line.c_str());
//      cout << a[i] << endl;
//          cout << line << '\n';
        i++;
    }
    myfile2.close();
  }

  else cout << "Unable to open file"; 
/*                                                                                      */  

//for (i=0; i< N; i++){
//      printf("%3d ",array[i]);
//  }

/* Chose the sorting algorithms and calculate the time */

    start = clock();

//  insertionSort(array, 0, N-1);
//  selectionSort(array, 0 , N-1);  
//  bubbleSort (array, N);
//  shellSort (array, N);
//  quicksort (array , 0, N-1);
//  usequicksort (array , 0, N-1);
    heapsort (array , 0 , N-1);
//  radixsort (array , N);

    end = clock();
    double rs = end - start;
    delete[] array;

// print out the sorted sequence and time consuming

//      printf("\n The sequence after sorted \n");  
    for (i=0; i< N; i++){
        printf("%3d ",a[i]);
    }

    cout << "Time consuming: " <<  rs << endl;

    return 0;
}

I think the problem is when i put the array into my sorting function. Unfortunately, i cant find a solution for this. It would be tremendous if you guys could help me out, thank a ton

Answer 1

Here are a couple of hints that may help you going forward.

First, use the standard containers and algorithms as much as possible. It massively reduces the changes of a bug.

Second, no need to store your random numbers in a file. If you provide the generator with the same seed each time, you'll get the same pseudo-random sequence.

Here's an example of how I might approach it.

You might find it a useful framework for comparing your various sorting algorithms:

#include <iostream>
#include <random>
#include <vector>
#include <algorithm>
#include <chrono>

auto main() -> int
{
    using namespace std;

    // make the test space big enough to defeat artificial cacheing gains.
    vector<int> v(20000000);

    auto genstart = chrono::high_resolution_clock::now();

    // use a known seed to force the same random sequence for each test
    generate(begin(v),
             end(v),
             std::bind(uniform_int_distribution<>(0, 999999),
                       default_random_engine(0)));


    auto start = chrono::high_resolution_clock::now();
    sort(begin(v), end(v));
    auto finish = chrono::high_resolution_clock::now();

    auto genduration = chrono::duration_cast<chrono::milliseconds>(start - genstart).count();
    auto duration = chrono::duration_cast<chrono::milliseconds>(finish - start).count();

    // sort time should be in the order of twice the generation time
    cout << "generation took " << genduration << "ms" << endl;
    cout << "sort took " << duration << "ms" << endl;

    return 0;
}

example output:

generation took 801ms
sort took 1556ms

Answer 2

Your code is fine (didn't check the algorithm - fine 'crash wise', except for one thing - You don't check if your new succeeds.
As @jonathan-potter said, it will throw an exception if you don't have enough memory.