RadixSort - поразрядная сортировка

[$continue$]

Описание:


Сам алгоритм работает так (кто знает, что такое mod (https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81_ %D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BA%D0%BE%D0%BC), тот разберется):

https://www.youtube.com/watch?v=xhr26ia4k38.
Сам алгоритм был переписан с С++ (т.к я не думаю, что алгоритм получился бы не идентичным).


https://hsto.org/getpro/habr/post_images/3da/386/eed/3da386eed54c16ff73b647b383aea085.png
https://hsto.org/getpro/habr/post_images/b91/1bc/ca9/b911bcca9ca9f9d8b0fa781a49118553.png



Параметры:

arr[] - массив, который нужен отсортировать.
size - размер массива (необязательный параметр)


Возвращаемое значение:

arr - отсортированный массив


Код:


#if !defined MAX_SIZE_ARRAY_SORT
#define MAX_SIZE_ARRAY_SORT 1000
#endif

stock GetMaxValue(arr[], size = sizeof(arr), &index=-1)
{
new max_arr = arr[0];
for (new i = 1; i < size; i++)
{
if (arr[i] > max_arr)
{
max_arr = arr[i];
index = i;
}
}
return max_arr;
}
stock CountSort(arr[], size = sizeof(arr), exp)
{
new output[MAX_SIZE_ARRAY_SORT]; // костыль из не возможности dynamic memory
new i, count[10];
for (i = 0; i < size; i++)
count[(arr[i] / exp) %10] ++;

for (i = 1; i < 10; i++)
count[i] += count[i - 1];

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

for (i = 0; i < size; i++)
arr[i] = output[i];
}
stock RadixSort(arr[], size = sizeof(arr))
{
new max_val = GetMaxValue(arr, size);
for (new exp = 1; max_val / exp > 0; exp *= 10)
CountSort(arr, size, exp);
}

Пример использования:


#include <radix_sort>
main()
{
new arr[] = { 2, 4, 8, 12, 16, 20, 30, 40, 15, 14, 16, 200 };
RadixSort(arr);
for(new i = 0; i < sizeof(arr); i++)
printf("Index: %d | value: %d", i, arr[i]);
printf("max value in array: %d", arr[sizeof(arr) - 1]);
}

Готовая библиотека для использования: download (https://gist.github.com/continue98/801b69d8958450049888c49a73608670/archive/7b76d296b389dae8b8b4ae73ad66b3452eea1ef8.zip)

[Pa4enka]

Зачем в функции getMaxValue аргумент index?

[$continue$]

Чтобы вернуть индекс до сортировки в котором максимальное значение

Зачем в функции getMaxValue аргумент index?

[DeimoS]

main()
{
new arr[] = { 2, 4, 8, 12, 16, 20, 30, 40, 15, 14, 16, 200 };
RadixSort(arr);
for(new i = 0; i < sizeof(arr); i++)
printf("Index: %d | value: %d", i, arr[i])// Нет точки с запятой
printf("max value in array: %d", arr[sizeof(arr) - 1]);
}

[$continue$]

Доберусь до ПК - скомпилирую код, кроме того название вспомогательных функции нужно сделать в стиле CamelCase

[$continue$]

Обновлено.

Исправлены ошибки с компиляцией
Добавлена готовая библиотека

[Geebrox]

Думаю стоит добавить проверку на то, что имеется ли функция GetMaxValue, возможно это название используется не только в этом инклюде, или добавить тег