GTU C PROGRAMS | HEAP SORT PROGRAM

C:
-------------------------------------------------------------------------
/* HEAP SORT */
/* HEAP.C */
# include<stdio.h>
void  heap_sort(int *, int );
void create_heap(int *, int);
void display(int *, int);
/*  Definition of the function */
void create_heap(int list[], int n )
{
 int k, j, i, temp;
 for(k = 2 ; k <= n;  ++k)
 {
  i = k ;
  temp = list[k];
  j = i / 2 ;
  while((i > 1) && (temp > list[j]))
  {
   list[i] = list[j];
   i = j ;
   j = i / 2 ;
   if ( j < 1 )
    j = 1 ;
  }
  list[i] = temp ;
 }
}
/* End of heap creation function */
/* Definition of the function */
void heap_sort(int list[], int n)
{
 int k, temp, value, j, i, p;
 int step = 1;
 for(k = n ; k >= 2; --k)
 {
  temp = list[1] ;
  list[1] = list[k];
  list[k] = temp ;
  i = 1 ;
  value = list[1];
  j = 2 ;
  if((j+1) < k)
   if(list[j+1] > list[j])
    j ++;
  while((j <= ( k-1)) && (list[j] > value))
  {
   list[i] = list[j];
   i = j ;
   j = 2*i ;
   if((j+1) < k)
    if(list[j+1] > list[j])
     j++;
    else
     if( j > n)
      j = n ;
   list[i] = value;
  } /* end of while statement */
  printf("\n Step = %d ", step);
  step++;
  for(p = 1; p <= n; p++)
   printf(" %d", list[p]);
 } /* end for loop */
}
/* Display function */
void display(int list[], int n)
{
 int i;
 for(i = 1 ; i <= n; ++ i)
 {
  printf("  %d", list[i]);
 }
}
/* Function main */
void main()
{
 int list[]={ 0,10,23,64,21,74,95,2,59,44,87,55};
 int i, size = 11 ;
 clrscr();
/* printf("\n Size of the list: %d", size);
 for(i = 1 ; i <= size ; ++i)
 {
  list[i] = rand() % 100;
 }*/
 printf("\n Entered list is as follows:\n");
 display(list, size);
 create_heap(list, size);
 printf("\n Heap\n");
 display(list, size);
 printf("\n\n");
 heap_sort(list,size);
 printf("\n\n Sorted list is as follows :\n\n");
 display(list,size);
 getch();
}

--------------------------------------------------------------------------
C++ :
--------------------------------------------------------------------------
  // HEAP SORT
  // HEAP.CPP
  # include<iostream.h>
  class heap_s
    {
 private:
 public:
    void  heap_sort(int *, int );
    void create_heap(int *, int);
    void display(int *, int);
    };

 //  definition of the function
  void heap_s :: create_heap(int list[], int n )
  {
    for( int k = 2 ; k <= n;  ++k)
       {
  int i = k ;
  int temp = list[k];
  int j = i / 2 ;
  while((i > 1) && (temp > list[j]))
     {
      list[i] = list[j];
      i = j ;
      j = i / 2 ;
      if ( j < 1 )
        j = 1 ;
     }
     list[i] = temp ;
   }
       }
// end of heap creation function
// definition of the function
 void  heap_s :: heap_sort(int list[], int n)
 {
    for( int k = n ; k >= 2; --k)
      {
  int temp = list[1] ;
  list[1] = list[k];
  list[k] = temp ;
  int i = 1 ;
  int value = list[1];
  int j = 2 ;
  if((j+1) < k)
     if(list[j+1] > list[j])
        j ++;
         while((j <= ( k-1)) && (list[j] > value))
   {
    list[i] = list[j];
    i = j ;
    j = 2*i ;
     if((j+1) < k)
       if(list[j+1] > list[j])
         j++;
         else
         if( j > n)
         j = n ;
         list[i] = value;
         } // end of while statement
       cout<<"\n";
       for(int p=1; p<=n; p++)
       cout<<"  "<<list[p];
    } //end for loop
        }
  void heap_s :: display(int list[], int n)
      {
 for( int i = 1 ; i <= n; ++ i)
     {
       cout<<"  "<<list[i];
     }
       }
    void main()
  {
    heap_s sort;
    int list[100];
    int size ;
    cout<<"\n Input the size of the list :";
    cin>>size;

    for(int i = 1 ; i <= size ; ++i)
     {
       cout<<"\n Input values for :" <<i<< " : ";
       cin>>list[i];
     }
     cout<<"\n Entered list is as follows:\n";
     sort.display(list, size);
     sort.create_heap(list, size);
     cout<<"\n Heap\n";
     sort.display(list, size);
     sort.heap_sort(list,size);
     cout<<"\n Sorted list is as follows :\n";
     sort.display(list,size);
  }

Read more »

GTU C PROGRAMS | SHELL SORT PROGRAM

C :
-------------------------------------------------------------------------
/* shell.c */
/* shell sort */
#include <stdio.h>
#include <stdlib.h>
void shell_sort(int array[], int size)
{
 int temp, gap, i, exchange_occurred;
 gap = size / 2;
 do {
  do {
   exchange_occurred = 0;
   for (i = 0; i < size - gap; i++)
    if (array[i] > array[i + gap])
    {
     temp = array[i];
     array[i] = array[i + gap];
     array[i + gap] = temp;
     exchange_occurred = 1;
    }
  } while (exchange_occurred);
 } while (gap == gap / 2);
}
void main(void)
{
 int values[50], i;
 printf("\n Unsorted list is as follows \n");
 for (i = 0; i < 50; i++)
 {
  values[i] = rand() % 100;
  printf(" %d", rand() %100);
 }
 shell_sort(values, 50);
 printf("\n Sorted list is as follows \n");
 for (i = 0; i < 50; i++)
  printf("%d ", values[i]);
}
-------------------------------------------------------------------------
C++
-------------------------------------------------------------------------
// SHELL SORTING
// SHELL.CPP
# include<iostream.h>
#include <stdio.h>
#include <stdlib.h>
   class shell
       {
 private:
  int temp, gap, i, swap;
 public:
  void shell_sort(int *, int );
  void display(int *, int);
       };
void shell :: shell_sort(int array[], int size)
   {
     gap = size / 2;
     int k =0;
   do {
    do {
      swap = 0;
      k++;
      for (i = 0; i < size - gap; i++)
       if (array[i] > array[i + gap])
        { 
          temp = array[i];
          array[i] = array[i + gap];
          array[i + gap] = temp;
   swap = 1;
 }
 for(int t=0;t<size; t++)
  cout<<" "<<array[t];
 cout<<"  Swap="<<swap;
 cout<<"\n";
    } while (swap);
   } while (gap = gap / 2);
  }
  void shell :: display(int list[], int n)
     {
       cout<<"\n Sorted list is as follows:\n";
       for( int i = 0; i < n; i++)
 cout<<"  " << list[i];
     }
   void main(void)
    {
    shell sort;
    int list[50];
    int number;
   cout<<"\n Input the number of elements in the list:";
   cin>>number;
   for (int i = 0; i < number; i++)
   {
      cout<<"\n Input the value for the "<< i+1<<" : ";
      cin>>list[i];
   }
   sort.shell_sort(list, number);
   sort.display(list,number);
 }

Read more »

GTU C PROGRAMS | RADIX SORT PROGRAM

C :
--------------------------------------------------------------------------

/* RADIX SORT */
/* RADIX.C*/
# include<stdio.h>
# include<malloc.h>
# include<stdlib.h>
struct node
{
 int data ;
 struct node *next;
};
typedef struct node node1;
node1 *first;
node1 *pocket[100], *pocket1[100];
void create_node(node1 *, int);
void display(node1 *);
node1 *radix_sort(node1 *);
int large(node1 * );
int numdig(int );
int digit(int , int);
void update(int, node1 *);
node1 *Make_link(int, node1 *);
/* This function create nodes and take input data */
void  create_node(node1 *rec, int n)
{
 int i, j, k;
 for(i = 0 ; i< n; i++)
 {
  rec->next = (node1 *) malloc(sizeof(node1));
  printf("\n First node value: %d: ", i);
  scanf("%d", &rec->data);
  rec = rec->next;
 }
 rec->data = NULL;
 rec->next = NULL;
}
/* Output Function */
void  display(node1 *rec)
{
 while(rec != NULL)
 {
  printf(" %d", rec->data);
  rec= rec->next;
 }
}
/* This radix sort function */
node1 *radix_sort(node1 *rec)
{
 node1 *r, *nex;
 int poc = 0 ;
 int i, j, k;
 int larg = large(rec);
 int m = numdig(larg);
 /* These statements create pockets */
 for(k = 0 ; k < 10; k++)
 {
  pocket[k] = (node1 *)malloc(sizeof(node1));
  pocket1[k] = (node1 *)malloc(9*sizeof(node1));
 }
 /* These statements initialize pockets */
 for(j = 1; j <= m ; j++)
 {
  for(i = 0 ; i < 10 ; i++)
  {
   pocket[i] = NULL;
   pocket1[i] = NULL ;
  }
  r = rec ;
  while(r != NULL)
  {
   int dig = digit(r->data, j);
   nex = r->next ;
   update(dig,r);
   r = nex;
  }
  if(r!= NULL)
  {
   int dig = digit(r->data,j);
   update(dig,r);
  }
  while(pocket1[poc] == NULL)
   poc ++;
  rec = Make_link(poc, rec);
 }
 return(rec);
}
/* This function finds largest number in the list */
int large(node1 *rec)
{
 node1 *save ;
 int p = 0;
 save = rec ;
 while(save != NULL)
 {
  if(save ->data > p)
  {
   p = save->data;
  }
  save = save->next ;
 }
 printf("\n Largest element: %d", p);
 return(p);
}
/* This Function finds number digits in a number */
int numdig(int large)
{
 int temp = large ;
 int num = 0 ;
 while(temp != 0)
 {
  ++num ;
  temp = temp/10 ;
 }
 printf("\n  Number of digits of the number %d is %d\n", large, num);
 return(num);
}
/* This function scarve a number into digits */
int digit(int num, int j)
{
 int dig, i, k;
 int temp = num ;
 for(i = 0 ; i < j ; i++)
 {
  dig = temp % 10 ;
  temp = temp / 10 ;
 }
 printf("\n  %d digit of number  %d is %d", j, num, dig);
 return(dig);
}
/* This function updates the pockets value */
void  update(int dig, node1 *r)
{
 if(pocket[dig] == NULL)
 {
  pocket[dig] = r ;
  pocket1[dig] = r ;
 }
 else
 {
  pocket[dig]->next = r ;
  pocket[dig] = r ;
 }
 r->next = NULL;
}
/* This function create links between the nodes */
node1* Make_link(int poc , node1 *rec)
{
 int i, j, k;
 node1 *pointer;
 rec = pocket1[poc];
 for(i = poc +1 ; i< 10 ; i++)
 {
  pointer = pocket[i-1];
  if(pocket[i] != NULL)
   pointer->next= pocket1[i];
  else
   pocket[i] = pointer ;
 }
 return(rec);
}
/* Main function */
void  main()
{
 node1 *start, *pointer;
 int number;
 printf("\n Input the number of elements in the list:");
 scanf("%d", &number);
 start = (node1 *)malloc(sizeof(node1));
 create_node(start, number);
 printf("\n Given list is as follows \n");
 display(start);
 start = radix_sort(start);
 printf("\n Sorted list is as follows:\n");
 display (start);
}
-------------------------------------------------------------------------
C++

-------------------------------------------------------------------------
 // RADIX SORT
 // RADIX.CPP
#include<iostream.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>
struct node
{
 int data;
 struct node *next;
};
typedef struct node node1;
class radix
{
 public:
  node1 *first;
  node1 *pocket[100], *pocket1[100];
 public:
  void create_node(node1 *, int);
  void display(node1 *);
  node1 *radix_sort(node1 *);
  int large(node1 * );
  int numdig(int );
  int digit(int , int);
  void update(int, node1 *);
  node1 *Make_link(int, node1 *);
};
// This function create nodes and take input data
void radix :: create_node(node1 *rec, int n)
{
 for( int i = 1 ; i<= n; i++)
 {
  rec->next = (node1 *) malloc(sizeof(node1));
  cout<<"\n First node value:"<<i<<":";
  cin>>rec->data;
  rec = rec->next;
 }
 rec->next = NULL;
}
// Output Function
void radix ::  display(node1 * rec)
{
 while(rec)
 {
  cout<<"  "<<rec->data;
  rec= rec->next;
 }
 getch();
}
// This radix sort function
node1 * radix ::  radix_sort(node1 *rec)
{
 int larg = large(rec);
 int m = numdig(larg);
// These statements create pockets
 for(int k = 0 ; k < 10; k++)
 {
  pocket[k] = (node1 *)malloc(sizeof(node1));
  pocket1[k] = (node1 *)malloc(9*sizeof(node1));
 }
// These statements initialize pockets
 for(int j = 1; j <= m ; j++)
 {
  for(int i = 0 ; i < 10 ; i++)
  {
   pocket[i] = NULL;
   pocket1[i] = NULL ;
  }
  node1 *r = rec ;
  while(r != NULL)
  {
   int dig = digit(r->data, j);
   node1 *nex = r->next ;
   update(dig,r);
   r = nex;
  }
  if(r!= NULL)
  {
   int dig = digit(r->data,j);
   update(dig,r);
  }
  int poc = 0 ;
  while(pocket1[poc] == NULL)
   poc ++;
  rec = Make_link(poc, rec);
  cout<<"\n Newly ordered list:\n";
  display(rec);
 }
 return(rec);
}
// This function finds largest number in the list
int radix :: large(node1 *rec)
{
 node1 *save ;
 int p = 0;
 save = rec ;
 while(save != NULL)
 {
  if(save ->data > p)
   p = save->data;
  save = save->next ;
 }
 cout <<"\n Largest element:"<<p;
 return(p);
}
// This Function finds number digits in a number
int radix :: numdig(int large)
{
 int temp = large ;
 int num = 0 ;
 while(temp != 0)
 {
  ++num ;
  temp = temp/10 ;
 }
 cout <<"\n Number of digits of the number "<<large<<" is "<<num ;
 return(num);
}
// This function scarve a number into digits
int radix :: digit(int num, int j)
{
 int dig ;
 int temp = num ;
 for( int i = 0 ; i < j ; i++)
 {
  dig = temp % 10 ;
  temp = temp / 10 ;
 }
 cout<<"\n";
 cout <<j <<" digit of number "<<num <<" is "<<dig;
 getch();
 return(dig);
}
// This function updates the pockets value
void radix :: update(int dig, node1 *r)
{
 if(pocket[dig] == NULL)
 {
  pocket[dig] = r ;
  pocket1[dig] = r ;
 }
 else
 {
  pocket[dig]->next = r ;
  pocket[dig] = r ;
 }
 r->next = NULL;
}
// This function create links between the nodes
node1* radix :: Make_link(int poc , node1 *rec)
{
 node1 *pointer;
 rec = pocket1[poc];
 for(int i = poc +1 ; i< 10 ; i++)
 {
  pointer = pocket[i-1];
  if(pocket[i] != NULL)
   pointer->next= pocket1[i];
  else
   pocket[i] = pointer ;
 }
 return(rec);
}
// Main function
void  main()
{
 radix rad;
 node1 *start, *pointer;
 int number;
 cout<<"\n Input the elements of the list :\n";
 cout<<"\n Input the number of elements in the list:";
 cin>>number;
 start = (node1 *)malloc(sizeof(node1));
 rad.create_node(start, number);
 cout<<"\n Given list is as follows \n";
 rad.display(start);
 start = rad.radix_sort(start);
 cout<<"\n Sorted list is as follows:\n";
 rad.display (start);
}

Read more »

GTU C PROGRAMS | QUICK SORT PROGRAM

C :

/* quick.c */
#include <stdio.h>
#include <stdlib.h>
void quick_sort(int array[], int first, int last)
{
 int temp, low, high, list_separator,i;
 low = first;
 high = last;
 list_separator = array[(first + last) / 2];
 do {
  while (array[low] < list_separator)
   low++;
  while (array[high] > list_separator)
   high--;
  if (low <= high)
  {
   temp = array[low];
   array[low++] = array[high];
   array[high--] = temp;
  }
 } while (low <= high);
 for (i = 0; i < 11; i++)
  printf("%d ", array[i]);
 printf("\n");
 getch();
 if (first < high)
  quick_sort(array, first, high);
 if (low < last)
  quick_sort(array, low, last);
}
void main(void)
{
 int values[]={10,23,64,21,74,95,2,59,44,87,55}, i;
 clrscr();
 for (i = 0; i < 11; i++)
  printf("%d ", values[i]);
 printf("\n");
/* printf("\n Unsorted list is as follows \n");
 for (i = 0; i < 20; i++)
 {
  values[i] = rand() % 100;
  printf(" %d", rand() %100);
 }*/
 quick_sort(values, 0, 10);
 printf("\n Sorted list as follows\n");
 for (i = 0; i < 11; i++)
  printf("%d ", values[i]);
 getch();
}

------------------------------------------------------------------

C++

  // QUICK SORT
  # include<iostream.h>
  # include <stdlib.h>
    class quick
       {
 private: int temp, low, high, pivot;
 public:
 void Q_sort(int *, int , int );
 void display(int *, int );
      };
// sorting function
void quick :: Q_sort(int array[], int first, int last)
 {
   low = first;
   high = last;
   pivot = array[(first + last) / 2];
   do {
     while (array[low] < pivot )
       low++;
     while (array[high] > pivot)
       high--;
     if (low <= high)
      {
 temp = array[low];
 array[low++] = array[high];
 array[high--] = temp;
      }
   } while (low <= high);
  if (first < high)
    Q_sort(array, first, high);
  if (low < last)
    Q_sort(array, low, last);
 }
   void quick :: display(int list[], int n)
     {
       cout<<"\n List after sorting the elements:\n";
       for( int i = 1 ; i <= n ; i++)
       {
  cout<<"  "<<list[i];
       }
     }
 void main(void)
  {
   quick sort;
   int list[100];
   int number ;
   cout<< "\n Input the number of elements in the list:";
   cin>> number;
   for ( int i = 1; i <= number; i++)
    {
     cout<<" Input the value for : "<< i <<" : ";
     cin>>list[i];
    }
  sort.Q_sort(list, 1, number);
  sort.display(list, number);
   }

Read more »

GTU C PROGRAMS MATERIAL | BUBBLE SORT PROGRAM

C :

/* bubble.c */
#include <stdio.h>
#include <stdlib.h>
void bubble_sort(int array[], int size)
{
 int temp, i, j;
 for (i = 0; i < size; i++)
  for (j = 0; j < size; j++)
   if (array[i] < array[j])
   {
    temp = array[i];
    array[i] = array[j];
    array[j] = temp;
   }
}
void main(void)
{
 int values[30], i;
 printf("\n Unsorted list is as follows\n");
 for (i = 0; i < 10; i++)
 {
  values[i] = rand() % 100;
  printf(" %d", rand()%100);
 }
 bubble_sort(values, 10);
 printf("\n Sorted list is as follows\n");
 for (i = 0; i < 10; i++)
  printf("%d ", values[i]);
}

------------------------------------------------------------
C++

 // BUBBLE SORT
 # include<iostream.h>
 # include<conio.h>
     class bubble
      {
 private:
 public:
       void bubble_sort(int , int *); // prototype
       void display(int *, int);
      };
// definition of function
void bubble ::  bubble_sort(int n, int l[])
  {
      int limit = n - 1 ;
      int flag = 1 ;
   for(int j = 0 ; j< n - 1; j++)
   {
     for(int k = 0 ; k<  limit - j ; k++)
      {
        if(l[k] > l[k+1])
   {
    int  temp = l[k];
         l[k] = l[k+1];
         l[k+1] = temp ;
         flag = 0;
    }
        }
    if(flag)
       break ;
       else
        flag = 1;
     }
 }
      void bubble :: display(int list[], int number)
 {
   for( int i = 0 ; i < number ; i++)
   cout<<"  "<< list[i];
 }

 void main()
        {
  bubble sort;
  int number, key, list[200];
  clrscr();
  cout <<"Input the number of elements in the list:";
  cin >> number;
  cout <<"\n Number  of elements in the list is :"<<number;
  for(int i = 0 ; i < number; i++)
  {
  cout<<"\nInput the elements of the list : "<< i+1<<" : ";
  cin >> list[i];
  }
  cout<<"\n Entered list is as follows:\n";
  sort.display(list,number);
  sort.bubble_sort(number, list);
  cout<<"\n After sorting list is as  follows:\n";
  sort.display(list, number);
 }

Read more »

GTU C PROGRAM | SELECTION SORT PROGRAME

C.........

/* select.c */
/* selection sort */
#include <stdio.h>
#include <stdlib.h>
void selection_sort(int array[], int size)
{
 int temp, current, j;
 for (current = 0; current < size; current++)
  for (j = current + 1; j < size; j++)
   if (array[current] > array[j])
   {
    temp = array[current];
    array[current] = array[j];
    array[j] = temp;
   }
}
void main(void)
{
 int values[30], i;
 clrscr();
 printf("\n Unsorted list is as follows \n");
 for (i = 0; i < 30; i++)
 {
  values[i] = rand() % 100;
  printf(" %d", rand() %100);
 }
 selection_sort(values, 30);
 printf("\n Sorted list is as follows \n");
 for (i = 0; i < 30; i++)
 printf("%d ", values[i]);
 getch();
}

----------------------------------------------------------------------------
C++.........

// SELECTION SORT
# include<iostream.h>
#include <stdio.h>
#include <stdlib.h>
 class selection
      {
       private:
  int temp, current, j;
       public:
  void selection_sort(int *, int);
  void display(int *, int );
 };
   void selection :: selection_sort(int array[], int size)
   {
   for (current = 0; current < size; current++)
    for (j = current + 1; j < size; j++)
      if (array[current] > array[j])
 {
   temp = array[current];
   array[current] = array[j];
   array[j] = temp;
 }
  }
     void selection :: display( int list[], int n)
       {
   cout<<"\n Sorted list is as follows :\n";
   for(int i = 0 ; i < n ; i++)
      {
        cout<<"  "<<list[i];
      }
 }
void main(void)
 {
   selection sort;
   int list[30];
   int number;
   cout<<"\n Input the number of the elements:";
   cin>>number;
   for (int i = 0; i < number; i++)
      {
 cout<<"\n Input the values for | "<<i+1<<" | ";
 cin>>list[i];
      }
       sort.selection_sort(list, number);
       sort.display(list, number);
    }

Read more »

data structure - sorting

BUBBLE SORT

BUBBLE _SORT [N,A]


The bubble sort loops through the elements in the list comparing the adjacent element and moves the largest element to the top of the list

Here , n= total no of elements
a= represent the list of element
i &j =are the integer variable
Temp=temporary variable of type integer


step 1: [ Initialize]

I0


Step 2: repeat through step 5 while (i

Step 3: [Initialize]

J0

Step 4: repeat through step 5 while ( j< n-i)


Step 5: if (a[j] > a[j+1]) then

(temp is a temporary variable which store the largest element )

tempa[j]
a[j]  a[j+1]
a[j+1]  temp

endif

step 6: Exit






SELECTION SORTING


SELECTION _SORTING (A,N)



Selection sorting starts from fist element and searches the entire list until finds the minimum value. The sort places minimum value in the first place, select the second element and searches for the second smallest element.

Here , n= represent the size of list
a= represent the list of elements
i &j =are the integer variable
Temp=temporary variable of type integer


Step 1: [initialize]

I0

Step 2: Repeat through step 7 while ( i
Step 3: [initialize]

J I+1

Step 4: Repeat through step 6 while (j
step 5: if (a[j] > a[j]) then

(temp is a temporary variable which store the largest element )

temp a[j]
a[j]  a[j]
a[j]  temp

endif

step 6: j  j+1

step 7: I I+1

step 8: Exit



LINEAR SEARCH

LINEAR _SEARCH (I,N,KEY)

This is a technique to find out an element an unsorted list. In this technique value is compared with the first element if match is found then search is successful otherwise next element from the list is fetched and compared with the key.
This process is continue till the key is found or list is completed.

Where a= represent the list of element
N=represent the no of element in the list
Key=represent the value to be search in the list
Flag =0 means True
Flag =1 means False


Step 1: [initaialize]

I0
Flag1

Step 2: Repeat step 3 for k=0,1,2………..n-1

Step 3: a[i] = key then

Flag0
( prompt the message search successful)
write “search is successful”
(increasing the value of variable I by 1)

II+1

Step 4: [prompt the message if search is not done]
Write “Search is unsuccessful”

Step 5: Exit








BINARY SEARCH

BINARY_SEARCH (KEY,N,A)

Binary search works for sorted list and is a very efficient technique.It is use to find the location of a given element or record in a list.


Where low= lower limit of the list
upper =upper limit of the list
mid= average of low and high

a= represent the list of element
N=represent the no of element in the list
Key=represent the value to be search in the list
Flag =0 means True
Flag =1 means False



Step 1: [initialize]

Low0
uppern-1
Flag1

Step 2: Repeat through step 4 while ( low<=upper)

Step 3: [find average]

mid (low+upper)/2
step 4: if (key = a[I]) then

(change the lower to mid)

uppermid-1
else if
(change upper to mid)
lowmid+1

else if
(when key is found)

(key = a[mid])

write “Search is successful”
flag0

return

step 5: if (flag =1)
write “search is unsuccessful”

step 6: Exit





DOUBLE ORDER LINK LIST

DOUBLE_LIST (HEAD,VAL)

[This function to insert an element in the list which sorted to its info field and value is the info field of the new node and prev is the field which point to previous node]

step 1: [Allocate the memory for the new node]

new=node

step 2: [Copy the information field of the new node]

info(new)=val

step 3: [is the list empty?]

if (temphead=NULL) then

temphead newnode
next(temphead) NULL
return (temphead)

step 4: [does the newnode precede all other node in the list?]

if (val < info(temphead) then

prev(newnode) prev(temphead)
next(newnode) temphead
tempheadnewnode
return (temphead)
else

firsttemphead

while(val > info(next(temphead)) && next(temphead) !=NULL)
tempheadnext(temphead)

endwhile

next(newnode) next(temphead)
prev(newnode) temphead
next(temphead) newnode
return (first)
step 5: exits

Read more »