Tuesday 26 February 2013

C Implementation Of Radix sort


/*Radix sort using counting sort*/

#include <stdio.h>
#include <conio.h>
#define max 10
void print(int arr[max],int len)
{
    int i;
    for(i=0;i<len;i++)
        printf("%d\t",arr[i]);
    printf("\n");
}
void counting_sort_modified(int source_array[max],int destination_array_order[max],int upper_bound,int src_array_length)
{
    int temp_buffer[max],i;
    for(i=0;i<=upper_bound;i++)
    {
        temp_buffer[i]=0;
    }
    for(i=0;i<src_array_length;i++)
    {
        temp_buffer[source_array[i]]=temp_buffer[source_array[i]]+1;
    }
    for(i=1;i<=upper_bound;i++)
    {
        temp_buffer[i]=temp_buffer[i]+temp_buffer[i-1];
    }
    for(i=src_array_length-1;i>=0;i--)
    {
        destination_array_order[temp_buffer[source_array[i]]-1]=i;//source_array[i]; Returns the array of positions of sorted elements.
        temp_buffer[source_array[i]]=temp_buffer[source_array[i]]-1;
    }
}
void array_copy(int src[max],int dest[max],int length)
{
    int iterator=0;
    while(iterator < length)
    {
        dest[iterator]=src[iterator];
        iterator++;
    }
}
void radix_sort(int source_array[max],int src_array_length)
{
    int destination_array[max],stuffed_array[max],iterator,divisor=0,flag;
    do
    {
        flag=iterator=0;
        while(iterator < src_array_length)
        {
            stuffed_array[iterator]=(int)(source_array[iterator]/pow(10,divisor))%10;
            if(stuffed_array[iterator])
            {
                flag=1;
            }
            iterator++;
        }
        if(flag)
        {
            counting_sort_modified(stuffed_array,destination_array,9,src_array_length);
            iterator=0;
            while(iterator < src_array_length)
            {
                stuffed_array[iterator]=source_array[destination_array[iterator]];
                iterator++;
            }
            array_copy(stuffed_array,source_array,src_array_length);
        }
        divisor++;
    }while(flag);
}
int main()
{
    int arr[]={183,265,149,43,123,627};
    print(arr,6);
    radix_sort(arr,6);
    print(arr,6);
    getche();
    return 1;
}

Sunday 14 October 2012

Introduction to Data Types in C Language



Introduction to Data Types in
C Language
Nilanjan Bhattacharya
Abstract
This work is intended to give an insight to a beginner programmer in C about the data storing facilities provided by C Language.
This document covers primitive data types, custom data types, use of arrays, pointers ,dynamic memory allocation techniques.
Introduction
                We encounter data types when we declare a variable in program. It tells the language processor that what kind of data is to be stored in the variable.
Primitively the data types can be of following kind
1.       Integer: These data types are used to signify that the declared variable will contain an integer number. The range of the number is fixed as per the language construct. C language have following keywords to represent Integer:
a.       int
b.      short int
c.       long int
d.      unsigned
2.       Real Number: These data types make a variable store the real numbers. The size is subject to language. There is limitation to the precision of the number. C language have following keywords to represent Real Number:
a.       float
b.      double
3.       Character: This represents the alphabetic character that is stored in the variables. The storage is form of ASCII codes. C language have following keywords to represent Character:
a.       char
4.       Pointer: These variables store the memory address of other variables that are allocated. Two operations are basically defined ‘&’ it shows us the address of variable and   ‘*’it shows value at a memory address.
The word variable is a sloppy nomenclature to memory allocations, actually the variable name has the tag value for the starting memory address and the variable type tells the offset to compute the limit of allocated block of locations in the main memory.

Custom Data Type
The primitive types alone do not suffice the need of a programmer. A programmer may also need his custom data types which are although built out of the primitive types. Some time programmers prefer to give custom names to primitive data types.  
·         typedef construct : This keyword enables a user to define his own custom type. This actually binds name to any data type.
Eg: typedef int  Roll_Number
        Roll_Number rollNo1;
·         struct construct: Whenever we define a composite data type the first thing that hits our mind is struct key word. Suppose our program need variables that is used to store instance of time.
Eg: struct Tx
        {
                        int hour;
                        int min;
                        int sec;
} ;
typedef struct Tx TIME;

TIME t1;               //this statement instantiates a variable of TIME type
int s=(sizeof)TIME;          //this statement will tell the size of time
t1.hour=10;        //Accessing the hour component of TIME structure

·         enum construct : In a problem we may require to have a set of named integer constants that can be helpful in representing scenario where we need look ups or index  just like implementing a priority list.
Eg: enum Px
        {
                        HIGHEST_PRIORITY, //default value to HIGHEST_PRIORITY is 0 and rest follows +1 order .The Numbers could be assigned to names by assignment operator.
                        HIGH_PRIORITY,
                        AVERAGE_PRIORITY,
                        LOW_PRIORITY,
                        LEAST_PRIORITY
} PRIORITY_LIST;
·         union construct: Union is a very important feature provided us in C language. It helps us to create custom data types like in structure but the components are bundled in same storage space. The space consumed by a union is implementation dependent because it saves the space of unused components. The number of bytes to store union must be at least large enough to hold the largest component.
Eg:          union Mx
                {
                                int marks_int;
                                double marks_real;
};
typedef union Mx MARKS;
MARKS m1={10};//initialize the integer part and truncate the double part
MARKS m1={8.5};//initialize the double part and truncate the integer part
MARKS m1.marks_int=10; //initialize the integer part
MARKS m1.marks_real=10; //initialize the double part
Arrays
                It is used to assimilate similar type of data together. It allocates contiguous memory allocation to store desired number of data items. The best thing about it is that it follows random access mechanism to fetch data via the ArrayName[SUBSCRIPT] construct.
Eg:
 int arr[5];//will declare a five blocks in memory where each can store integer number.
                arr={1,3,4,5,6};//will store the number in braces in location arr[0]=1,arr[1]=3…,arr[4]=6.
                arr[3]=7;//assigning the values directly to array by specifying subscript can also be done.
Array name is actually the starting address of the array and it’s subscript is the displacement from the base address.
The bad thing about the array is that it is static in nature i.e. it cannot grow or shrink.

Pointers and Dynamic Memory Allocation
Pointers: These are the special data types that help us to store the memory address of other data object, so that we can access them via referencing.
Basically we have two operations associated with pointers
·         Address Of Operation: It is denoted by “&” it enables us to get the address of the data object.
eg:          int *addr, val;
                addr=&val;
·         Value At Operation: It is denoted by “*” this, enables us to fetch the data stored at a location.
Eg:          int x;
                x=*(addr);
Basic Pointer Arithmetic
·         Increment operation: Pointer increment operator increments the value of the location by the factor of the size of the data type.
Eg:          int *p=1002;
                p++;//it will increment the size by two byte.

·         Decrement operation: Pointer decrement operator increments the value of the location by the factor of the size of the data type.
Eg:          int *p=1002;
                p--;//it will increment the size by two byte.
Dynamic Memory Allocation
                Till now whatever memory allocations we had seen were static in nature that is all the memories were allocated during the compile time of the program. The dynamic memory allocation technique allows us to allocate memory during run time of the program.
                Contiguous Memory Allocation using “calloc” function.
      Calloc function takes in the number of data units required and the size of the data type. Then it returns set of addresses which are in continuity.
      Relation between Array and Pointer is that array name is a pointer to the start of the array.
Eg:   double *pr=(double*)calloc(3,sizeof(double));
//This will allocate 12 byte of memory whose starting address will be marked by pr
Eg: A program in C to store Array of items whose size is dynamically determined.
#include 
#include 

int main ()
{
  int i, n;
  int *pointerData;

  printf ("Enter number of items to be stored: ");
  scanf ("%d", &i);
  pointerData = (int*) calloc (i, sizeof(int));
  
  if (pointerData==NULL) 
      exit (1);
      
  for (n = 0; n < i; n++)
  {
    printf ("Enter number #%d: ", n);
    scanf ("%d", &pointerData[ n ]);
  }
  printf ("You have entered: ");
  
  for (n = 0; n < i; n++) 
      printf ("%d ", pointerData[ n ]);
  free (pointerData);
  return 0;
}

Dynamic memory Allocation using “malloc” function.
        Malloc function is used to just pull up a memory block from allocation heap to store a data object into it.
        Malloc function takes in the size of data type and just returns the location where it could be stored. The address returned is to be casted into respective data type, as it is returned as a void type.
Eg: int* ptr=(int)malloc(sizeof(int));

CASE:  Self referential structures.
        The data objects of such structures, store references to the similar kind of data object.
One of the common example is a linked list which comprises of data nodes appearing to be weaved into a chain. Where each node is apart from storing desired data is also burdened to store the reference to the next node.

Eg: Sample C code for creating, deleting and printing nodes a simple linked list.

#include
#include
struct linklist
{
    int data;
    struct linklist *next; //referencing oneself
};
typedef struct linklist node;//binding name ‘node’ to custom type linklist

node *create_node()
{
    node *p;
    p=(node*)malloc(sizeof(node)); //allocating memory block to store the node
    return p; //returning the address of allocated block
}

node *create_list_b(int val,node *head)//Adding nodes to the beginning
{
    node *t=create_node();//Allocating node
    if(t!=NULL)//If the node is available
    {
        t->data=val;//Placing the desired content
        t->next=head;//Referencing to the first node of list
        head=t;//Making this node the first node of the list
    }
    else
        printf("Sorry no more memory space available\n");
    return head;
}
node *del_beg(node *head)/*Deleting from beginning*/
{
    node *p;
    if(head==NULL)//if there is no element
        printf("Underflow\n");
    else
    {
        p=head;
        printf("%d\n",head->data);
        head=head->next;//Making  the next node of head new node
        free(p);//this function is used to free any memory block
    }
    return head;
}
void print(node *head)/*Prints the contents of the linked list*/
{
    node *t_head=head;
    printf("\nContents\n");
    while(t_head!=NULL)//iterating while the next reference encountered is null
    {
        printf("%d\n",t_head->data);
        t_head=t_head->next;
    }
}
int main()
{
    node *head=NULL;
    int i=0;
    while(i<=10) //filling list with first 10 integers
    {
        head=create_list_b(i,head);
        i++;
    }
    print(head);
    printf("\n");
    head=del_beg(head);//deleting the first node
    head=del_beg(head);
    printf("\n");    
    print(head);
    getch();
}

Twitter Delicious Facebook Digg Stumbleupon Favorites More

 
@Gnosioware Solutions