Home » Data Structure

Sorting using Address Calculation Sort

In this article, we will look up on what is sorting and one of its types which is address calculation sort? By Manu Jemini, on January 15, 2018

When we say sorting it means serializing a collection of data inside any the collections like arrays, linked list etc. There is one good reason for implementing sorting on any collection is that it makes the searching very fast as compared to the collection which is unsorted. Now, this is not true for every test case but on an average, it is so.

Address calculation sort?

Take an array of integers of range 0 to 100. It will be easy to sort 10 smaller arrays rather than sorting one big array. So someone comes up with an algorithm. Now what is an algorithm, it is nothing but an approach to solve a problem.

So in this approach, we make a pass through whole the array and separate the different integers into 10 smaller groups.

Example

For example: 56, 78, 65, 1, 9, 98, 23, 33, 34, 39

[0] => 1, 9
[1] => NULL
[2] => 23
[3] => 33, 34, 39
[4] => Null
[5] => 56
[6] => 65 
[7] => 78 
[8] => NULL 
[9] => 98     

Now solving these arrays are very easy, one of the main reason is the array which has less than equal to 1 item are already sorted in nature.

Implement Sorting using Address Calculation Sort in C

Let's understand further with the help of code:

#include<stdio.h>
#include<malloc.h>

#define MAX 20

struct node {
  int info;
  struct node * link;
};

struct node * head[10];
int n, i, arr[MAX];

/*Inserts the number in sorted linked list*/
void insert(int num, int addr) {
  struct node * q, * tmp;
  tmp = (struct node * ) malloc(sizeof(struct node));
  tmp -> info = num;
  /*list empty or item to be added in begining */
  if (head[addr] == NULL || num < head[addr] -> info) {
    tmp -> link = head[addr];
    head[addr] = tmp;
    return;
  } else {
    q = head[addr];
    while (q -> link != NULL && q -> link -> info < num)
      q = q -> link;
    tmp -> link = q -> link;
    q -> link = tmp;
  }
} /*End of insert()*/

/* Finds number of digits in the largest element of the list */
int large_dig() {

  int large = 0, ndig = 0;

  for (i = 0; i < n; i++) {
    if (arr[i] > large)
      large = arr[i];
  }
  printf("Largest Element is %d , ", large);
  while (large != 0) {
    ndig++;
    large = large / 10;
  }

  printf("Number of digits in it are %d\n", ndig);
  return (ndig);
} /*End of large_dig()*/

int hash_fn(int number, int k) {
  /*Find kth digit of the number*/
  int digit, addr, i;
  for (i = 1; i <= k; i++) {
    digit = number % 10;
    number = number / 10;
  }
  addr = digit;
  return (addr);
} /*End of hash_fn()*/

void addr_sort() {
  int i, k, dig;
  struct node * p;
  int addr;
  k = large_dig();
  for (i = 0; i <= 9; i++)
    head[i] = NULL;
  for (i = 0; i < n; i++) {
    addr = hash_fn(arr[i], k);
    insert(arr[i], addr);
  }

  for (i = 0; i <= 9; i++) {
    printf("head(%d) -> ", i);
    p = head[i];
    while (p != NULL) {
      printf("%d ", p -> info);
      p = p -> link;
    }
    printf("\n");
  }

  /*Taking the elements of linked lists in array*/
  i = 0;
  for (k = 0; k <= 9; k++) {
    p = head[k];
    while (p != NULL) {
      arr[i++] = p -> info;
      p = p -> link;
    }
  }
} /*End of addr_sort()*/

int main() {

  int i;
  printf("Enter the number of elements in the list : ");
  scanf("%d", & n);
  for (i = 0; i < n; i++) {
    printf("Enter element %d : ", i + 1);
    scanf("%d", & arr[i]);
  } /*End of for */

  printf("Unsorted list is :\n");
  for (i = 0; i < n; i++)
    printf("%d  ", arr[i]);
  printf("\n");
  addr_sort();
  printf("Sorted list is :\n");
  for (i = 0; i < n; i++)
    printf("%d  ", arr[i]);
  printf("\n");
  
  return 0;
} /*End of main()*/

Output