RadixSort - поразрядная сортировка
Описание:
Сам алгоритм работает так (кто знает, что такое
mod, тот разберется):
Открыть/закрыть.
Сам алгоритм был переписан с С++ (т.к я не думаю, что алгоритм получился бы не идентичным).
Временная сложность (скрины взяты с хабры)
Параметры:
arr[] - массив, который нужен отсортировать.
size - размер массива (необязательный параметр)
Возвращаемое значение:
arr - отсортированный массив
Код:
PHP код:
#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);
}
Пример использования:
PHP код:
#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
