Hello, I am trying to read a file of more than 1 million ints and use counting sort to sort it (I'm aware this is going to be extremely slow). I don't know how many ints are in the file to begin with so I read all the ints into a string and keep a count. However when I try to use that big of a number to allocate an array, it will not compile. I've googled how to get around this and found that if I use a pointer it will allocate space on the heap instead of the stack but I can't figure out how to use the pointer to place the values into the new array.
void print(int a[], int size) {
for (int i = 0; i < size; i++ )
cout << a[i] << endl;
}
int CountingSort(int *A,int size) {
int range = 65536;
int B[size], C[range];
int i, j, k, z;
// set auxiliary array to 0
for(i = 0; i < range+1; i++)
C[i] = 0;
// set value of C[i] to number of elements in array with value i+1
for(i = 0; i < size; i++)
{
z = A[i] + 1 - 0;
C[z]++;
}
// update C[i] to contain number of values less than i-1
for(i = 1; i <= range; i++)
C[i] += C[i - 1];
// sort array, giving each element its own position
for(i=(size-1); i >= 0; i--)
{
j = A[i]-0;
k = C[j];
B[k] = A[i];
C[j]++;
}
// copy array over
for(i=0; i < size; i++)
A[i] = B[i];
print(A, size);
}
int main()
{
int Size = 0;
ifstream input("integersToSort.txt");
if(!input)
{
// Print an error and exit
cerr << "File read error!" << endl;
exit(1);
}
// count number of ints in file
int i = 1;
string sortStr = "";
while(!input.eof())
{
input >> sortStr;
Size = i;
i++;
}
input.close();
cout << "Size = " << Size << endl;
int *sortPtr = newint[Size];
//This is where I'm unsure how to go about putting the values into the array.
//I had to open the file and read it twice because when just trying to get
//the counting sort part of my program working I used numbersToSort[] and
//used the Size I got from the previous read. But using a pointer is proving
//to be an entirely different beast.
// int numbersToSort[] = sortPtr;
// ifstream input2("integersToSort.txt");
// if(!input2)
// {
// // Print an error and exit
// cerr << "File read error!" << endl;
// exit(1);
// }
//
// int h = 0;
// while(!input2.eof())
// {
// input2 >> sortPtr;
// h++;
// }
// input2.close();
CountingSort(sortPtr, Size); // show sorted array
free(sortPtr);
return 0;
}
You can't create an array on the stack whose size is a variable or depends on values that exist only at run time. Counting sort only needs a single auxiliary array, anyway, so you can simply get rid of B.