Как можна изменить сортировку подсчетом

Question

void CountingSort(int *a, int *c, int n, int k)
{
    for (int i = 0; i < k; i++) {
        c[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        c[a[i]] = c[a[i]] + 1;
    }
    int i = 0;
    for (int j = 0; j < k; j++) {
        while (c[j] != 0) {
            a[i] = j;
            c[j]--;
            i++;
        }
    }
}

Здравствуйте, извиняюсь что всех беспокою, но вот возник вопрос, написал данную функцию, и хочется как-то ее изменить в лучшую сторону, может кто-то поможет буду благодарен

Answer 1

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

поиск минимума :

void CountingSort(int *a, int *c, int n, int k)
{
    int min = 0 ;
    if (n)
      min = a[0];
    for (int i = 1; i < n; i++)
       if(a[i] < min)
         min = a[i]; 

...

    }

дальше уже работать со счётчиком, но со сдвинутым индексом.

...
for (int i = 0; i < n; i++) {
    ++ c[a[i] - min] ;
    }
    int i = 0;
    for (int j = 0; j < k; j++) {
        while (c[j] != 0) {
            a[i] = j + min;
            c[j]--;
            i++;
        }
    }
...

Если диапазон данных заранее не известен и/или данные подсчёта далее не нужны, то нужно опять посчитать этот диапазон и выделить память.

void CountingSort(int *a, int n)
{
  int *c ;
  int k ;
    int min = 0 ;
    int max = 0 ;
    if (n) {
      min = a[0];
      max = a[0];  }
    for (int i = 1; i < n; i++) {
       if(a[i] < min)
         min = a[i];
       if(a[i] > max)
         max = a[i]; }

k = max - min + 1 ;
c = new int [ k ] ;
...

И не забываем потом освобождать память :

delete [ ] c ;

БЛОГ НА HUSL

Как можна изменить сортировку подсчетом

Ответы (1 шт):