Binary Search Algorithm – GCC Program for UBUNTU

Introduction

Click on the following link to download the PPT of Binary Search Algorithm.

BinarySearchAlgorithm

In computer science, binary search or half-interval search algorithm finds the position of a specified value (the input “key”) within a sorted array. In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element’s key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special “Not found” indication is returned.

Implementation

//**********************************************************
// Binary Search Algorithm Implementation
//**********************************************************
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<dos.h>

int sequential(int *a, int n, int x)
{
int i;
for(i=0;i<n;i++)
if((*(a+i)) >= x) return i;
return n;
}

int divnconq(int *a,int n,int x)
{
if (n==0 || x>(*(a+(n-1)))) return n;
else return binrec(&a[0],0,n-1,x);
}

int binrec(int *a,int st, int n,int x)
{
int k;
if(st==n) return st;
k=(st+n)/2;
if(x<=(*(a+k))) return binrec(&a[0],st,k,x);
else return binrec(&a[0],k+1,n,x);
}

void main()
{
int a[100],x,n,i;
struct time t1,t2,t3,t4;
clrscr();

printf(“Enter the total Number of Elements: “);
scanf(“%d”,&n);
printf(“\nEnter %d elements in Ascending Order only: “,n);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);

printf(“\nNow, Enter the element you want to search: “);
scanf(“%d”,&x);

printf(“\n************** Search Element(SEQUENTIAL) **************”);
printf(“\nPosition (Index) for %d element is %d”,x,sequential(&a[0],n,x));
printf(“\n********************************************************\n”);

printf(“\n************** Binary Search (DIVIDE & CONQUER) **************”);
printf(“\nPosition (Index) for %d element is %d”,x,divnconq(&a[0],n,x));
printf(“\n********************************************************\n\n”);
getch();
}

Heap Sort Algorithm – GCC Program for UBUNTU

Introduction

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort.

The first loop, the Θ(n) “heapify” phase, puts the array into heap order. The second loop, the O(n·lg(n)) “sortdown” phase, repeatedly extracts the maximum and restores heap order.

For more details about Heap Sort click here:

OR  Click following link to download PDF for Heap Sort Algorithm.

HeapSortAlgorithm.pdf

 

Implementation

//**********************************************************
// Heap Sort Algorithm Implementation & Analysis.
//**********************************************************

#include<stdio.h>

int t[25],tsize; /* GLOBAL TREE AS AN ARRAY WITH IT’S SIZE */

/* Find a Parent Node of a given node */
int parent(int i)
{ return (i/2); }

/* Find a Left Child of a given node */
int left(int i)
{ return (i*2); }

/* Find a Right Child of a given node */
int right(int i)
{ return ((i*2)+1); }

void max_heapify(int i)
{
int l,r,largest,temp,k;
l=left(i);
r=right(i);
/*
printf(“\n————————————\n”);
for(k=1;k<=tsize;k++)
printf(” %d -“,t[k]);
*/
if(l<=tsize && t[l] > t[i])
largest=l;
else largest=i;

if(r<=tsize && t[r] > t[largest])
largest=r;

if(largest!=i)
{
temp=t[i];
t[i]=t[largest];
t[largest]=temp;

max_heapify(largest);
}
}

int main()
{
int i,temp,tstemp;

printf(“Enter Size of Tree:”);
scanf(“%d”,&tsize);

printf(“Now Enter %d Elements of Binary Tree\n”,tsize);
for(i=1;i<=tsize;i++)
scanf(“%d”,&t[i]);

printf(“\n*****************\nInitial Random Binary Tree:\n”);
for(i=1;i<=tsize;i++)
printf(” %d -“,t[i]);
printf(“\n*****************\n”);

/* BUILD-MAX-HEAP PROCEDURE */
for(i=(int)(tsize/2);i>=1;i–)
max_heapify(i);

printf(“\n*****************\n FINAL MAX-HEAP:\n”);
for(i=1;i<=tsize;i++)
printf(” %d -“,t[i]);
printf(“\n*****************\n”);

/* HEAP-SORT PROCEDURE */
tstemp=tsize;
for(i=tsize;i>=2;i–)
{
temp=t[i];
t[i]=t[1];
t[1]=temp;

tsize=tsize-1;

max_heapify(1);
}

printf(“\n*******************************\n FINAL HEAP-SORTED TREE:\n”);
for(i=1;i<=tstemp;i++)
printf(” %d -“,t[i]);
printf(“\n*************************\n”);

return 0;
}

Merge Sort – GCC Program for Ubuntu

Click following links to download merge sort algorithm PPTs.

MergeSort – PPT1

MergeSort – PPT2

 

Implementation

//**************************************************************************
// Implementation of Merge Sort Algorithm using Divide & Conquer Method.
//**************************************************************************

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

int n;
int main()
{

int i, low, high;
int a[100];
void mergesort(int a[100],int low, int high);
void display(int a[100]);

printf(“\n***************** Merge Sort *****************\n”);
printf(“\nEnter the length of list:”);
scanf(“%d”,&n);
printf(“\nEnter list of elements: “);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
low=0;
high=n-1;
mergesort(a,low,high);
display(a);
printf(“\n”);
return 0;
}

/* This function split the list into sublists */
void mergesort(int a[100],int low, int high)
{
int mid;
void combine(int a[100],int low,int mid,int high);
if(low<high)
{
mid=(low+high)/2; //split the list at mid
mergesort(a,low,mid); //first sublist
mergesort(a,mid+1,high); //second sublist
combine(a,low,mid,high); //merging of two sublists
}
}
/* This function merge the two sublists */
void combine(int a[100],int low, int mid, int high)
{
int i,j,k;
int temp[100];
k=low;
i=low;
j=mid+1;
while(i<=mid && j<=high)
{
if(a[i]<=a[j])
{
temp[k]=a[i];
i++;
k++;
}
else
{
temp[k]=a[j];
j++;
k++;
}
}
while(i<=mid)
{
temp[k]=a[i];
i++;
k++;
}
while(j<=high)
{
temp[k]=a[j];
j++;
k++;
}
for(k=low;k<=high;k++)
a[k]=temp[k];
}

void display(int a[100])
{
int i;
printf(“\n****************** The Sorted Array Is… *****************\n”);
for(i=0;i<n;i++)
printf(“%d – “,a[i]);
}

Quick Sort – GCC Program for Ubuntu

Click following links to download Quick Sort PPTs.

QuickSort – PPT 1

QuickSort – PPT 2

 

Implementation

//**************************************************************************
// Implementation of Quick Sort Algorithm using Divide & Conquer Method.
//**************************************************************************

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

#define SIZE 10

void quick(int a[SIZE],int,int);
int partition(int a[SIZE],int,int);
void swap(int a[SIZE],int *,int *);
int n;

int main()
{
int i;
int a[SIZE];

printf(“\n************** Quick Sort Algorithm **************\n”);
printf(“\nEnter total numbers to sort:”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
printf(“\n Enter %dth number: “,i+1);
scanf(“%d”,&a[i]);
}
quick(a,0,n-1);
printf(“\n\n*********** Sorted Array Is.. ****************\n”);
for(i=0;i<n;i++)
printf(“\t%d”,a[i]);
printf(“\n”);
return 0;
}

void quick(int a[SIZE],int low, int high)
{
int m,i;
if(low<high)
{
m=partition(a,low,high);
quick(a,low,m-1);
quick(a,m+1,high);
}
}

int partition(int a[SIZE],int low,int high)
{
int pivot=a[low],i=low,j=high;
while(i<=j)
{
while(a[i]<=pivot)
i++;
while(a[j]>pivot)
j–;
if(i<j)
swap(a,&i,&j);
}
swap(a,&low,&j);
return j;
}

void swap(int a[SIZE],int *i,int *j)
{
int temp;
temp=a[*i];
a[*i]=a[*j];
a[*j]=temp;
}

 

Dijkstra’s Algorithm for Shortest Path Problem – GCC Program for Ubuntu

Dijkstra’s Algorithm finds the shortest path with the lower cost in a Graph. Dijkstra’s Algorithm solves the Single Source Shortest Path problem for a Graph. It is a Greedy algorithm and similar to Prim’s algorithm.

Read more about Dijkstra’s Algorithm for Shortest Path Problem.

Implementation

//**************************************************************************
// Implementation of Dijkstra’s Algorithm (Greedy Method to solve Shortest Path Problem)
//**************************************************************************

#include<stdio.h>

#define infinity 999

void dij(int n,int v,int cost[10][10],int dist[])
{
int i,u,count,w,flag[10],min;
for(i=1;i<=n;i++)
flag[i]=0,dist[i]=cost[v][i];
count=2;
while(count<=n)
{
min=99;
for(w=1;w<=n;w++)
if(dist[w]<min && !flag[w])
min=dist[w],u=w;
flag[u]=1;
count++;
for(w=1;w<=n;w++)
if((dist[u]+cost[u][w]<dist[w]) && !flag[w])
dist[w]=dist[u]+cost[u][w];
}
}

int main()
{
int n,v,i,j,cost[10][10],dist[10];

printf(“\n***** DIJKSTRA’S ALGORITHM FOR FINDING SHORTEST PATHS TO EACH NODE *****\n”);
printf(“\nEnter the Number of Nodes:”);
scanf(“%d”,&n);
printf(“\nEnter the Cost Matrix:\n”);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf(“%d”,&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=infinity;
}
printf(“\nEnter the Source Node:”);
scanf(“%d”,&v);
dij(n,v,cost,dist);
printf(“\n\n***** Shortest Paths to Each Node *****:\n”);
for(i=1;i<=n;i++)
if(i!=v)
printf(“Node %d -> Node %d, cost=%d\n\n”,v,i,dist[i]);
return 0;
}