Как работают функции?

Question

Не могли бы вы объяснить мне, как работают следующие два алгоритма?

int countSort(int arr[], int n, int exp) 
{ 
    int output[n]; 
    int i, count[n] ; 
    for (int i=0; i < n; i++) 
     count[i] = 0; 
    for (i = 0; i < n; i++) 
     count[ (arr[i]/exp)%n ]++; 
    for (i = 1; i < n; i++) 
     count[i] += count[i - 1]; 
    for (i = n - 1; i >= 0; i--) 
    { 
     output[count[ (arr[i]/exp)%n] - 1] = arr[i]; 
     count[(arr[i]/exp)%n]--; 
    } 
    for (i = 0; i < n; i++) 
     arr[i] = output[i]; 
} 


void sort(int arr[], int n) 
{ 
    countSort(arr, n, 1); 
    countSort(arr, n, n); 
} 

Я хотел применить алгоритм в этом массиве:

После вызова функции countSort (обр, п, 1), мы получаем следующее:

Когда я вызываю тогда функцию countSort (arr, n, n), в этом цикле for:

for (i = n - 1; i >= 0; i--) 
{ 
    output[count[ (arr[i]/exp)%n] - 1] = arr[i]; 
    count[(arr[i]/exp)%n]--; 
} 

Я получаю выход [-1] = arr [4].

Но массив не имеет такой позиции ...

ли я сделал что-то не так?

РЕДАКТИРОВАТЬ: Учитывая массив обр [] = {10, 6, 8, 2, 3}, граф массив будет содержать следующие элементы:

, что эти цифры представляют ? Как мы их используем?

Answer 1

Counting сортировки очень просто - скажем, у вас есть массив, который содержит номера из диапазона 1..3:
[3,1,2,3,1,1,3,1,2]

Вы можете подсчитать, сколько раз каждое число встречается в массиве:
count[1] = 4
count[2] = 2
count[3] = 3

Теперь вы знаете, что в сортированном массиве
номер 1 будут занимать позиции 0..3 (от 0 до count[1] - 1), а затем
числа 2 на позиции 4..5 (от count[1] до count[1] + count[2] - 1), а затем
числа 3 на позиции 6..8 (от count[1] + count[2] до count[1] + count[2] + count[3] - 1).

Теперь, когда вы знаете конечную позицию каждого номера, вы можете просто вставить каждое число в правильное положение. Это в основном то, что делает countSort функция.

Однако в реальной жизни ваш входной массив не будет содержать только цифры из диапазона 1..3, поэтому решение состоит в том, чтобы сначала сортировать номера по наименьшей значащей цифре (LSD), затем LSD-1 ... до самых значительных цифра.
Таким образом, вы можете сортировать большие числа, сортируя числа из диапазона 0..9 (одноразрядный диапазон в десятичной системе цифр).
Этот код: (arr[i]/exp)%n в countSort используется только для получения этих цифр.n - это основание вашей системы цифр, поэтому для десятичного кода вы должны использовать n = 10, а exp следует начинать с 1 и умножаться на базу на каждой итерации, чтобы получить последовательные цифры.
Например, если мы хотим получить третью цифру с правой стороны, мы используем n = 10 и exp = 10^2:
x = 1234, (x/exp)%n = 2.

Этот алгоритм называется Radix рода и подробно объясняется в Википедии: http://en.wikipedia.org/wiki/Radix_sort

Answer 2

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

В вашей функции countSort размер вашего count был неправильным. Он должен быть размером base, в данном случае 10. (у вас было 5) Вы путали использование exp и base всей функции. Переменная exp проходит через полномочия 10, позволяя вам получить значение и положение каждого элемента в массиве в сочетании с операцией modulo base. Вместо этого у вас было modulo n. Эта проблема также пронизала диапазоны циклов, где у вас было несколько индексов циклов, итерация которых превышала 0 < n, где правильный диапазон был 0 < base.

Вы пропустили поиск максимального значения в исходном массиве, который затем используется для предела числа проходов через массив для выполнения сортировки. Фактически все ваши существующие петли в countSort должны попадать внутрь цикла итерации while (m/exp > 0). Наконец, вы опустили приращение exp в пределах внешнего цикла, необходимого для применения сортировки к каждому элементу массива. Наверное, вы просто запутались, но я рекомендую вам попытаться переписать процедуру сортировки, а не просто скопировать/вставить из другого места. (возможно, вы скопировали/вставляли, но если это так, у вас есть дополнительные проблемы ...)

С каждой из этих проблем сортировка работает. Посмотрите хотя бы изменения и понять, что он делает. radix sort/count sort - это distribution sorts, полагаясь на то, где числа встречаются и обрабатывают индексы, а не сравнивают значения друг с другом, что делает этот тип рода неудобным для понимания вначале. Дайте знать, если у вас появятся вопросы. Я попытался сохранить ваше соглашение об именах во всей функции, добавив пару, которая была опущена, и предотвратить жесткое кодирование 10 в качестве базы.

#include <stdio.h> 

void prnarray (int *a, int sz); 

void countSort (int arr[], int n, int base) 
{ 
    int exp = 1; 
    int m = arr[0]; 
    int output[n]; 
    int count[base]; 
    int i; 

    for (i = 1; i < n; i++)     /* find the maximum value   */ 
     m = (arr[i] > m) ? arr[i] : m; 

    while (m/exp > 0) 
    { 
     for (i = 0; i < base; i++) 
      count[i] = 0;     /* zero bucket array (count)  */ 

     for (i = 0; i < n; i++) 
      count[ (arr[i]/exp) % base ]++; /* count keys to go in each bucket */ 

     for (i = 1; i < base; i++)   /* indexes after end of each bucket */ 
      count[i] += count[i - 1]; 

     for (i = n - 1; i >= 0; i--)  /* map bucket indexes to keys  */ 
     { 
      output[count[ (arr[i]/exp) % base] - 1] = arr[i]; 
      count[(arr[i]/exp)%n]--; 
     } 

     for (i = 0; i < n; i++)    /* fill array with sorted output */ 
      arr[i] = output[i]; 

     exp *= base;      /* inc exp for next group of keys */ 
    }  
} 

int main (void) { 

    int arr[] = { 10, 6, 8, 2, 3 }; 
    int n = 5; 
    int base = 10; 

    printf ("\n The original array is:\n\n"); 
    prnarray (arr, n); 

    countSort (arr, n, base); 

    printf ("\n The sorted array is\n\n"); 
    prnarray (arr, n); 

    printf ("\n"); 

    return 0; 
} 

void prnarray (int *a, int sz) 
{ 
    register int i; 
    printf (" ["); 
    for (i = 0; i < sz; i++) 
     printf (" %d", a[i]); 
    printf (" ]\n"); 
} 

выход:

$ ./bin/sort_count 

The original array is: 

    [ 10 6 8 2 3 ] 

The sorted array is 

    [ 2 3 6 8 10 ]