1

This question is about sorting with the array container in c++. I am doing some comparisons of sort code. I have a bubble sort and an array container in c++ in Mac Xcode. The task is to build an array of random numbers and then sort those numbers and see how long it takes for the sort to be completed. The bubble sort requires 59 seconds for 100,000 random numbers and 6,086 seconds for 1,000,000 random numbers. I have not asked the bubble sort to try more than a million numbers. The array container requires one second for 100,000 random numbers and fails at run time when presented with an array size of a million random numbers. The failure occurs just inside main{...}, before any other statements are processed. The first statement inside main, is a simple cout << "this is a test of sorts \n";

In Xcode, the error message is: Thread1: EXC_BAD_ACCESS(code=2, address=0xfff5ecbd258)

The applicable code statements are shown below.

Note that I retyped the code here, so a typo is possible. I hope the basic idea is complete enough for you to see what is going on. 

#define ARRAY_SIZE 1000000
#include <iterator>
#include <array>

The following code is inside main

std::array<double, ARRAY_SIZE> A1 = {0};

// Here, I have some code that fills array A1 with random numbers using the rand() function

std::sort(A1.begin(), A1.end());

// some code that prints a selection of the A1 array.

My question is... is there an upper limit for the array container? if there is, how can I know what it is, and is there a work_around? The max_size statement simply returns the size handed to the array by the #define statement.

Is there a better, faster, way to sort a million items?

Thank you.

K17
  • 697
  • 3
  • 8
  • 26
  • Some interesting answers on sorting algorithms here: http://cs.stackexchange.com/questions/3/why-is-quicksort-better-than-other-sorting-algorithms-in-practice – Robinson Jul 26 '15 at 19:22

2 Answers2

5

If it's a global variable, then it's most likely only limited by the amount of memory your process can use [in other words, how much memory your machine has, and that the OS lets the process have, whichever is lower].

If it's a local variable inside a function (and the "bad access" seen in your error message indicates that this is case, but it's not clear from your code samples), since std::array takes space on the stack, the limit is whatever your stack-size is. If you want a LOCAL variable to hold a lot of items, use std::vector, which will dynamically allocate, and then becomes limited by the amount of memory in your machine [as per above].

There are many other ways to solve this problem, but std::vector<double> A1(ARRAY_SIZE); is the simplest version, and it will only require one single call to new double[ARRAY_SIZE]; which is likely to not be noticeable in your overall run time if you fill and sort the contents of 1 million entries.

Mats Petersson
  • 126,704
  • 14
  • 140
  • 227
  • Or if for some reason it must be an `std::array` you can declare it `static` (but note that this has additional side-effects) or allocate it on the heap: `std::unique_ptr> arr_ptr(new std::array>);`. This'll be a bit harder to access, though. (Maybe put it in a reference as well? `std::array& arr = *arr_ptr;`) – celticminstrel Jul 26 '15 at 19:10
  • Yes, there ARE other plausible ways to solve it. But most likely the OP is beginner, and don't really need/want those extra options... – Mats Petersson Jul 26 '15 at 19:12
4

For std::array it is the same as for ordinary C arrays, so look here.

Community
  • 1
  • 1
stgatilov
  • 5,333
  • 31
  • 54