Radix Sort

C program to sort an array elements using Radix Sort

#include<stdio.h>

#include<stdlib.h>

struct node

{

    int info ;

    struct node *link;

};

typedef struct node * NODE;

NODE bucket[10];

int n, a[20];

int largest()

{

    int i, large = a[0];

    for(i=0;i<n;i++)                        /*First find the largest number in the array*/

    {

        if(a[i] > large)

            large = a[i];

    }

    return large;

}

void insert_rear(int item, int rem)

{

      NODE cur, tmp;

      tmp = (NODE)malloc(sizeof(struct node));

      tmp->info = item;

      tmp->link = NULL;

      if(bucket[rem] == NULL)

      {

            bucket[rem] = tmp;

            return;

      }

      else

      {

           cur = bucket[rem];

           while(cur->link != NULL)

          {

                 cur = cur->link;

           }

           cur->link = tmp;

      }

}

void radix_sort()

{

        NODE p;

        int i, m,k, large, pass = 0, rem, divisor=1, j;

        large = largest();      /*largest number in the array*/

        printf("\nLargest Element is %d", large);

        while(large != 0)           /*Finds number of digits in the largest number*/

        {

            pass++;

            large = large/10 ;

        }

        printf("\nNumber of passes are %d", pass);

        for(m=1; m<=pass; m++)

        {

               printf("\n\n::::Pass %d::::", m);

               for(i=0;i<=9;i++)           /*initialize the buckets: Total 9 buckets*/

                      bucket[i] = NULL;

               for(i=0;i<n;i++)

               {

                     rem = (a[i] / divisor) %10;

                     insert_rear(a[i], rem);

               }

               for(i=0; i<=9 ; i++)

              {

                    printf("\nbucket(%d) -> ",i);

                    p = bucket[i];

                    while(p!=NULL)

                   {

                           printf("%d ",p->info);

                           p = p->link;

                    }

              }

            /*Taking the elements of linked lists in array*/

             i = 0;

             for(k=0;k<=9;k++)

             {

                  p = bucket[k];

                  while(p!=NULL)

                 {

                      a[i++] = p->info;

                      p = p->link;

                 }

            }

            divisor = divisor*10;

        }

}

void main()

{

    int i;

    printf("\nEnter the number of elements in the list : ");

    scanf("%d",&n);

    for(i=0;i<n;i++)

    {

        printf("\nEnter element %d : ",i+1);

        scanf("%d",&a[i]);

    }

    printf("\nUnsorted list is :\n");

    for(i=0;i<n;i++)

        printf("%d ",a[i]);

    radix_sort();

    printf("\nSorted list is :\n");

    for(i=0;i<n;i++)

        printf("%d ",a[i]);

}

Output:

Enter the number of elements in the list : 10

Enter element 1 : 179

Enter element 2 : 208

Enter element 3 : 306

Enter element 4 : 93

Enter element 5 : 859

Enter element 6 : 984

Enter element 7 : 55

Enter element 8 : 9

Enter element 9 : 271

Enter element 10 : 33

Unsorted list is :

179   208   306   93   859   984   55   9   271   33

Largest Element is 984

Number of passes are 3

::::Pass 1::::

bucket(0) ->

bucket(1) -> 271

bucket(2) ->

bucket(3) -> 93 33

bucket(4) -> 984

bucket(5) -> 55

bucket(6) -> 306

bucket(7) ->

bucket(8) -> 208

bucket(9) -> 179 859 9

::::Pass 2::::

bucket(0) -> 306 208 9

bucket(1) ->

bucket(2) ->

bucket(3) -> 33

bucket(4) ->

bucket(5) -> 55 859

bucket(6) ->

bucket(7) -> 271 179

bucket(8) -> 984

bucket(9) -> 93

::::Pass 3::::

bucket(0) -> 9 33 55 93

bucket(1) -> 179

bucket(2) -> 208 271

bucket(3) -> 306

bucket(4) ->

bucket(5) ->

bucket(6) ->

bucket(7) ->

bucket(8) -> 859

bucket(9) -> 984

Sorted list is :

9   33   55   93   179   208   271   306   859   984

Address Calculation Sort

C Program to sort array elements using Address Calculation Sort

#include<stdio.h>
#include<stdlib.h>

struct node
{
       int info;
       struct node *link;
};
typedef struct node * NODE;
NODE head[10];
int n,i,a[20];

int hash_fn(int number,  int k)
{
             /*Find kth digit of the number :example: if its 356 then kth digit will be 3 or if its 29 then kth digit will be 2*/
        int digit, i;
        for(i = 1 ; i <=k ; i++)
        {
              digit = number % 10 ;
              number = number /10 ;
        }
        return digit;       //address
}


/* Finds number of digits in the largest element of the list */
int large_dig()
{
       int large = a[0],ndig = 0 ;
       for(i=0;i<n;i++)                        /*First find the largest number in the array*/
      {
              if(a[i] > large)
                      large = a[i];
       }
       printf("\nLargest Element is %d",large);

      while(large != 0)           /*Finds number of digits in the largest number*/
      {
               ndig++;
               large = large/10 ;
      }
      printf("\nNumber of digits in it are %d", ndig);
      return(ndig);
}


/*Inserts the number in linked list in sorted manner*/
void insert(int num, int addr)
{
      NODE cur ,tmp;
      tmp = (NODE)malloc(sizeof(struct node));
      tmp->info = num;

      /*list empty or item to be added in beginning */
       if(head[addr] == NULL || num < head[addr]->info)
      {
            tmp->link = head[addr];
            head[addr] = tmp;
            return;
      }
     else
     {
            cur = head[addr];
            while(cur->link != NULL && cur->link->info < num)
                      cur = cur->link;
            tmp->link = cur->link;
            cur->link = tmp;
     }
}

void addr_sort()
{
       int i, k, dig, addr;
       NODE p;
       k = large_dig();        /*number of digits in the largest number*/
       for(i=0;i<=9;i++)
               head[i]=NULL;
       for(i=0;i<n;i++)
      {
               addr = hash_fn(a[i], k);
               insert(a[i], addr);
       }

      for(i=0; i<=9 ; i++)
      {
              printf("\nhead(%d) -> ", i);
              p = head[i];
              while(p!=NULL)
             {
                    printf("%d ", p->info);
                    p = p->link;
              }
      }
     /*Taking the elements of linked lists in array*/
      i = 0;
      for(k=0;k<=9;k++)
      {
               p = head[k];
               while(p!=NULL)
              {
                       a[i++] = p->info;
                       p = p->link;
               }
      }
}

void main()
{
      int i;
      printf("\nEnter the number of elements in the list : ");
      scanf("%d", &n);
      for(i=0;i<n;i++)
      {
             printf("\nEnter element %d : ",i+1);
             scanf("%d",&a[i]);
      }

      printf("\nUnsorted list is :\n");
      for(i=0;i<n;i++)
            printf("%d ",a[i]);

      addr_sort();
      printf("\nSorted list is :\n");
      for(i=0;i<n;i++)
              printf("%d ",a[i]);
}


Output:

Enter the number of elements in the list : 15
Enter element 1 : 12
Enter element 2 : 345
Enter element 3 : 567
Enter element 4 : 367
Enter element 5 : 789
Enter element 6 : 23
Enter element 7 : 15
Enter element 8 : 56
Enter element 9 : 567
Enter element 10 : 899
Enter element 11 : 123
Enter element 12 : 321
Enter element 13 : 678
Enter element 14 : 67
Enter element 15 : 45
Unsorted list is :
12   345   567  367   789   23   15   56   567   899   123   321   678   67   45
Largest Element is 899
Number of digits in it are 3

head(0) -> 12  15  23  45  56  67
head(1) -> 123
head(2) ->
head(3) -> 321  345  367
head(4) ->
head(5) -> 567  567
head(6) -> 678
head(7) -> 789
head(8) -> 899
head(9) ->
Sorted list is :
12   15   23   45   56   67   123   321   345   367   567   567   678   789  899

Insertion Sort

C Program to sort the elements using Insertion Sort

#include<stdio.h>
int n, a[20];

void insertion_sort()
{
       int i, j, temp;
       for(i=1; i<n ;i++)
      {
              temp = a[i];
              j = i-1;
              while(j>=0 &&  temp < a[j])
             {
                    a[j+1] = a[j];
                    j = j-1;
             }
             a[j+1] = temp;
       }
}

void main()
{
       int i;
       printf("\nEnter the number of elements: ");
       scanf("%d",&n);

      printf("\nEnter the array elements:");
      for(i=0;i<n;i++)
           scanf("%d", &a[i]);

      insertion_sort();

     printf("\nThe array elements after insertion sort: ");
     for(i=0;i<n;i++)
            printf("%d ", a[i]);
}

Output:
Enter the number of elements: 7
Enter the array elements:  89     45      68       90       29       34       17
The array elements after insertion sort: 17       29       34         45        68        89       90