Data Structures in C: June 2014

Monday, June 30, 2014

Selection Sort

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n²) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.

Selection sort carries out a sequence of passes over the table. At the first pass an entry is selected on some criteria and placed in the correct position in the table. The possible criteria for selecting an element are to pick the smallest or pick the largest. If the smallest is chosen then, for sorting in ascending order, the correct position to put it is at the beginning of the table. Now that the correct entry is in the first place in the table the process is repeated on the remaining entries. Once this has been repeated n-1 times the n-1 smallest entries are in the first n-1 places which leaves the largest element in the last place. Thus only n-1 passes are required. The algorithm can be described as follows:

for i from 1 to n-1
   {
    Find smallest element in ith to nth entries.
    Exchange this element with ith entry.
   }

For example consider the following example of selection sort being carried out on a sample set of data:

9 2 5 7 4 8   on pass 1 look for smallest in 1st to 6th
              swap 2nd with first giving
2 9 5 7 4 8   on pass 2 look for smallest in 2nd to 6th
              swap 5th with second giving
2 4 5 7 9 8   on pass 3 look for smallest in 3rd to 6th
              swap 3rd with third giving
2 4 5 7 9 8   on pass 4 look for smallest in 4th to 6th
              swap 4th with fourth giving
2 4 5 7 9 8   on pass 5 look for smallest in 5th to 6th
              swap 5th with 6th giving
2 4 5 7 8 9   sorted.

The algorithm is now written in C++. Of course the limits 1 to n-1 in the above now become 0 to n-2 because array subscripts start at 0.

for (i = 0; i < n-1; i++)
  {
     // find smallest entry in ith to n-1 th place
     // p is subscript of smallest entry yet found
   p = i;
   for (j = i+1; j < n; j++)
     if (a[j]<a[p])
       p = j;
     // exchange pth element with ith element
   t = a[p];
   a[p] = a[i];
   a[i] = t;
  }

Note that when finding the smallest element the index p is the index of the smallest value found so far. Only after the position of the minimum value has been found does the actual interchange take place.
In assessing the efficiency of sorting routines it is usual to count the number of comparisons made between keys and the number of exchanges of table entries.
To count the number of comparisons in the above algorithm note that the outer loop is traversed n-1 times. At the ith execution of the outer loop the inner loop is executed as j takes values from i+1 to n-1, that is n-i-1 times. Hence the total number of comparisons made is

(n-1)+(n-2)+.....+3+2+1 = n(n-1)/2

So on comparisons selection sort is order(

). Thus doubling the number of entries to be sorted will mean that four times as many comparisons will be made.
Inside the outer loop entries are exchanged three times. Thus the total number of exchanges is 3*(n-1), i.e. of order(n).

Source code:

#include "stdio.h"

void main( )
{
 int arr[5] = { 25, 17, 31, 13, 2 } ;
 int i, j, temp ;
 for ( i = 0 ; i <= 3 ; i++ )
 {
  for ( j = i + 1 ; j <= 4 ; j++ )
  {
   if ( arr[i] > arr[j] )
   {
    temp = arr[i] ;
    arr[i] = arr[j] ;
    arr[j] = temp ;
   }
  }
 }

 printf ( "\n\nArray after sorting:\n") ;

 for ( i = 0 ; i <= 4 ; i++ )
  printf ( "%d\t", arr[i] ) ;
}

Insertion Sort

Insertion sort is an elementary sorting algorithm. It has a time complexity of Θ(n²), thus being slower than heapsort, merge sort and also shellsort. Insertion sort is well suited for sorting small data sets or for the insertion of new elements into a sorted sequence.

Suppose A is an array of N Integer values. We want to sort A in ascending order, that is, so A(1) is smallest and A(N) is largest.

Insertion Sort is an algorithm to do this as follows: We have the top part of the array, which is in order, and the bottom part of the array, which needs more work. We repeatedly look at the top element in the unsorted part of the array and move it up, a step at a time, to where it belongs in the sorted part of the array.

We use a Swap subroutine which switches the values of two array elements.

Of course, instead of using subroutines, we could easily write all the code we need in the main program.

It is easy to modify this to put the values in descending order nstead, so A(1) is largest and A(N) is smallest.

Example
Suppose A is an array of 10 Integer values and the initial values in A are:

         67    33    21     4    84    49    15    55    75     6

Pass 1: We insert 33 into the sorted part of the array, which at the moment is just 67.

          As 33 < 67, we swap them:
         33    67    21     4    84    49    15    55    75     6
     \------/  \------------------------------------------------/
   sorted part          unsorted part of the array

Pass 2: We insert 21 into the sorted part of the array.

          As 21 < 67, we swap them:     
         33    21    67     4    84    49    15    55    75     6

          As 21 < 33, we swap them:
         21    33    67     4    84    49    15    55    75     6
         \------------/    \------------------------------------/
          sorted part           unsorted part of the array

Pass 3: We insert 4 into the sorted part of the array.

          As 4 < 67, we swap them:
         21    33     4    67    84    49    15    55    75     6
           
          As 4 < 33, we swap them:
         21     4    33    67    84    49    15    55    75     6

          As 4 < 21, we swap them:
          4    21    33    67    84    49    15    55    75     6
         \------------------/    \------------------------------/
             sorted part            unsorted part of the array

Pass 4: We insert 84 into the sorted part of the array.

          As 84 > 67, we do not swap them and we exit the loop.
          4    21    33    67    84    49    15    55    75     6
         \------------------------/    \------------------------/
          sorted part of the array     unsorted part of the array

Pass 5: We insert 49 into the sorted part of the array.

          As 49 < 84, we swap them:
          4    21    33    67    49    84    15    55    75     6

          As 49 < 67, we swap them:
          4    21    33    49    67    84    15    55    75     6
 
          As 49 > 33, we do not swap them and we exit the loop.
          4    21    33    49    67    84    15    55    75     6
         \------------------------------/    \------------------/
             sorted part of the array            unsorted part

Pass 6: We insert 15 into the sorted part of the array.

          As 15 < 84, we swap them:
          4    21    33    49    67    15    84    55    75     6

          As 15 < 67, we swap them:
          4    21    33    49    15    67    84    55    75     6

          As 15 < 49, we swap them:
          4    21    33    15    49    67    84    55    75     6

          As 15 < 33, we swap them:
          4    21    15    33    49    67    84    55    75     6

          As 15 < 21, we swap them:
          4    15    21    33    49    67    84    55    75     6

          As 15 > 4, we do not swap them and we exit the loop (for two reasons).
          4    15    21    33    49    67    84    55    75     6
         \------------------------------------/    \------------/
                sorted part of the array            unsorted part

Pass 7: We insert 55 into the sorted part of the array.

          As 55 < 84, we swap them:
          4    15    21    33    49    67    55    84    75     6

          As 55 < 67, we swap them:
          4    15    21    33    49    55    67    84    75     6

          As 55 > 49, we do not swap them and we exit the loop.
          4    15    21    33    49    55    67    84    75     6
         \------------------------------------------/    \------/
                 sorted part of the array                unsorted

Pass 8: We insert 75 into the sorted part of the array.

          As 75 < 84, we swap them:
          4    15    21    33    49    55    67    75    84     6

          As 75 > 67, we do not swap them and we exit the loop.
          4    15    21    33    49    55    67    75    84     6
         \------------------------------------------------/ \------/
                   sorted part of the array                  sorted

Pass 9: We insert 6 into the sorted part of the array.

          As 6 < 84, we swap them:
          4    15    21    33    49    55    67    75     6    84

          As 6 < 75, we swap them:
          4    15    21    33    49    55    67     6    75    84

          As 6 < 67, we swap them:
          4    15    21    33    49    55     6    67    75    84

          As 6 < 55, we swap them:
          4    15    21    33    49     6    55    67    75    84

          As 6 < 49, we swap them:
          4    15    21    33     6    49    55    67    75    84

          As 6 < 33, we swap them:
          4    15    21     6    33    49    55    67    75    84

          As 6 < 21, we swap them:
          4    15     6    21    33    49    55    67    75    84

          As 6 < 15, we swap them:
          4     6    15    21    33    49    55    67    75    84

          As 6 > 4, we do no swap them and we exit the loop (for two reasons).
          4     6    15    21    33    49    55    67    75    84

At this point we are done.
In the process, we have done 35 comparisons and 25 swaps. For an array of 10 elements, Insertion Sort may do anywhere from 9 to 45 comparisons and anywhere from 0 to 45 swaps.

Source Code:

#include<stdio.h>

#include<conio.h>

int main()

    int a[10],n,k,i,j,temp;

    a[10]={9,7,6,15,16,5,10,11};

    for(k=1;k<=n-1;k++)

            temp=a[k];

            j=k-1;

    while(temp<a[j]&&j>=0)

            a[j+1]=a[j];

            j=j-1;

            a[j+1]=temp;

    printf("Elements of array after sorting are :");

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

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

    getch();

Bubble Sort

Bubble sort is a sorting algorithm that works by repeatedly stepping through lists that need to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. This passing procedure is repeated until no swaps are required, indicating that the list is sorted. Bubble sort gets its name because smaller elements bubble toward the top of the list.

Source Code:

#include<stdio.h>
#include<conio.h>
int data[10]={22,65,1,99,32,17,74,49,33,2};
int n=10;
void bubble(void);
void main()
{
    int i;
    //clrscr(); This will not work at Dev c++
    bubble();
    printf("The values from array after sorted: \n");
    for (i=0;i<10;i++)
        printf(" %d",data[i]);

    getch();
}
void bubble(void)
{
    int k,ptr,temp;
    for(k=0;k<=n-1-1;k++)
    {
        ptr=0;
        while(ptr<=(n-k-1-1))
        {
            if(data[ptr]>data[ptr+1])
            {
                temp=data[ptr];
                data[ptr]=data[ptr+1];
                data[ptr+1]=temp;
            }
            ptr+=1;
        }
    }
}

Binary Tree

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

typedef struct BST
{
    int data;
    struct BST *lchild,*rchild;
}node;

void insert(node *,node *);
void inorder(node *);
void preorder(node *);
void postorder(node *);
node *search(node *,int,node **);

void main()
{
int choice;
char ans='N';
int key;
node *new_node,*root,*tmp,*parent;
node *get_node();
root=NULL;
clrscr();

printf("nProgram For Binary Search Tree ");
do
{
   printf("n1.Create");
   printf("n2.Search");
   printf("n3.Recursive Traversals");
   printf("n4.Exit");
   printf("nEnter your choice :");
   scanf("%d",&choice);

   switch(choice)
   {
    case 1:
           do
             {
             new_node=get_node();

             printf("nEnter The Element ");
             scanf("%d",&new_node->data);

             if(root==NULL)   /* Tree is not Created */
                 root=new_node;
             else
                 insert(root,new_node);

             printf("nWant To enter More Elements?(y/n)");
             ans=getch();

             }while(ans=='y');

             break;

     case 2:
             printf("nEnter Element to be searched :");
             scanf("%d",&key);

             tmp = search(root,key,&parent);

             printf("nParent of node %d is %d",
                              tmp->data,parent->data);
             break;

    case 3:

            if(root==NULL)
                printf("Tree Is Not Created");
            else
               {
               printf("nThe Inorder display : ");
               inorder(root);
               printf("nThe Preorder display : ");
               preorder(root);
               printf("nThe Postorder display : ");
               postorder(root);
               }

            break;
    }
}while(choice!=4);
}
/*
Get new Node
*/
node *get_node()
{
node *temp;
temp=(node *)malloc(sizeof(node));
temp->lchild=NULL;
temp->rchild=NULL;
return temp;
}
/*
This function is for creating a binary search tree
*/
void insert(node *root,node *new_node)
{
if(new_node->data < root->data)
     {
     if(root->lchild==NULL)
         root->lchild = new_node;
     else
         insert(root->lchild,new_node);
     }

if(new_node->data > root->data)
     {
     if(root->rchild==NULL)
         root->rchild=new_node;
     else
         insert(root->rchild,new_node);
     }
}
/*
This function is for searching the node from
      binary Search Tree
*/
node *search(node *root,int key,node **parent)
{
node *temp;
temp=root;
    while(temp!=NULL)
    {
      if(temp->data==key)
         {
         printf("n The %d Element is Present",temp->data);
         return temp;
         }
      *parent=temp;

      if(temp->data>key)
         temp=temp->lchild;
      else
         temp=temp->rchild;
    }
return NULL;
}
/*
This function displays the tree in inorder fashion
*/
void inorder(node *temp)
{
   if(temp!=NULL)
    {
    inorder(temp->lchild);
    printf("%d",temp->data);
    inorder(temp->rchild);
    }
}
/*
This function displays the tree in preorder fashion
*/
void preorder(node *temp)
{
if(temp!=NULL)
    {
    printf("%d",temp->data);
    preorder(temp->lchild);
    preorder(temp->rchild);
    }
}

/*
This function displays the tree in postorder fashion
*/
void postorder(node *temp)
{
if(temp!=NULL)
    {
    postorder(temp->lchild);
    postorder(temp->rchild);
    printf("%d",temp->data);
    }
}

Hints:

Preorder traversal sequence : F, B, A, D, C, E, G, I, H
   (root, left, right)
Inorder traversal sequence  : A, B, C, D, E, F, G, H, I
   (left, root, right)
Postorder traversal sequence: A, C, E, D, B, H, I, G, F
   (left, right, root)