C program for Heap Sort

#include <stdio.h> 

#include <stdlib.h>

 

// To heapify a subtree rooted with node i which is 

// an index in arr[]. n is size of heap 

void heapify(int arr[], int n, int i) //Max heap

{ 

    int root = i; // Initialize largest as root 

    int l = 2*i + 1; // left = 2*i + 1 

    int r = 2*i + 2; // right = 2*i + 2 

  

    // If left child is larger than root 

    if (l < n && arr[l] > arr[root]) 

        root = l; 

  

    // If right child is larger than largest so far 

    if (r < n && arr[r] > arr[root]) 

        root = r; 

  

    // If largest is not root 

    if (root != i) 

    { 

        int tmp=arr[i];

        arr[i]=arr[largest];

        arr[largest]=tmp;  

        // Recursively heapify the affected sub-tree 

        heapify(arr, n, root); 

    } 

} 

/* A utility function to print array of size n */

void printArray(int arr[], int n) 

{ 

    int i; 

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

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

    printf("\n"); 

}

  

// main function to do heap sort 

void heapSort(int arr[], int n) 

{ 

    int i=0;

    // Build heap (rearrange array) 

    for (i = n / 2 - 1; i >= 0; i--) 

        heapify(arr, n, i); 

    

    printArray(arr, n); 

    // One by one extract an element from heap 

    for (i=n-1; i>=0; i--) 

    { 

        printf("\nPass %d\n",n-i);

        // Move current root to end 

        //swap(arr[0], arr[i]);

        int tmp=arr[i];

        arr[i]=arr[0];

        arr[0]=tmp;   

        printArray(arr, n); 

        // call max heapify on the reduced heap 

        heapify(arr, i, 0); 

        printArray(arr, n); 

    }

} 

 

  

// Driver program 

int main() 

{ 

    int arr[] = {12, 11, 13, 5, 6, 7}; 

    int n = sizeof(arr)/sizeof(arr[0]); 

  

    heapSort(arr, n); 

  

    printf("\nSorted array is \n"); 

    printArray(arr, n); 

}

C program for merge sort

#include <stdio.h>

int n;

void msort(int arr[], int ll,int m,int uu) 

{ 

    int i, j; 

    int n1 = m-ll+1; 

    int n2 = uu-m; 

    

    int L[n1];

    int R[n2];

    

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

    {

        L[i]=arr[ll+i];

    }

    for (j=0;j<n2;j++)

    {

        R[j]=arr[m+j+1];

    }

    i=0;

    j=0;

    int k=ll;

    while(i<n1 && j<n2)

    {

        if(L[i]<=R[j])

        {

            arr[k]=L[i];

            i++;

        }

        else 

        {

            arr[k]=R[j];

            j++;

        }

        k++;

    }

    while(i<n1)

    {

        arr[k]=L[i];

        k++;

        i++;

    }

    while(j<n2)

    {

        arr[k]=R[j];

        k++;

        j++;

    }

} 

void merge(int ar[],int l,int u)

{

    int mid=(l+u)/2;

    if(l<u)

    {

        merge(ar,l,mid);

        merge(ar,mid+1,u);

        msort(ar,l,mid,u);

    }    

}

int main(void)

{

    n=8; // Length of array

    int ar[]={12,11,13,5,6,7,7,-34};

    int i=0;

    merge(ar,0,n-1);

    printf("\nSorted array is \n");

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

    {

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

    }

}

C program for randomized Quick Sort

//Using lomuto algo for randomized pivot quick sort

#include <stdio.h>

#include <stdlib.h>

void swap(int a,int b,int ar[])

{

    int tmp=ar[a];

    ar[a]=ar[b];

    ar[b]=tmp;

}

int partition(int ar[],int i,int j)

{

    int index=i;

    int pivot=ar[index];

    while(i<j)

    {

        while(pivot<ar[j])

        {

            j--;

        }

        while(pivot>=ar[i])

        {

            i++;

        }

        if(i<j)

        {

            swap(i,j,ar);

        }

    }

    swap(index,j,ar);

    return j;

}

int random_pivot(int ar[],int left,int right)  //Choose a random pivot and swap with lowest bound 

{

    int gap=(right-left+1);  //Length of subarray

    int r=left+rand()%gap;

    swap(left,r,ar);

    return partition(ar,left,right);

}

void sort(int ar[],int left,int right)

{   

    int pivot;

    if(left<right)

    {

        pivot=random_pivot(ar,left,right);

        sort(ar,left,pivot-1);

        sort(ar,pivot+1,right);

    }

}

int main(void)

{

    int ar[]={546,-1,-2,12,10,80,30,90,1,89,-4,50,70};

    int left=0;

    int right=(int)(sizeof(ar)/sizeof(int)) -1;

    sort(ar,left,right);

    printf("\nSorted array\n");

    int i=0;

    for (;i<=right;i++)

    {

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

    }

}

C program for Quick Sort

#include <stdio.h>

#include <stdlib.h>

void sort(int ar[],int left,int right)

{   

    int pivot;

    if(left<right)

    {

        pivot=partition(ar,left,right);

        sort(ar,left,pivot-1);

        sort(ar,pivot+1,right);

    }

}

int partition(int ar[],int i,int j)

{

    int pivot=ar[i];

    int index=i;

    while(i<j)

    {

        while(pivot<ar[j])

        {

            j--;

        }

        while(pivot>=ar[i])

        {

            i++;

        }

        if(i<j)

        {

            int tmp=ar[i];

            ar[i]=ar[j];

            ar[j]=tmp;

        }

    }

    int tmp=ar[j];

    ar[j]=ar[index];

    ar[index]=tmp;

    return j;

}

int main(void)

{

    int ar[]={546,-1,-2,12,10,80,30,90,1,89,-4,50,70};

    int left=0;

    int right=(int)(sizeof(ar)/sizeof(int)) -1;

    sort(ar,left,right);

    printf("\nSorted array\n");

    int i=0;

    for (;i<=right;i++)

    {

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

    }

}

C program for Selection Sort

#include <stdio.h>

int sort(int ar[],int n)

{

    int i=0;

    int j=0;

    int temp;

    int min;

    int pos;

    for(;i<n;i++)

    {

        min=ar[i];

        pos=i;

        for(j=i;j<n;j++)

        {

            if(ar[j]<min)

            {

                pos=j;

                min=ar[j];

            }

        }

        if(pos==i)

        {

            continue;

        }

        else 

        {

            temp=ar[i];

            ar[i]=min;

            ar[pos]=temp;

        }

    }

}

int main(void)

{

    int n;

    

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

    scanf("%d",&n);

    int ar[n];  //Declaring array

    int i=0;

    for (;i<n;i++)

    {

        printf("\nEnter the array element :-  ");

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

    }

    sort(ar,n);

    printf("\nPrinting sorted array\n");

    

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

    {

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

    }    

}

C program for Shell Sort

#include<stdio.h>

#include<stdlib.h>

void sort(int ar[],int n)

{

    unsigned int i=0;

    unsigned int j=0;

    unsigned int gap=0;

    for (gap=n/2;gap>0;gap/=2)

    {

        for (i=gap;i<n;i++)

        {

            int temp=ar[i];

            for (j=i;j>0;j=j-gap)

            {

                if(ar[j-gap]>temp)

                {

                    ar[j]=ar[j-gap];

                }

                else 

                    break;

            }

            ar[j]=temp;

        }

    } 

}

int main(void)

{

    int n;

    int ar[]={45,13,-1,90,12};

    n=(int)(sizeof(ar)/sizeof(int));

    sort(ar,n);

    

    int i=0;

    printf("\nSorted array:- \n");

    for (;i<n;i++)

    {

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

    }

}

Binary Search for Sorted Array

Binary Search for Sorted Array

#include<stdio.h>
int main()
{
   int c, first, last, middle, n, search, array[100];
   printf("Enter number of elements:\n");
   scanf("%d",&n);
   printf("Enter %d integers:\n", n);
   for (c = 0; c < n; c++)
      scanf("%d",&array[c]);
   printf("Enter the value to find:\n");
   scanf("%d", &search);
   first = 0;
   last = n - 1;
   middle = (first+last)/2;
   while (first <= last) {
      if (array[middle] < search)
         first = middle + 1;   
      else if (array[middle] == search) {
         printf("%d is present at index %d.\n", search, middle+1);
         break;
      }
      else
         last = middle - 1;
      middle = (first + last)/2;
   }
   if (first > last)
      printf("Not found! %d is not present in the list.\n", search);
   return 0; 
}



Sample Output:

Enter number of elements:

5

Enter 5 integers:

1
9
22
24
46

Enter the value to find:

24

24 is present at index 4.

Linear Search in C

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
int main()
{
int i,num,f=0,pos=-1,*arr,n;
printf("\n Enter the number of elements ");
scanf("%d",&n);
arr=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
  printf("\n Enter element %d :",i);
  scanf("%d",(arr+i));
}
printf("\n Enter the element to be searched ");
scanf("%d",&num);
for(i=0;i<n;i++)
{
  if(*(arr+i)==num)
  {
  f=1;
  pos=i;
  break;
  }
}
if(f==1)
printf("\n %d is found at the position %d. ",num,pos);
if(f==0)
printf("\n The searched number %d does not exist in the array. ",num);
getch();
return 0;
}

Insertion Sort in C

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
int main()
{
int j,i,n,*arr,temp;
printf("\n Enter the number of elements ");
scanf("%d",&n);
arr=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
 printf("\n Enter the element %d ",i);
 scanf("%d",&arr[i]);
}
for(i=1;i<n;i++)
{
temp=arr[i];
j=i-1;
while(temp<arr[j] && j>=0)
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=temp;
}
printf("\n Sorted array is...... ");
for(i=0;i<n;i++)
printf("\t %d ",arr[i]);
getch();
return 0;
}

Binary Search in C

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
main()
{
int c=0,f=0,i,num,beg,*arr,n,end;
printf("\n Enter the number of elements ");
scanf("%d",&n);
arr=(int*)malloc(n*2);
for(i=0;i<n;i++)
{
  printf("\n Enter element %d :",i);
  scanf("%d",(arr+i));
}
printf("\n Enter the element to be searched ");
scanf("%d",&num);
beg=0,end=n-1;
while(beg<=end)
{
int mid=(beg+end)/2;
if(*(arr+mid)==num)
{
c++;
printf("\n %d is present in the array at the position = %d ",num,mid);
f=1;
break;
}
else if(*(arr+mid)>num)
end=mid-1;
else
beg=mid+1;
c++;
}
if(beg>end && f==0)
printf("\n %d does not exist in the array ",num);
getch();
}

Bubble sort in C

/*Program to sort a given array using bubble sort*/

#include<malloc.h>
#include<stdio.h>
#include<conio.h>
main()
{
int j,i,n,*arr,temp;
printf("\n Enter the number of elements ");
scanf("%d",&n);
arr=(int*)malloc(n*2);
for(i=0;i<n;i++)
{
 printf("\n Enter the element %d ",i);
 scanf("%d",(arr+i));
}
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(*(arr+j)>*(arr+j+1))
{
temp=*(arr+j);
*(arr+j)=*(arr+j+1);
arr[j+1]=temp;
}
}
}
printf("\n The sorted array is: ");
for(i=0;i<n;i++)
printf("\t %d ",*(arr+i));
getch();
}