C Exercises: Sort numbers using Bead Sort method

C Programming Searching and Sorting Algorithm: Exercise-12 with Solution

Write a C program that sorts numbers using the Bead Sort method.

According to Wikipedia "Bead sort, also called gravity sort, is a natural sorting algorithm, developed by Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen in 2002, and published in The Bulletin of the European Association for Theoretical Computer Science. Both digital and analog hardware implementations of bead sort can achieve a sorting time of O(n); however, the implementation of this algorithm tends to be significantly slower in software and can only be used to sort lists of positive integers. Also, it would seem that even in the best case, the algorithm requires O(n2) space".

Sample Solution:

Sample C Code:

// Source: https://bit.ly/2rcvXK5
#include <stdio.h>
#include <stdlib.h>
// Function to perform Bead Sort on an array
void bead_sort(int *a, int len) {
    int i, j, max, sum;
    unsigned char *beads;
    // Define a macro for accessing elements in the beads array
    #define BEAD(i, j) beads[i * max + j]
    // Find the maximum element in the array
    for (i = 1, max = a[0]; i < len; i++)
        if (a[i] > max) max = a[i];
    // Allocate memory for the beads array
    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;
    // Count the number of beads on each post
    for (j = 0; j < max; j++) {
        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;
    }
    // Assign sorted values back to the array
    for (i = 0; i < len; i++) {
        for (j = 0; j < max && BEAD(i, j); j++);
        a[i] = j;
    }
    // Free the allocated memory
    free(beads);
}
// Main function
int main() {
    int i, x[] = {5, 3, 1, 7, 4, 1, 1, 20};
    int len = sizeof(x) / sizeof(x[0]);
    // Display original array
    printf("Original Array:\n");
    for (i = 0; i < len; i++)
        printf("%d%s", x[i], i == len - 1 ? "\n" : " ");
    // Sort the array using Bead Sort
    bead_sort(x, len);
    // Display sorted array
    printf("\nSorted Array:\n");
    for (i = 0; i < len; i++)
        printf(" %d", x[i]);
    return 0;
}

Sample Output:

Original Array:
5 3 1 7 4 1 1 20

Sorted Array:
 1 1 1 3 4 5 7 20

Flowchart:

C Programming Code Editor:

Previous: Write a C program that sort numbers using QuickSort method.
Next: Write a C program that sort numbers using Bogo Sort method.