Counting sort on Int array of 1 million+

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.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
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 = new int[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.
Last edited on
Topic archived. No new replies allowed.