Упражнения C: сортировка чисел методом сортировки по бисеру

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

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

Согласно Википедии, «сортировка по бисеру, также называемая гравитационной сортировкой, является естественным алгоритмом сортировки, разработанным Джошуа Дж. Аруланандхамом, Кристианом С. Калуде и Майклом Дж. Диннином в 2002 году и опубликованным в Бюллетене Европейской ассоциации теоретических компьютерных наук». Как цифровые, так и аналоговые аппаратные реализации сортировки по бусинкам могут достигать времени сортировки O (n), однако реализация этого алгоритма, как правило, значительно медленнее в программном обеспечении и может использоваться только для сортировки списков положительных целых чисел. Казалось бы, даже в лучшем случае алгоритм требует O (n2) пробела ».

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

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

// https://bit.ly/2rcvXK5
#include  <stdio.h>  
#include <stdlib.h>
 
void bead_sort(int *a, int len)
{
	int i, j, max, sum;
	unsigned char *beads;
       #define BEAD(i, j) beads[i * max + j]
 
	for (i = 1, max = a[0]; i < len; i++)
		if (a[i] > max) max = a[i];
 
	beads = calloc(1, max * len);
 
	/* mark the beads */
	for (i = 0; i < len; i++)
		for (j = 0; j < a[i]; j++)
			BEAD(i, j) = 1;
 
	for (j = 0; j < max; j++) {
		/* count how many beads are on each post */
		for (sum = i = 0; i < len; i++) {
			sum += BEAD(i, j);
			BEAD(i, j) = 0;
		}
		/* mark bottom sum beads */
		for (i = len - sum; i < len; i++) BEAD(i, j) = 1;
	}
 
	for (i = 0; i < len; i++) {
		for (j = 0; j < max && BEAD(i, j); j++);
		a[i] = j;
	}
	free(beads);
}
 
int main()
{
	int i, x[] = {5, 3, 1, 7, 4, 1, 1, 20};
	int len = sizeof(x)/sizeof(x[0]);
    printf("Original Array:\n");
    for (i = 0; i < len; i++)
    printf("%d%s", x[i], i == len - 1 ? "\n" : " ");
	bead_sort(x, len);
	printf("\nSorted Array:\n");
	for (i = 0; i < len; i++)
		printf(" %d", x[i]);
 
	return 0;
}

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

 Оригинальный массив:
5 3 1 7 4 1 1 20
Сортированный массив:
 1 1 1 3 4 5 7 20

Блок - схема:

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

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

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