when I trying to implement the counting sort I got this error " the problem caused the program to stop working correctly Windows will close the program and notify you if a solution is available "
void CountingSort(int *A,int size) {
int SizeC = Max(A, size);
int* B = new int[size];
int* C = new int[SizeC+1];
for (int i = 0; i < SizeC; i++) {
C[i] = 0;
}
for (int i = 0; i < size; i++) {
C[A[i]]++ ;
}
for (int i = 0; i <SizeC; i++)
{
C[i] += C[i - 1];
}
for (int j = size - 1; j >= 0; j--) {
B[C[A[j]]] = A[j];
C[A[j]] --;
}
for (int i = 0; i < size; i++) {
cout << B[i] << "\t" << endl;
}
delete[] C;
delete[] B;
}
i < SizeC and i <SizeC should be i <= SizeC. Otherwise, the elements with value SizeC won't be treated properly.C[i] += C[i - 1]; with i = 0 will result in out-of-range read of C[-1]. The initialization of corresponding for loop should be int i = 1, not int i = 0.C[A[j]] --; should happen before B[C[A[j]]] = A[j];, or out-of-range write of B[size] will happen.A contains negative values.Fixed code (negative values are still not supported):
void CountingSort(int *A,int size) {
int SizeC = Max(A, size);
int* B = new int[size];
int* C = new int[SizeC+1];
for (int i = 0; i <= SizeC; i++) {
C[i] = 0;
}
for (int i = 0; i < size; i++) {
C[A[i]]++ ;
}
for (int i = 1; i <= SizeC; i++)
{
C[i] += C[i - 1];
}
for (int j = size - 1; j >= 0; j--) {
C[A[j]] --;
B[C[A[j]]] = A[j];
}
for (int i = 0; i < size; i++) {
cout << B[i] << "\t" << endl;
}
delete[] C;
delete[] B;
}