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);
  }

Posted in: C LANGUAGE, C++ LANGUAGE, Data Structures (DS), DOWNLOAD, gtu, gtu material, GTU MCA 1ST SEMESTER, GTU MCA MATERIAL, MCA, PROGRAMS