Sorting techniques in C

/* Write a program of Binary Tree Sort. */

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

struct Node
{
int info;
struct Node *left;
struct Node *right;
struct Node *father;
};

typedef struct Node *Nodeptr;

Nodeptr getnode()
{
return( ( Nodeptr ) malloc( sizeof ( struct Node ) ) );
}

Nodeptr makenode( int x )
{
Nodeptr temp;

temp = getnode();
temp->info = x;
temp->left = temp->right = temp->father = NULL;

return( temp );
}

Nodeptr buildtree( Nodeptr root, int x )
{
if ( root == NULL )
root = makenode( x );

else if( x <= root->info )
{
root->left = buildtree( root->left, x );
root->left->father = root;
}

else
{
root->right = buildtree( root->right, x );
root->right->father = root;
}

return( root );
}

void intraverse( Nodeptr root, int *a )
{
static int i = 0;

if( root == NULL )
return;

intraverse( root->left, a );

*( a + i++ ) = root->info;

intraverse( root->right, a );
}

void binarytreesort( int *a, int n )
{
Nodeptr root;
int i;

root = NULL;

for( i = 0; i < n; i++ )
{
root = buildtree( root, *( a + i ) );
}

intraverse(root, a );
}

void main()
{

int i, n, x;
int *item;

clrscr();

printf("Enter total number of items: ");
scanf("%d",&n );

item = ( int * ) malloc( n * sizeof( int ) );
printf("Enter items: ");
for( i = 0; i < n; i++ )
{
scanf("%d", ( item + i ) );
}

binarytreesort( item, n );

printf("\nThe sorted list => ");
for( i = 0; i < n; i++ )
printf("%d ", *(item+i) );

getch();
}

...........................................................................................................................................


/* Write a program of Bubble Sort. */

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

void bubblesort( int item[], int n )
{
int flag, pass, count;

for( pass = 0; pass < n - 1; pass++ )
{
flag = 0;

for( count = 0; count < n - 1 - pass; count ++ )
if( item[count] > item[count+1] )
{
item[count] = item[count] + item[count+1];
item[count+1] = item[count] - item[count+1];
item[count] = item[count] - item[count+1];
flag = 1;
}

if( flag == 0 )
break;
}
}

void main()
{
int *item, n, i;

clrscr();
printf("Enter total number of items: ");
scanf("%d",&n);

item = ( int * ) malloc( n * sizeof( int ) );

printf("Enter the items: ");
for( i = 0; i < n; i++ )
scanf("%d", (item+i) );

bubblesort( item, n );

printf("\nThe sorted list => ");
for( i = 0; i < n; i++ )
printf("%d ", *(item+i) );

getch();
}

..................................................................................................................................................

/* Write a program of Quick Sort. */

#include <stdio.h>

#include <conio.h>

int partition( int item[], int lb, int ub )

{

int down, up, temp, x;

down = lb;

up = ub;

x = item[lb];

while( down < up )

{

while( item[down] <= x && down < ub )

down++;

while( item[up] > x )

up--;

if( down < up )

{

temp = item[down];

item[down] = item[up];

item[up] =temp;

}

}

item[lb] = item[up];

item[up] = x;

return( up );

}

void quicksort( int item[], int lb, int ub )

{

int p;

if( lb > ub )

return;

p = partition( item, lb, ub );

quicksort( item, lb, p - 1 );

quicksort( item, p + 1, ub );

}

void main()

{

int *item, n, i;

clrscr();

printf("Enter total number of items: ");

scanf("%d",&n);

item = ( int * ) malloc( n * sizeof( int ) );

printf("Enter the items: ");

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

scanf("%d", (item+i) );

quicksort( item, 0, n-1 );

printf("\nThe sorted list => ");

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

printf("%d ", *(item+i) );

getch();

}

.................................................................................................................................................

/* Write a program of Selection Sort. */

#include <stdio.h>

#include <conio.h>

void selectionsort( int item[], int n )

{

int large, index, pass, count;

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

{

large = item[0];

index = 0;

for( count = 1; count <= pass; count++ )

if( item[count] > large )

{

large = item[count];

index = count;

}

item[index] = item[pass];

item[pass] = large;

}

}

void main()

{

int *item, n, i;

clrscr();

printf("Enter total number of items: ");

scanf("%d",&n);

item = ( int * ) malloc( n * sizeof( int ) );

printf("Enter the items: ");

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

scanf("%d", (item+i) );

selectionsort( item, n );

printf("\nThe sorted list => ");

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

printf("%d ", *(item+i) );

getch();

}