Упражнения на языке C: алгоритм сортировки по Radix

Алгоритм поиска и сортировки при программировании на C: упражнение 8 с решением

Напишите программу на C для сортировки списка элементов, используя алгоритм сортировки radix.

Замечания:
Radix sort - это не сравнительный алгоритм целочисленной сортировки, который сортирует данные по целочисленным ключам путем группировки ключей по отдельным цифрам, которые имеют одинаковые значимые позиции и значения.

Пример решения:

Образец кода C:

#include  <stdio.h>
  
  int print(int *a, int n) {
  int i;
  for (i = 0; i < n;  i++)
  printf("%d\t", a[i]);
  }
  
  void radix_sort(int *a, int n) {
  int i, b[10], m = 0,  exp = 1;
  for (i = 0; i < n;  i++) {
  if (a[i] > m)
  m = a[i];
  }
  
  while (m / exp >  0) {
  int box[10] = { 0 };
  for (i = 0; i <  n; i++)
  box[a[i] / exp %  10]++;
  for (i = 1; i <  10; i++)
  box[i] += box[i -  1];
  for (i = n - 1; i  >= 0; i--)
  b[--box[a[i] / exp  % 10]] = a[i];
  for (i = 0; i <  n; i++)
  a[i] = b[i];
  exp *= 10;
  }
  }
  
  int main() {
  int arr[10];
  int i, num;
  
  printf("Input  number of elements: ");
  scanf("%d",  &num);
  
  printf("\nInput  array elements one by one : ");
  for (i = 0; i <  num; i++)
  scanf("%d", &arr[i]);
  
  printf("\nArray  elements : ");
  print(&arr[0],  num);
  
  radix_sort(&arr[0], num);
  
  printf("\nSorted  elements : ");
  print(&arr[0],  num);
  
  return 0;
  }

Пример ввода:

 3
12
15
56

Выход:

 Введите количество элементов: 
Входные элементы массива один за другим: 
Элементы массива: 12 15 56	
Сортированные элементы: 12 15 56

Блок - схема:

Редактор кода программирования C:

Улучшите этот пример решения и опубликуйте свой код через Disqus.

Предыдущий: Написать программу на C для сортировки списка элементов с использованием алгоритма быстрой сортировки.
Далее: Написать программу на C для подсчета сортировки.