Считать сортировку с отрицательными целыми числами?

Question

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

вот что у меня есть ( ошибка сегментации ):

void counting_sort(int *vet, int max, int min, int n){

  int i, j, C[(max-min)+1], B[n];

  for (i=0;i<=max;i++){
    C[i]=0;
  }

  for (i=0;i<n;i++){
    C[vet[i]-min]++;
  }

  for (i=1;i<=(max-min);i++){
    C[i]=C[i]+C[i-1];
  }

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

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

Answer 1

Этот цикл выглядит так, как будто в нем есть ошибка "один на один":

for (i=1;i<=(max-min+1);i++){
    C[i]=C[i]+C[i-1];
}

Обратите внимание, что в массиве C содержится max - min + 1 элемент, поэтому, если вы выполняете итерацию до и включаете index max - min + 1, вы записываете конец массива.

Здесь могут быть и другие проблемы, но я бы начал с этого.

Answer 2

Вы можете изменить это для сортировки в прямом порядке:

    int i, j, C[(max-min)+2], B[n];   // ...+2...
    for (i=0;i<=(max-min)+1;i++){     // ...+1...
        C[i]=0;
    }
    for (i=0;i<n;i++){
        C[vet[i]+1-min]++;            // ...+1...
    }
    for (i=2;i<=(max-min);i++){       // i = 2
        C[i]+=C[i-1];
    }
    for (i=0;i<n;i++){                // 0 to n-1 sort
        B[C[vet[i]-min]++]=vet[i];
    }

Answer 3

Я не знаю, что является причиной ошибки сегментации, но если вы хотите отсортировать отрицательные числа с помощью сортировки подсчетом, вам просто нужно найти самое низкое отрицательное число в массиве и добавить абсолютное значение ко всем значениям временного массива. После этого используйте алгоритм сортировки обычного подсчета для сортировки массива, а затем вычтите самое низкое минимальное значение из каждого числа в полученном массиве.

---

Добавление / вычитание числа из всех элементов массива не влияет на результат сортировки.