Подсчет Сортировка Мой вход 1,4,3,1 Но выход - значение мусора, 1,1,3 Ввод неправильный

Question

#include<stdio.h>    
#include<stdlib.h> 

main() 
{ 
    int A[200],p=0,r=0,s=0,i,n,temp=0,B[200]; 
    printf("Enter no. of Element for counting sort :"); 
    scanf("%d",&n); 
    for(i=0;i<n;i++) 
     scanf("%d",&A[i]); 

    printf("\nBefore Sorting: "); 

    for(i=0;i<n;i++) 
     printf("%d ",A[i]); 

    printf("\n"); 

    for(i=0;i<n;i++) 
    { 
     if(A[i]>temp) 
      temp=A[i]; 
    } 

    printf("\nLargest %d \n",temp); 

    counting_sort(A,B,n,temp); 

    for(i=0;i<n;i++) 
     printf("%d ",B[i]); 

    printf("\n"); 
} 


counting_sort(int A[],int B[],int n,int temp) 
{ 
    int i=0,C[200],j; 
    for(i=0;i<=temp;i++) 
     C[i]=0; 

    for(i=0;i<n;i++) 
     C[A[i]]=C[A[i]]+1; 

    for(i=1;i<=temp;i++) 
     C[i]=C[i]+C[i-1]; 

    for(i=n-1;i>=0;i--) 
    { 
     B[C[A[i]]]=A[i]; 
     C[A[i]]=C[A[i]]-1; 
    } 
} 

Answer 1

Хорошо, карандаш-бумага. Ваш вход:

A = {1, 4, 3, 1} 

Ваш подсчет определяются правильно:

C' = {0, 2, 0, 1, 1} 

Вы затем превратить это в накопившихся подсчетов:

C = {0, 2, 2, 3, 4} 

Этот шаг тоже правильно. Что представляет этот массив? Для каждого элемента a в A, C[a] является индексом элемента после того, как все a с в отсортированном массиве, B:

i  0 1 2 3 4 
B[i] 1 1 3 4 < 

То же самое справедливо и для элементов, не в A: C[2] равно 2. Существует (мнимый) блок нулевых двоек после них индекс после этого блока 2.

Поскольку индекс является индексом после блока, вы должны уменьшать свой индекс, прежде чем использовать его:

for (i = n - 1; i >= 0; i--) { 
    C[A[i]] = C[A[i]] - 1; 
    B[C[A[i]]] = A[i]; 
} 

В противном случае вы будете писать в индекс 4 в конце концов, когда будете обрабатывать элемент 4, но этот индекс является одним из пределов вашего массива. (Числа, которые вы видели, были всего лишь мусором из неинициализированных элементов в B.)

Кстати, при первом уменьшении числа отсчетов часто происходит C, что связано с тем, что верхние границы массивов являются исключительными. Ваш цикл может быть записан следующим образом:

for (i = n; i-- > 0;) { 
    C[A[i]] = C[A[i]] - 1; 
    B[C[A[i]]] = A[i]; 
} 

Обновление части отсутствует, так как декремент происходит до того, как вошло в теле цикла. И вы уходите, не вычитая его в инициализации.