30.Heap Sort

Heapsort algorithm is a comparison-based sorting algorithm. The heap sort works as its name suggests. It begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array. After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements.

Heapsort inserts the input list elements into a heap data structure. The largest value (in a max-heap) or the smallest value (in a min-heap) are extracted until none remain, the values having been extracted in sorted order. The heap's invariant is preserved after each extraction, so the only cost is that of extraction.

During extraction, the only space required is that needed to store the heap. In order to achieve constant space overhead, the heap is stored in the part of the input array that has not yet been sorted. (The structure of this heap is described at Binary heap: Heap implementation.)

Heapsort uses two heap operations: insertion and root deletion. Each extraction places an element in the last empty location of the array. The remaining prefix of the array stores the unsorted elements.

Worst case performance	O(nlogn)
Best case performance	O(nlogn)[1]
Average case performance	O(nlogn)
Worst case space complexity	O(n) total, O(1)auxiliary

Heap Sort Program

#include <stdio.h> 
#include <conio.h> 
void main() 
 { 
   int i,v,p,l[100],n,k,t,j; 
   clrscr(); 
   printf("enter the number"); 
   scaf("%d",&n); 
   for(i=1;i<=n;i++) 
     { 
      scanf("%d",&l[i]); 
     } 
   printf("\nentered list are as follows"); 
   for(i=1;i<=n;i++) 
     { 
       printf("\t%d",l[i]); 
     } 
/*creation of heap*/ 
   for(k=2;k<=n;k++) 
     { 
       i=k; 
       t=l[k]; 
       j=i/2; 
         while((i>1)&&(t > l[j])) 
         { 
          l[i]=l[j]; 
          i=j; 
          j=i/2; 
          if(j<1) 
          j=1; 
         } 
       l[i]=t; 
      } 

    printf("\nHEAP"); 

    for(i=1;i<=n;i++) 
     { 
      printf("\t%d",l[i]); 
     } 
      printf("\n"); 
  //heapsort 
    for(k=n;k>=2;--k) 
   { 
     t=l[1]; 
     l[1]=l[k]; 
     l[k]=t; 
     i=1; 
     v=l[1]; 
     j=2; 
     if(j+1) 
       if(l[j+1]>l[j]) 
         j++; 
     while((j<=(k-1))&&(l[j]>v)) 
      { 
       l[i]=l[j]; 
       i=j; 
       j=2*i; 
       if(j+1) 
          if(l[j+1]>l[j]) 
             j++; 
     else 
        if(j>n) 
          j=n; 
          l[i]=v; 
      } 
     for(p=1;p<=n;p++) 
      { 
       printf("\t%d",l[p]); 
      } 
       printf("\n"); 
     } 
    printf("\nthe sorted list "); 
    for(i=1;i<=n;i++) 
     { 
      printf("\t%d",l[i]); 
     } 
getch(); 

} 

Output:

enter the number
5
8
6
2
4
45

entered list are as follows     8       6       2       4       45
HEAP    45      8       2       4       6
8       6       2       4       45
6       4       2       8       45
2       4       6       8       45
4       2       6       8       45

the sorted list         4       2       6       8       45

If you like this please Link Back to this article...

<a href="https://learning-tutorial.blogspot.com/2011/01/30heap-sort_21.html">30.Heap Sort</a>

30.Heap Sort

Heapsort algorithm is a comparison-based sorting algorithm. The heap sort works as its name suggests. It begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array. After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements.

Heapsort inserts the input list elements into a heap data structure. The largest value (in a max-heap) or the smallest value (in a min-heap) are extracted until none remain, the values having been extracted in sorted order. The heap's invariant is preserved after each extraction, so the only cost is that of extraction.

During extraction, the only space required is that needed to store the heap. In order to achieve constant space overhead, the heap is stored in the part of the input array that has not yet been sorted. (The structure of this heap is described at Binary heap: Heap implementation.)

Heapsort uses two heap operations: insertion and root deletion. Each extraction places an element in the last empty location of the array. The remaining prefix of the array stores the unsorted elements.

Worst case performance	O(nlogn)
Best case performance	O(nlogn)[1]
Average case performance	O(nlogn)
Worst case space complexity	O(n) total, O(1)auxiliary

Heap Sort Program

#include <stdio.h> 
#include <conio.h> 
void main() 
 { 
   int i,v,p,l[100],n,k,t,j; 
   clrscr(); 
   printf("enter the number"); 
   scaf("%d",&n); 
   for(i=1;i<=n;i++) 
     { 
      scanf("%d",&l[i]); 
     } 
   printf("\nentered list are as follows"); 
   for(i=1;i<=n;i++) 
     { 
       printf("\t%d",l[i]); 
     } 
/*creation of heap*/ 
   for(k=2;k<=n;k++) 
     { 
       i=k; 
       t=l[k]; 
       j=i/2; 
         while((i>1)&&(t > l[j])) 
         { 
          l[i]=l[j]; 
          i=j; 
          j=i/2; 
          if(j<1) 
          j=1; 
         } 
       l[i]=t; 
      } 

    printf("\nHEAP"); 

    for(i=1;i<=n;i++) 
     { 
      printf("\t%d",l[i]); 
     } 
      printf("\n"); 
  //heapsort 
    for(k=n;k>=2;--k) 
   { 
     t=l[1]; 
     l[1]=l[k]; 
     l[k]=t; 
     i=1; 
     v=l[1]; 
     j=2; 
     if(j+1) 
       if(l[j+1]>l[j]) 
         j++; 
     while((j<=(k-1))&&(l[j]>v)) 
      { 
       l[i]=l[j]; 
       i=j; 
       j=2*i; 
       if(j+1) 
          if(l[j+1]>l[j]) 
             j++; 
     else 
        if(j>n) 
          j=n; 
          l[i]=v; 
      } 
     for(p=1;p<=n;p++) 
      { 
       printf("\t%d",l[p]); 
      } 
       printf("\n"); 
     } 
    printf("\nthe sorted list "); 
    for(i=1;i<=n;i++) 
     { 
      printf("\t%d",l[i]); 
     } 
getch(); 

} 

Output:

enter the number
5
8
6
2
4
45

entered list are as follows 8 6 2 4 45
HEAP 45 8 2 4 6
8 6 2 4 45
6 4 2 8 45
2 4 6 8 45
4 2 6 8 45

the sorted list 4 2 6 8 45

If you like this please Link Back to this article...

<a href="https://learning-tutorial.blogspot.com/2011/01/30heap-sort.html">30.Heap Sort</a>

29.Quick Sort

Quicksort sorts a list based on the divide and conquer strategy. In quicksort algorithm we divide the list into two sub-lists, sort these sub-lists and recursively until the list is sorted; The basic steps of quicksort algorithm are as follows:

1. Choose a key element in the list which is called a pivot.
2. Reorder the list with the rule that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it. After the partitioning, the pivot is in its final position.
3. Recursively reorder two sub-lists: the sub-list of lesser elements and the sub-list of greater elements.

Worst case performance	O(n2)
Best case performance	O(n log n)
Average case performance	O(n log n)
Worst case space complexity	O(n)

Quick Sort Program

#include<stdio.h>

int main(){

  int x[20],size,i;

  printf("\nEnter size of the array :");

  scanf("%d",&size);

  printf("\nEnter %d elements :",size);

  for(i=0;i<size;i++)

    scanf("%d",&x[i]);

  quicksort(x,0,size-1);

  printf("\nSorted elements :");

  for(i=0;i<size;i++)

    printf(" %d",x[i]);

  return 0;

}

quicksort(int x[10],int first,int last){

    int pivot,j,temp,i;

     if(first<last){

         pivot=first;

         i=first;

         j=last;

         while(i<j){

             while(x[i]<=x[pivot]&&i<last)

                 i++;

             while(x[j]>x[pivot])

                 j--;

             if(i<j){

                 temp=x[i];

                  x[i]=x[j];

                  x[j]=temp;

             }

         }

         temp=x[pivot];

         x[pivot]=x[j];

         x[j]=temp;

         quicksort(x,first,j-1);

         quicksort(x,j+1,last);

    }

}

Output of the Program:

Enter the size of the array:5

Enter 5 elements:6 8 5 9 3

Sorted elements:3 5 6 8 9

If you like this please Link Back to this article...

<a href="https://learning-tutorial.blogspot.com/2011/01/29quick-sort_21.html">29.Quick Sort</a>

29.Quick Sort

Quicksort sorts a list based on the divide and conquer strategy. In quicksort algorithm we divide the list into two sub-lists, sort these sub-lists and recursively until the list is sorted; The basic steps of quicksort algorithm are as follows:

1. Choose a key element in the list which is called a pivot.
2. Reorder the list with the rule that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it. After the partitioning, the pivot is in its final position.
3. Recursively reorder two sub-lists: the sub-list of lesser elements and the sub-list of greater elements.

Quick Sort Program

#include<stdio.h>

int main(){

  int x[20],size,i;

  printf("\nEnter size of the array :");

  scanf("%d",&size);

  printf("\nEnter %d elements :",size);

  for(i=0;i<size;i++)

    scanf("%d",&x[i]);

  quicksort(x,0,size-1);

  printf("\nSorted elements :");

  for(i=0;i<size;i++)

    printf(" %d",x[i]);

  return 0;

}

quicksort(int x[10],int first,int last){

    int pivot,j,temp,i;

     if(first<last){

         pivot=first;

         i=first;

         j=last;

         while(i<j){

             while(x[i]<=x[pivot]&&i<last)

                 i++;

             while(x[j]>x[pivot])

                 j--;

             if(i<j){

                 temp=x[i];

                  x[i]=x[j];

                  x[j]=temp;

             }

         }

         temp=x[pivot];

         x[pivot]=x[j];

         x[j]=temp;

         quicksort(x,first,j-1);

         quicksort(x,j+1,last);

    }

}

Output of the Program:

Enter the size of the array:5

Enter 5 elements:6 8 5 9 3

Sorted elements:3 5 6 8 9

If you like this please Link Back to this article...

<a href="https://learning-tutorial.blogspot.com/2011/01/29quick-sort.html">29.Quick Sort</a>

28.Selection Sort

Selection Sort Program
Selection sort is a simplicity sorting algorithm. It works as its name as it is. Here are basic steps of selection sort algorithm:
1. Find the minimum element in the list
2. Swap it with the element in the first position of the list
3. Repeat the steps above for all remainder elements of the list starting at the second position.

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

#define MAXSIZE 500
void selection(int elements[], int maxsize);
int elements[MAXSIZE],maxsize;
int main()
{
  int i;
  printf("\nHow many elements you want to sort:" );
  scanf("%d",&maxsize);
  printf("\nEnter the values one by one: ");
  for (i = 0; i < maxsize; i++)
   {
     printf ("\nEnter element %i :",i);
     scanf("%d",&elements[i]);
   }
  printf("\nArray before sorting:\n");
  for (i = 0; i < maxsize; i++)
  printf("[%i], ",elements[i]);
  printf ("\n");
  selection(elements, maxsize);
  printf("\nArray after sorting:\n");
  for (i = 0; i < maxsize; i++)
      printf("[%i], ", elements[i]);
 }

void selection(int elements[], int array_size)
{
  int i, j, k;
  int min, temp;
  for (i = 0; i < maxsize-1; i++)
   {
     min = i;
     for (j = i+1; j < maxsize; j++)
       {
         if (elements[j] < elements[min])
         min = j;
       }
  temp = elements[i];
  elements[i] = elements[min];
  elements[min] = temp;
  }
}

OUTPUT:

How many elements you want to sort:5

Enter the values one by one:
Enter element 0:8
Enter element 1:5
Enter element 2:6
Enter element 3:4
Enter element 4:2

Array before sorting:
[8],[5],[7],[4],[2].

Array after sorting:
[2],[4],[5],[6],[8].

If you like this please Link Back to this article...

<a href="https://learning-tutorial.blogspot.com/2011/01/28selection-sort.html">28.Selection Sort</a>

27.Insertion Sort

Logic : Here, sorting takes place by inserting a particular element at the appropriate position, that’s why the name- insertion sorting. In the First iteration, second element A[1] is compared with the first element A[0]. In the second iteration third element is compared with first and second element. In general, in every iteration an element is compared with all the elements before it. While comparing if it is found that the element can be inserted at a suitable position, then space is created for it by shifting the other elements one position up and inserts the desired element at the suitable position. This procedure is repeated for all the elements in the list.

If we complement the if condition in this program, it will give out the sorted array in descending order. Sorting can also be done in other methods, like selection sorting and bubble sorting, which follows in the next pages.

Insertion Sort Program

#include<stdio.h>  
#include<conio.h>  
  
   void insertion(int a[],int n)  
   {  
  
    int i,j,x,k;  
  
           for(i=1;i<=n-1;i++)  
    
                {  
                       j=i;  
  
                       x=a[i];  
  
  
                       while(a[j-1]>x && j>0)  
  
                                 {  
  
                                   a[j]=a[j-1];  
                                    j=j-1;  
  
                                 }  
  
                        a[j]=x;  
  
  
                       printf("\n\n The array after pass no.%d: ",i);  
                       for(k=0;k<=n-1;k++)  
                      printf("%4d",a[k]);  
  
  
                 }//end for.  
  
  
   } //end function.  
  
   void main()  
  
   {  
  
     int a[1000],n,i;  
  
     clrscr();  
  
     printf("\n\nEnter an integer value for total no.s of elements to be sorted: ");  
     scanf("%3d",&n);  
  
     for(i=0;i<=n-1;i++)  
  
          {  
  
            printf("\n\nEnter an integer value for element no.%d: ",i+1);  
            scanf("%4d",&a[i]);  
  
          }  
  
  
     insertion(a,n);  
  
  
     printf("\n\n\nFinally sorted array is : ");  
     for(i=0;i<=n-1;i++)  
     printf("%4d",a[i]);  
  
  
   }//end program.  
  
/* 
 

OUTPUT:

Enter an integer value for total no.s of elements to be sorted: 6


Enter an integer value for element no.1: 67


Enter an integer value for element no.2: 34


Enter an integer value for element no.3: -23


Enter an integer value for element no.4: 100


Enter an integer value for element no.5: 0


Enter an integer value for element no.6: -68


The array after pass no.1: 34 67 -23 100 0 -68

The array after pass no.2: -23 34 67 100 0 -68

The array after pass no.3: -23 34 67 100 0 -68

The array after pass no.4: -23 0 34 67 100 -68

The array after pass no.5: -68 -23 0 34 67 100


Finally sorted array is : -68 -23 0 34 67 100

If you like this please Link Back to this article...

<a href="https://learning-tutorial.blogspot.com/2011/01/27insertion-sort.html">27.Insertion Sort</a>

2.C Data Types

Data types are used to store various types of data that is processed by program. Data type attaches with variable to determine the number of bytes to be allocate to variable and valid operations which can be performed on that variable. C supports various data types such as character, integer and floating-point types.

Character Data Type

C stores character type internally as an integer. Each character has 8 bits so we can have 256 different characters values (0-255).

Character set is used to map between an integer value and a character. The most common character set is ASCII.

Let take a look at example of using a variable which hold character 'A'.

01	#include <stdio.h>

02

03	void main()

04

{

05	char ch = 'A';

06	printf("%c\n",ch);

07	ch = 65;// using integer representation

08	printf("%c\n",ch);

09	ch = '\x41';   // using hexadecimal representation

10	printf("%c\n",ch);

11	ch = '\101';   // using octal representation

12	printf("%c\n",ch);

13

}

Here is the output

A
A
A
A

Integer Data Type

Integer data types are used to store numbers and characters. Here is the table of integer data type in various forms:

Data Type	Memory Allocation	Range
signed char	1 byte	−27 to 27−1 (−128 to 127)
Unsigned char	1 byte	0 to 28−1 (0 to 255)
short	2 bytes	−215 to 215 −1 (−32768 to 32767)
Unsigned short	2 bytes	0 to 216 −1 (0 to 65535)
long int	4 bytes	231 to 231−1 (2,147,483,648 to 2,147,483,647)
int	2 or 4 bytes depending on implementation	Range for 2 or 4 bytes as given above

Floating-point Data Type

The floating-point data types are used to represent floating-point numbers. Floating-point data types come in three sizes: float (single precision), double (double precision), and long double (extended precision). The exact meaning of single, double, and extended precision is based on implementation defined. Choosing the right precision for a problem where the choice matters requires understanding of floating point computation.

Floating-point literal

Floating-point literal is double by default. You can use the suffix f or F to get a floating-point literal 3.14f or 3.14F

Type Conversion

Type conversion occurs when an expression has a mixed data types. At this time, the compiler will try to convert from lower to higher type, because converting from higher to lower may cause loss of precision and value.C has following rules for type conversion.

• Integer types are lower than floating-point types.
• Signed types are lower than unsigned types.
• Short whole-number types are lower than longer types.
• The hierarchy of data types is as follows: double, float, long, int, short, char.

So based on those rules, we have general rules for type conversion:

• Character and short data are promoted to integer.
• Unsigned char and unsigned short are converted to unsigned integer.
• If the expression includes unsigned integer and any other data type, the other data type is converted to an unsigned integer and the result will be unsigned integer.
• If the expression contains long and any other data type, that data type is converted to long and the result will be long.
• Float is promoted to double.
• If the expression includes long and unsigned integer data types, the unsigned integer is converted to unsigned long and the result will be unsigned long.
• If the mixed expression is of the double data type, the other operand is also converted to double and the result will be double.
• If the mixed expression is of the unsigned long data type, then the other operand is also converted to double and the result will be double.

Conversion Type Casting

When we want to convert the value of a variable from one type to another we can use type casting. Type casting does not change the actual value of variable. It can be done using a cast operator (unary operator).

If you like this please Link Back to this article...

<a href="https://learning-tutorial.blogspot.com/2011/01/2c-data-types.html">2.C Data Types</a>