Program on deque that implements a linked list.

Program on deque that implements a linked list.

#include ""
#include ""
#include ""

struct node
{
int data ;
struct node *link ;
} ;

struct dqueue
{
struct node *front ;
struct node *rear ;
} ;

void initdqueue ( struct dqueue * ) ;
void addqatend ( struct dqueue *, int item ) ;
void addqatbeg ( struct dqueue *, int item ) ;
int delqatbeg ( struct dqueue * ) ;
int delqatend ( struct dqueue * ) ;
void display ( struct dqueue ) ;
int count ( struct dqueue ) ;
void deldqueue ( struct dqueue * ) ;

void main( )
{
struct dqueue dq ;
int i, n ;

clrscr( ) ;

initdqueue ( &dq ) ;

addqatend ( &dq, 11 ) ;
addqatbeg ( &dq, 10 ) ;
addqatend ( &dq, 12 ) ;
addqatbeg ( &dq, 9 ) ;
addqatend ( &dq, 13 ) ;
addqatbeg ( &dq, 8 ) ;
addqatend ( &dq, 14 ) ;
addqatbeg ( &dq, 7 ) ;

display ( dq ) ;

n = count ( dq ) ;
printf ( "\nTotal elements: %d", n ) ;

i = delqatbeg ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatbeg ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatbeg ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

i = delqatend ( &dq ) ;
printf ( "\nItem extracted = %d", i ) ;

display ( dq ) ;
n = count ( dq ) ;
printf ( "\nElements Left: %d", n ) ;

deldqueue ( &dq ) ;

getch( ) ;
}

/* initializes elements of structure */
void initdqueue ( struct dqueue *p )
{
p -> front = p -> rear = NULL ;
}

/* adds item at the end of dqueue */
void addqatend ( struct dqueue *p, int item )
{
struct node *temp ;

temp = ( struct node * ) malloc ( sizeof ( struct node ) );
temp -> data = item ;
temp -> link = NULL ;

if ( p -> front == NULL )
p -> front = temp ;
else
p -> rear -> link = temp ;
p -> rear = temp ;
}

/* adds item at begining of dqueue */
void addqatbeg ( struct dqueue *p, int item )
{
struct node *temp ;
int *q ;
temp = ( struct node * ) malloc ( sizeof ( struct node ) );
temp -> data = item ;
temp -> link = NULL ;

if ( p -> front == NULL )
p -> front = p -> rear = temp ;
else
{
temp -> link = p -> front ;
p -> front = temp ;
}
}

/* deletes item from begining of dqueue */
int delqatbeg ( struct dqueue *p )
{
struct node *temp = p -> front ;
int item ;
if ( temp == NULL )
{
printf ( "\nQueue is empty." ) ;
return 0 ;
}
else
{
temp = p -> front ;
item = temp -> data ;
p -> front = temp -> link ;
free ( temp ) ;

if ( temp == NULL )
p -> rear = NULL ;
return ( item ) ;
}
}

/* deletes item from end of dqueue */
int delqatend ( struct dqueue *p )
{
struct node *temp , *rleft, *q ;
int item ;
temp = p -> front ;
if ( p -> rear == NULL )
{
printf ( "\nQueue is empty." ) ;
return 0 ;
}
else
{
while ( temp != p -> rear )
{
rleft = temp ;
temp = temp -> link ;
}
q = p -> rear ;
item = q -> data ;
free ( q ) ;
p -> rear = rleft ;
p -> rear -> link = NULL ;
if ( p -> rear == NULL )
p -> front = NULL ;
return ( item ) ;
}
}

/* displays the queue */
void display ( struct dqueue dq )
{
struct node *temp = dq.front ;

printf ( "\nfront -> " ) ;
while ( temp != NULL )
{
if ( temp -> link == NULL )
{
printf ( "\t%d", temp -> data ) ;
printf ( " <- rear" ) ;
}
else
printf ( "\t%d", temp -> data ) ;
temp = temp -> link ;
}
printf ( "\n" ) ;
}

/* counts the number of items in dqueue */
int count ( struct dqueue dq )
{
int c = 0 ;
struct node *temp = dq.front ;

while ( temp != NULL )
{
temp = temp -> link ;
c++ ;
}

return c ;
}

/* deletes the queue */
void deldqueue ( struct dqueue *p )
{
struct node *temp ;

if ( p -> front == NULL )
return ;

while ( p -> front != NULL )
{
temp = p -> front ;
p -> front = p -> front -> link ;
free ( temp ) ;
}
}

Program to find the shortest path

Program to find the shortest path

#include ""
#include ""

#define INF 9999

void main( )
{
int arr[4][4] ;
int cost[4][4] = {
7, 5, 0, 0,
7, 0, 0, 2,
0, 3, 0, 0,
4, 0, 1, 0
} ;
int i, j, k, n = 4 ;

clrscr( ) ;

for ( i = 0 ; i < n ; i++ )
{
for ( j = 0; j < n ; j++ )
{
if ( cost[i][j] == 0 )
arr[i][j] = INF ;
else
arr[i][j] = cost[i][j] ;
}
}

printf ( "Adjacency matrix of cost of edges:\n" ) ;
for ( i = 0 ; i < n ; i++ )
{
for ( j = 0; j < n ; j++ )
printf ( "%d\t", arr[i][j] ) ;
printf ( "\n" ) ;
}

for ( k = 0 ; k < n ; k++ )
{
for ( i = 0 ; i < n ; i++ )
{
for ( j = 0 ; j < n ; j++ )
{
if ( arr[i][j] > arr[i][k] + arr[k][j] )
arr[i][j] = arr[i][k] + arr[k][j];
}
}
}

printf ( "\nAdjacency matrix of lowest cost between the vertices:\n" ) ;
for ( i = 0 ; i < n ; i++ )
{
for ( j = 0; j < n ; j++ )
printf ( "%d\t", arr[i][j] ) ;
printf ( "\n" ) ;
}

getch( ) ;
}

minimum cost of a spanning tree.

minimum cost of a spanning tree.

#include "stdio.h"
#include "conio.h"
#include "alloc.h"

struct lledge
{
int v1, v2 ;
float cost ;
struct lledge *next ;
} ;

int stree[5] ;
int count[5] ;
int mincost ;

struct lledge * kminstree ( struct lledge *, int ) ;
int getrval ( int ) ;
void combine ( int, int ) ;
void del ( struct lledge * ) ;

void main( )
{
struct lledge *temp, *root ;
int i ;

clrscr( ) ;

root = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ;

root -> v1 = 4 ;
root -> v2 = 3 ;
root -> cost = 1 ;
temp = root -> next = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ;

temp -> v1 = 4 ;
temp -> v2 = 2 ;
temp -> cost = 2 ;
temp -> next = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ;

temp = temp -> next ;
temp -> v1 = 3 ;
temp -> v2 = 2 ;
temp -> cost = 3 ;
temp -> next = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ;

temp = temp -> next ;
temp -> v1 = 4 ;
temp -> v2 = 1 ;
temp -> cost = 4 ;
temp -> next = NULL ;

root = kminstree ( root, 5 ) ;

for ( i = 1 ; i <= 4 ; i++ )
printf ( "\nstree[%d] -> %d", i, stree[i] ) ;
printf ( "\nThe minimum cost of spanning tree is %d", mincost ) ;
del ( root ) ;

getch( ) ;
}
struct lledge * kminstree ( struct lledge *root, int n )
{
struct lledge *temp = NULL ;
struct lledge *p, *q ;
int noofedges = 0 ;
int i, p1, p2 ;

for ( i = 0 ; i < n ; i++ )
stree[i] = i ;
for ( i = 0 ; i < n ; i++ )
count[i] = 0 ;

while ( ( noofedges < ( n - 1 ) ) && ( root != NULL ) )
{
p = root ;

root = root -> next ;

p1 = getrval ( p -> v1 ) ;
p2 = getrval ( p -> v2 ) ;

if ( p1 != p2 )
{
combine ( p -> v1, p -> v2 ) ;
noofedges++ ;
mincost += p -> cost ;
if ( temp == NULL )
{
temp = p ;
q = temp ;
}
else
{
q -> next = p ;
q = q -> next ;
}
q -> next = NULL ;
}
}
return temp ;
}

int getrval ( int i )
{
int j, k, temp ;
k = i ;
while ( stree[k] != k )
k = stree[k] ;
j = i ;
while ( j != k )
{
temp = stree[j] ;
stree[j] = k ;
j = temp ;
}
return k ;
}

void combine ( int i, int j )
{
if ( count[i] < count[j] )
stree[i] = j ;
else
{
stree[j] = i ;
if ( count[i] == count[j] )
count[j]++ ;
}
}

void del ( struct lledge *root )
{
struct lledge *temp ;

while ( root != NULL )
{
temp = root -> next ;
free ( root ) ;
root = temp ;
}
}

Breadth first search algorithm.

Breadth first search algorithm.

#include "stdio.h"
#include "conio.h"
#include "alloc.h"

#define TRUE 1
#define FALSE 0
#define MAX 8

struct node
{
int data ;
struct node *next ;
} ;

int visited[MAX] ;
int q[8] ;
int front, rear ;

void bfs ( int, struct node ** ) ;
struct node * getnode_write ( int ) ;
void addqueue ( int ) ;
int deletequeue( ) ;
int isempty( ) ;
void del ( struct node * ) ;

void main( )
{
struct node *arr[MAX] ;
struct node *v1, *v2, *v3, *v4 ;
int i ;

clrscr( ) ;

v1 = getnode_write ( 2 ) ;
arr[0] = v1 ;
v1 -> next = v2 = getnode_write ( 3 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 1 ) ;
arr[1] = v1 ;
v1 -> next = v2 = getnode_write ( 4 ) ;
v2 -> next = v3 = getnode_write ( 5 ) ;
v3 -> next = NULL ;

v1 = getnode_write ( 1 ) ;
arr[2] = v1 ;
v1 -> next = v2 = getnode_write ( 6 ) ;
v2 -> next = v3 = getnode_write ( 7 ) ;
v3 -> next = NULL ;

v1 = getnode_write ( 2 ) ;
arr[3] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 2 ) ;
arr[4] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 3 ) ;
arr[5] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 3 ) ;
arr[6] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 4 ) ;
arr[7] = v1 ;
v1 -> next = v2 = getnode_write ( 5 ) ;
v2 -> next = v3 = getnode_write ( 6 ) ;
v3 -> next = v4 = getnode_write ( 7 ) ;
v4 -> next = NULL ;

front = rear = -1 ;
bfs ( 1, arr ) ;

for ( i = 0 ; i < MAX ; i++ )
del ( arr[i] ) ;

getch( ) ;
}

void bfs ( int v, struct node **p )
{
struct node *u ;

visited[v - 1] = TRUE ;
printf ( "%d\t", v ) ;
addqueue ( v ) ;

while ( isempty( ) == FALSE )
{
v = deletequeue( ) ;
u = * ( p + v - 1 ) ;

while ( u != NULL )
{
if ( visited [ u -> data - 1 ] == FALSE )
{
addqueue ( u -> data ) ;
visited [ u -> data - 1 ] = TRUE ;
printf ( "%d\t", u -> data ) ;
}
u = u -> next ;
}
}
}

struct node * getnode_write ( int val )
{
struct node *newnode ;
newnode = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
newnode -> data = val ;
return newnode ;
}

void addqueue ( int vertex )
{
if ( rear == MAX - 1 )
{
printf ( "\nQueue Overflow." ) ;
exit( ) ;
}

rear++ ;
q[rear] = vertex ;

if ( front == -1 )
front = 0 ;
}

int deletequeue( )
{
int data ;

if ( front == -1 )
{
printf ( "\nQueue Underflow." ) ;
exit( ) ;
}

data = q[front] ;

if ( front == rear )
front = rear = -1 ;
else
front++ ;

return data ;
}

int isempty( )
{
if ( front == -1 )
return TRUE ;
return FALSE ;
}

void del ( struct node *n )
{
struct node *temp ;

while ( n != NULL )
{
temp = n -> next ;
free ( n ) ;
n = temp ;
}
}

depth first search algorithm.

depth first search algorithm.

#include "stdio.h"
#include "conio.h"
#include "alloc.h"

#define TRUE 1
#define FALSE 0
#define MAX 8

struct node
{
int data ;
struct node *next ;
} ;

int visited[MAX] ;

void dfs ( int, struct node ** ) ;
struct node * getnode_write ( int ) ;
void del ( struct node * ) ;

void main( )
{
struct node *arr[MAX] ;
struct node *v1, *v2, *v3, *v4 ;
int i ;

clrscr( ) ;

v1 = getnode_write ( 2 ) ;
arr[0] = v1 ;
v1 -> next = v2 = getnode_write ( 3 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 1 ) ;
arr[1] = v1 ;
v1 -> next = v2 = getnode_write ( 4 ) ;
v2 -> next = v3 = getnode_write ( 5 ) ;
v3 -> next = NULL ;

v1 = getnode_write ( 1 ) ;
arr[2] = v1 ;
v1 -> next = v2 = getnode_write ( 6 ) ;
v2 -> next = v3 = getnode_write ( 7 ) ;
v3 -> next = NULL ;

v1 = getnode_write ( 2 ) ;
arr[3] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 2 ) ;
arr[4] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 3 ) ;
arr[5] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 3 ) ;
arr[6] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;

v1 = getnode_write ( 4 ) ;
arr[7] = v1 ;
v1 -> next = v2 = getnode_write ( 5 ) ;
v2 -> next = v3 = getnode_write ( 6 ) ;
v3 -> next = v4 = getnode_write ( 7 ) ;
v4 -> next = NULL ;

dfs ( 1, arr ) ;

for ( i = 0 ; i < q =" *"> data - 1] == FALSE )
dfs ( q -> data, p ) ;
else
q = q -> next ;
}
}

struct node * getnode_write ( int val )
{
struct node *newnode ;
newnode = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
newnode -> data = val ;
return newnode ;
}

void del ( struct node *n )
{
struct node *temp ;

while ( n != NULL )
{
temp = n -> next ;
free ( n ) ;
n = temp ;
}
}

Program that creates random numbers in a given file

Program that creates random numbers in a given file.

#include "stdio.h"
#include "conio.h"
#include "stdlib.h"

void main( )
{
FILE *fp ;
char str [ 67 ] ;
int i, noofr, j ;

clrscr( ) ;

printf ( "Enter file name: " ) ;
scanf ( "%s", str ) ;

printf ( "Enter number of records: " ) ;
scanf ( "%d", &noofr ) ;

fp = fopen ( str, "wb" ) ;
if ( fp == NULL )
{
printf ( "Unable to create file." ) ;
getch( ) ;
exit ( 0 ) ;
}

randomize( ) ;

for ( i = 0 ; i < noofr ; i++ )
{
j = random ( 1000 ) ;
fwrite ( &j, sizeof ( int ), 1, fp ) ;
printf ( "%d\t", j ) ;
}

fclose ( fp ) ;

printf ( "\nFile is created. \nPress any key to continue." ) ;

getch( ) ;
}

External Sorting.

External Sorting.

#include "stdio.h"
#include "conio.h"
#include "stdlib.h"

void shownums ( char * ) ;
void split ( char * ) ;
void sort ( char * ) ;

void main( )
{
char str[67] ;

clrscr( ) ;

printf ( "Enter file name: " ) ;
scanf ( "%s", str ) ;

printf ( "Numbers before sorting:\n" ) ;
shownums ( str ) ;

split ( str ) ;
sort ( str ) ;

printf ( "\nNumbers after sorting:\n" ) ;
shownums ( str ) ;

getch( ) ;
}

/* Displays the contents of file */
void shownums ( char *p )
{
FILE *fp ;
int i ;

fp = fopen ( p, "rb" ) ;
if ( fp == NULL )
{
printf ( "Unable to open file." ) ;
getch( ) ;
exit ( 0 ) ;
}

while ( fread ( &i, sizeof ( int ), 1, fp ) != 0 )
printf ( "%d \t", i ) ;

fclose ( fp ) ;
}

/* Splits the original file into two files */
void split ( char *p )
{
FILE *fs, *ft ;
long int l, count ;
int i ;

fs = fopen ( p, "rb" ) ;
if ( fs == NULL )
{
printf ( "Unable to open file." ) ;
getch( ) ;
exit ( 0 ) ;
}

ft = fopen ( "temp1.dat", "wb" ) ;
if ( ft == NULL )
{
fclose ( fs ) ;
printf ( "Unable to open file." ) ;
getch( ) ;
exit ( 1 ) ;
}

fseek ( fs, 0L, SEEK_END ) ;
l = ftell ( fs ) ;
fseek ( fs, 0L, SEEK_SET ) ;

l = l / ( sizeof ( int ) * 2 ) ;

for ( count = 1 ; count <= l ; count++ )
{
fread ( &i, sizeof ( int ), 1, fs ) ;
fwrite ( &i, sizeof ( int ), 1, ft ) ;
}

fclose ( ft ) ;

ft = fopen ( "temp2.dat", "wb" ) ;
if ( ft == NULL )
{
fclose ( fs ) ;
printf ( "Unable to open file." ) ;
getch( ) ;
exit ( 2 ) ;
}

while ( fread ( &i, sizeof ( int ), 1, fs ) != 0 )
fwrite ( &i, sizeof ( int ), 1, ft ) ;

fcloseall ( ) ;
}

/* Sorts the file */
void sort ( char *p )
{
FILE *fp[4] ;
char *fnames[ ] =
{
"temp1.dat",
"temp2.dat",
"final1.dat",
"final2.dat"
} ;

int i, j = 1, i1, i2, flag1, flag2, p1, p2 ;
long int l ;

while ( 1 )
{
for ( i = 0 ; i <= 1 ; i++ )
{
fp[i] = fopen ( fnames[i], "rb+" ) ;
if ( fp[i] == NULL )
{
fcloseall( ) ;
printf ( "Unable to open file." ) ;
getch( ) ;
exit ( i ) ;
}

fseek ( fp[i], 0L, SEEK_END ) ;
l = ftell ( fp[i] ) ;
if ( l == 0 )
goto out ;
fseek ( fp[i], 0L, SEEK_SET ) ;
}

for ( i = 2 ; i <= 3 ; i++ )
{
fp[i] = fopen ( fnames[i], "wb" ) ;
if ( fp[i] == NULL )
{
fcloseall( ) ;
printf ( "Unable to open file." ) ;
getch( ) ;
exit ( i ) ;
}
}

i = 2 ;
i1 = i2 = 0 ;
flag1 = flag2 = 1 ;

while ( 1 )
{
if ( flag1 )
{
if ( fread ( &p1, sizeof ( int ), 1, fp[0] ) == 0 )
{
/* If first file ends then the whole content of second
file is written in the respective target file */
while ( fread ( &p2, sizeof ( int ), 1, fp[1] ) != 0 )
fwrite ( &p2, sizeof ( int ), 1, fp[i] ) ;
break ;
}
}

if ( flag2 )
{
if ( fread ( &p2, sizeof ( int ), 1, fp[1] ) == 0 )
{
/* If second file ends then the whole content of first
file is written in the respective target file */
fwrite ( &p1, sizeof ( int ), 1, fp[i] ) ;
while ( fread ( &p1, sizeof ( int ), 1, fp[0] ) != 0 )
fwrite ( &p1, sizeof ( int ), 1, fp[i] ) ;
break ;
}
}

if ( p1 < p2 )
{
flag2 = 0 ;
flag1 = 1 ;
fwrite ( &p1, sizeof ( int ), 1, fp[i] ) ;
i1++ ;
}
else
{
flag1 = 0 ;
flag2 = 1 ;
fwrite ( &p2, sizeof ( int ), 1, fp[i] ) ;
i2++ ;
}

if ( i1 == j )
{
flag1 = flag2 = 1 ;
fwrite ( &p2, sizeof ( int ), 1, fp[i] ) ;
for ( i2++ ; i2 < j ; i2++ )
{
if ( fread ( &p2, sizeof ( int ), 1, fp[1] ) != 0 )
fwrite ( &p2, sizeof ( int ), 1, fp[i] ) ;
}
i1 = i2 = 0 ;
i == 2 ? ( i = 3 ) : ( i = 2 ) ;
}

if ( i2 == j )
{
flag1 = flag2 = 1 ;
fwrite ( &p1, sizeof ( int ), 1, fp[i] ) ;
for ( i1++ ; i1 < j ; i1++ )
{
if ( fread ( &p1, sizeof ( int ), 1, fp[0] ) != 0 )
fwrite ( &p1, sizeof ( int ), 1, fp[i] ) ;
}
i1 = i2 = 0 ;
i == 2 ? ( i = 3 ) : ( i = 2 ) ;
}
}

fcloseall( ) ;
remove ( fnames[0] ) ;
remove ( fnames[1] ) ;
rename ( fnames[2], fnames[0] ) ;
rename ( fnames[3], fnames[1] ) ;
j *= 2 ;
}

out :

fcloseall( ) ;
remove ( p ) ;
rename ( fnames[0], p ) ;
remove ( fnames[1] ) ;
}

Merge Sort.

Merge Sort.

#include
#include

void main( )
{
int a[5] = { 11, 2, 9, 13, 57 } ;
int b[5] = { 25, 17, 1, 90, 3 } ;
int c[10] ;
int i, j, k, temp ;

clrscr( ) ;

printf ( "Merge sort.\n" ) ;

printf ( "\nFirst array:\n" ) ;
for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", a[i] ) ;

printf ( "\n\nSecond array:\n" ) ;
for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", b[i] ) ;

for ( i = 0 ; i <= 3 ; i++ )
{
for ( j = i + 1 ; j <= 4 ; j++ )
{
if ( a[i] > a[j] )
{
temp = a[i] ;
a[i] = a[j] ;
a[j] = temp ;
}
if ( b[i] > b[j] )
{
temp = b[i] ;
b[i] = b[j] ;
b[j] = temp ;
}
}
}

for ( i = j = k = 0 ; i <= 9 ; )
{
if ( a[j] <= b[k] )
c[i++] = a[j++] ;
else
c[i++] = b[k++] ;

if ( j == 5 || k == 5 )
break ;
}

for ( ; j <= 4 ; )
c[i++] = a[j++] ;

for ( ; k <= 4 ; )
c[i++] = b[k++] ;

printf ( "\n\nArray after sorting:\n") ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", c[i] ) ;

getch( ) ;
}

Heap Sort.

Heap Sort.

#include "stdio.h"
#include "conio.h"

void makeheap ( int [ ], int ) ;
void heapsort ( int [ ], int ) ;

void main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;

clrscr( ) ;
printf ( "Heap Sort.\n" ) ;

makeheap ( arr, 10 ) ;

printf ( "\nBefore Sorting:\n" ) ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;

heapsort ( arr, 10 ) ;

printf ( "\nAfter Sorting:\n" ) ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;

getch( );
}

void makeheap ( int x[ ], int n )
{
int i, val, s, f ;
for ( i = 1 ; i < n ; i++ )
{
val = x[i] ;
s = i ;
f = ( s - 1 ) / 2 ;
while ( s > 0 && x[f] < val )
{
x[s] = x[f] ;
s = f ;
f = ( s - 1 ) / 2 ;
}
x[s] = val ;
}
}

void heapsort ( int x[ ], int n )
{
int i, s, f, ivalue ;
for ( i = n - 1 ; i > 0 ; i-- )
{
ivalue = x[i] ;
x[i] = x[0] ;
f = 0 ;

if ( i == 1 )
s = -1 ;
else
s = 1 ;

if ( i > 2 && x[2] > x[1] )
s = 2 ;

while ( s >= 0 && ivalue < x[s] )
{
x[f] = x[s] ;
f = s ;
s = 2 * f + 1 ;

if ( s + 1 <= i - 1 && x[s] < x[s + 1] )
s++ ;
if ( s > i - 1 )
s = -1 ;
}
x[f] = ivalue ;
}
}

Binary Tree Sorting.

Binary Tree Sorting.

#include "stdio.h"
#include "conio.h"
#include "alloc.h"

struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
} ;

void insert ( struct btreenode **, int ) ;
void inorder ( struct btreenode * ) ;

void main( )
{
struct btreenode *bt ;
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;

bt = NULL ;

clrscr( ) ;

printf ( "Binary tree sort.\n" ) ;

printf ( "\nArray:\n" ) ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;

for ( i = 0 ; i <= 9 ; i++ )
insert ( &bt, arr[i] ) ;

printf ( "\nIn-order traversal of binary tree:\n" ) ;
inorder ( bt ) ;

getch( ) ;
}

void insert ( struct btreenode **sr, int num )
{
if ( *sr == NULL )
{
*sr = malloc ( sizeof ( struct btreenode ) ) ;

( *sr ) -> leftchild = NULL ;
( *sr ) -> data = num ;
( *sr ) -> rightchild = NULL ;
}
else
{
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
}

void inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;
printf ( "%d\t", sr -> data ) ;
inorder ( sr -> rightchild ) ;
}
}

Insertion sort.

Insertion sort.

#include "stdio.h"
#include "conio.h"

void main( )
{
int arr[5] = { 25, 17, 31, 13, 2 } ;
int i, j, k, temp ;

clrscr( ) ;

printf ( "Insertion sort.\n" ) ;
printf ( "\nArray before sorting:\n") ;

for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;

for ( i = 1 ; i <= 4 ; i++ )
{
for ( j = 0 ; j < i ; j++ )
{
if ( arr[j] > arr[i] )
{
temp = arr[j] ;
arr[j] = arr[i] ;

for ( k = i ; k > j ; k-- )
arr[k] = arr[k - 1] ;

arr[k + 1] = temp ;
}
}
}

printf ( "\n\nArray after sorting:\n") ;

for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;

getch( ) ;
}

Quick sort

Quick sort

#include "conio.h"
#include "stdio.h"

int split ( int*, int, int ) ;

void main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;

void quicksort ( int *, int, int ) ;

clrscr( ) ;

printf ( "Quick sort.\n" ) ;
printf ( "\nArray before sorting:\n") ;

for ( i = 0 ; i <= 9 ; i++ ) printf ( "%d\t", arr[i] ) ; quicksort ( arr, 0, 9 ) ; printf ( "\nArray after sorting:\n") ; for ( i = 0 ; i <= 9 ; i++ ) printf ( "%d\t", arr[i] ) ; getch( ) ; } void quicksort ( int a[ ], int lower, int upper ) { int i ; if ( upper > lower )
{
i = split ( a, lower, upper ) ;
quicksort ( a, lower, i - 1 ) ;
quicksort ( a, i + 1, upper ) ;
}
}

int split ( int a[ ], int lower, int upper )
{
int i, p, q, t ;

p = lower + 1 ;
q = upper ;
i = a[lower] ;

while ( q >= p )
{
while ( a[p] <> i )
q-- ;

if ( q > p )
{
t = a[p] ;
a[p] = a[q] ;
a[q] = t ;
}
}

t = a[lower] ;
a[lower] = a[q] ;
a[q] = t ;

return q ;
}

Selection sort.

Selection sort.

#include ""
#include ""

void main( )
{
int arr[5] = { 25, 17, 31, 13, 2 } ;
int i, j, temp ;

clrscr( ) ;

printf ( "Selection sort.\n" ) ;
printf ( "\nArray before sorting:\n") ;

for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;

for ( i = 0 ; i <= 3 ; i++ )
{
for ( j = i + 1 ; j <= 4 ; j++ )
{
if ( arr[i] > arr[j] )
{
temp = arr[i] ;
arr[i] = arr[j] ;
arr[j] = temp ;
}
}
}

printf ( "\n\nArray after sorting:\n") ;

for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;

getch( ) ;
}

Bubble sort.

Bubble sort.

#include
#include

void main( )
{
int arr[5] = { 25, 17, 31, 13, 2 } ;
int i, j, temp ;

clrscr( ) ;

printf ( "Bubble sort.\n" ) ;
printf ( "\nArray before sorting:\n") ;

for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;

for ( i = 0 ; i <= 3 ; i++ )
{
for ( j = 0 ; j <= 3 - i ; j++ )
{
if ( arr[j] > arr[j + 1] )
{
temp = arr[j] ;
arr[j] = arr[j + 1] ;
arr[j + 1] = temp ;
}
}
}

printf ( "\n\nArray after sorting:\n") ;

for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;

getch( ) ;
}

Binary search in a sorted array.

Binary search in a sorted array.
#include ""
#include ""

void main( )
{
int arr[10] = { 1, 2, 3, 9, 11, 13, 17, 25, 57, 90 } ;
int mid, lower = 0 , upper = 9, num, flag = 1 ;

clrscr( ) ;

printf ( "Enter number to search: " ) ;
scanf ( "%d", &num ) ;

for ( mid = ( lower + upper ) / 2 ; lower <= upper ;
mid = ( lower + upper ) / 2 )
{
if ( arr[mid] == num )
{
printf ( "The number is at position %d in the array.", mid ) ;
flag = 0 ;
break ;
}
if ( arr[mid] > num )
upper = mid - 1 ;
else
lower = mid + 1 ;
}

if ( flag )
printf ( "Element is not present in the array." ) ;

getch( ) ;
}

Linear search in a sorted array.

Linear search in a sorted array.

#include ""
#include ""

void main( )
{
int arr[10] = { 1, 2, 3, 9, 11, 13, 17, 25, 57, 90 } ;
int i, num ;

clrscr( ) ;

printf ( "Enter number to search: " ) ;
scanf ( "%d", &num ) ;

for ( i = 0 ; i <= 9 ; i++ )
{
if ( arr[9] < num || arr[i] >= num )
{
if ( arr[i] == num )
printf ( "The number is at position %d in the array.", i ) ;
else
printf ( "Number is not present in the array." ) ;
break ;
}
}

getch( ) ;
}

Linear search in an unsorted array.

Linear search in an unsorted array.

#include <"stdio.h">
#include ""

void main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i, num ;

clrscr( ) ;

printf ( "Enter number to search: " ) ;
scanf ( "%d", &num ) ;

for ( i = 0 ; i <= 9 ; i++ )
{
if ( arr[i] == num )
break ;
}

if ( i == 10 )
printf ( "Number is not present in the array." ) ;
else
printf ( "The number is at position %d in the array.", i ) ;

getch( ) ;
}