Code@Node

A Blog about Data Structures and their C Language Implementation

Recursion : A breath taker(for you or machine?)

Posted by Abhinav Kushwaha on April 6, 2007

Recursion is just another subtle topic in any language paradigm. For some people recursion is breath taker and for some its just a handy tool for write a small code. At first Recursion seems complex to grasp, but after some practice we can master this technique very easily.

A simple definition of Recursion may be ” Recursion is a technique of defining the program in the terms of itself.”

Lets start with a simple example.

Any problem that can be subdivided in the term of itself can be solved with recursion. For example here is a recurrence formula for calculating the nth power of a ;

 

 

In this case for any value other than n = 0, we can calculate the nth power of a by multiplying the number by (n-1)th power of that number i.e an = a*an-1.

In recursion we always have to ensure a terminating condition. In absence of terminating condition the program will continue to call it self ever and ever again(forever).

In this case n=0 is terminating condition and we know its value (its 1).

Equipped with this knowledge, lets create a function for calculating nth power of a number. For simplicity assume that the number (a) is a Integer.

Here is power function in C .

int power(int base, int degree){
  if(degree == 0){
    return 1;
  }else{
    return (base*power(base, degree-1));
  }
}

In this example for 2nd line test for terminating condition, otherwise 5th line calculate a*an-1 .

Posted in C | Leave a Comment »

Insertion Sort

Posted by Abhinav Kushwaha on February 1, 2007

Insertion sort is very simple sorting algorithm. It is an efficient algorithm to sort small number of elements.

Insertion sort works the way many people sort a hand of playing card.We then remove one card at a time from the table and insert it into the
correct position in the left hand. To find the correct position for a card, we compare
it with each of the cards already in the hand, from right to left, as illustrated in
Figure 2.1. At all times, the cards held in the left hand are sorted, and these cards
were originally the top cards of the pile on the table[1].

In insertion sort we start with the second element of array and insert this element at the correct position into the sorted subarray to the left of that element. We take next elements and insert this element at the correct position into the left sorted subarray. We continue in this manner until whole array is sorted(we reached at the end of array). We insert any element into left sorted array, at correct position by comparing the element by the elements of left sorted subarrray.

Now, i will show the procedure of Insertion Sort with the help of diagram and then i will make a C function to perform insertion sort on the array of integer.

Suppose we have an array of six elements A[ ] = { 5,2,4,6,1,3 }

Diagramatic Representaion of Insertion Sort

This diagram shows the execution of insertion sort on a typical array. This diagram is self explanatory. On the first iteration second element 2 is compaired with first element 5, as 5 is the only element in the left sorted subarray(array with only one element is sorted in itself). Since 5 is greater than 2 hence 5 is shifted toward one place right and 2 is placed before 5(previous place occupied by element 5). Now after first iteration there are two elements on left sorted subarray. Now the 3rd element 4 is placed at the proper position into the left sorted subarray. The whole sorting algorithm continue in this fashion untill no element is left in right unordered array(see figure). When we shift more than one element during the execution , we shift the element toward right in the order of decreasing index value i.e. the element with the highest index value(in left sorted subarray) is shifted first then element with next lower index and so on. The order of shifting is shown in the figure with the help of thickness of arrow. The element with the thinest arrow is shifted first then next element with relativaly high thickness and so on.

Now I implement Insertion Sort in C language.


/* Insertion Sort Function
Created by: Abhinav Kushwaha*/

void InsertionSort(int *num, int length){
    int i=0,j=0,key;
    for(i=1;i<length;i++){
        key=num[i];    //store the key value so that we can place it at proper position
        j=i-1;            //the upper bound of left sorted array will be i-1
        while((j>=0)&&(key<num[j])){
            num[j+1]=num[j];    //shift the elements of sorted left subarray toward one place right
            j--;
        }
        num[j+1]=key;    //after shifting the elements we place the key element at proper position
    }
}

This function takes Array and its Length as parameter and perform insertion sort on that array. Since array is passed by reference the change in array in this function is also reflected in calling function.The outer for loop covers the right unordered subarray and inner while loop covers the left sorted subarray. key is variable that holds the element value which is currently under consideration(element in shaded box in the diagram). j variable span over left sorted subarray. In while loop we check where we have to insert the ‘key’ variable(the element under process).

while((j>=0)&&(key<num[j])){
    num[j+1]=num[j];
    j--;
}

The condition((j>=0) ) in while loop checks if the lower bound of array is reached or not. The condition((key<num[j])) in while loop ensure that comparision is made until procesing element(key) is less that the comparing element is left subarray.

The statement ( num[j+1]=num[j]; ) shifts the elements of left subarray to right, to make room for insertion of key element. After shifting of elements of left subarray thw while loop terminates , now statement ( num[j+1]=key; ) insert(store) the key element at the proper position.

Posted in C, Data Structure | Leave a Comment »

Sorting

Posted by Abhinav Kushwaha on January 31, 2007

Sorting is method by which we rearrange a sequence of data into particular order. Arrangement of data can be in Ascending order or descending order.

Sorting is implemented by various algorithms. Some of the commonly used sorting methods are Insertion Sort, Selection Sort, Merge Sort, Heap Sort etc. These methods (algorithms) differ in the term of efficiency. The efficiency of an algorithm is defined in the term of Algorithm Complexity. In simple words Complexity is defined in the term of Space required and/or running time of an algorithm. Complexity of any algorithm is defined over the number of inputs to the algorithm.

In computer science it is defined as Θ(n)( worst case representation of complexity, pronounced “theta of n”)[1].

Generally in any sorting method we input a sequence of n numbers a1, a2, . . . , an and the sorting method output a permutation (reordering) a’1 , a’2 , . . . , a’n of the input sequence such that a1 a2 · · ·an or a1 a2 · · · an or a1 a2 · · · an


[1] For detail information about various algorithms and their run time analysis read “Introduction To Algorithms”(Thomas H. Cormen, Charles E. Leiserson ,Ronald L. Rivest, Clifford Stein).

Posted in C, Data Structure | Leave a Comment »

Data Structure

Posted by Abhinav Kushwaha on January 31, 2007

Data structures are ways of organizing data in an efficient way. Different data types are better suited for different applications. Data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow a more efficient algorithm to be used. A well-designed data structure allows a variety of critical operations to be performed, using as few resources, both execution time and memory space, as possible. Data structures are implemented using the data types, references and operations on them provided by a programming language.

Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to certain tasks. For example, B-trees are particularly well-suited for implementation of databases, while routing tables rely on networks of machines to function.

Some Common Data Structures are as follows:

Usefull Links

Download Data structure Lectures
Dictionary of Algorithms and Data Structures
Wikipedia

Posted in Data Structure | Leave a Comment »

 
Follow

Get every new post delivered to your Inbox.