Programs on various Searching & Sorting Techniques

SORTING TECHNIQUES

1) Write a C program to implement Selection sort algorithm?

#include<stdio.h>

#include<conio.h>

int readf(int []);

int selectionsort(int [],int );

display(int [],int );

main()

int a[50],n;

clrscr();

n=readf(a);

selectionsort(a,n);

display(a,n);

getch();

int readf(int a[])

int i,n;

printf("size of an array:");

scanf("%d",&n);

printf("Enter the elements:");

1
Programs on various Searching & Sorting Techniques

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

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

return n;

int selectionsort(int a[],int n)

int pass,min_index,i,temp;

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

min_index=pass;

for(i=pass+1;i<n;i++)

if(a[i]<a[min_index])

min_index=i;

if(min_index!=pass)

temp=a[pass];

a[pass]=a[min_index];

a[min_index]=temp;

display(int a[], int n)

2
Programs on various Searching & Sorting Techniques

int i;

printf("Elements after sorting are:\n");

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

printf("%d\t",a[i]);

3
Programs on various Searching & Sorting Techniques

2) Write a C program to implement Bubble sort algorithm?

#include<stdio.h>

#include<conio.h>

int readf(int []);

int bubblesort(int [],int );

display(int [],int );

main()

int a[50],n;

clrscr();

n=readf(a);

bubblesort(a,n);

display(a,n);

getch();

int readf(int a[])

int i,n;

printf("Enter size of an array:");

scanf("%d",&n);

printf("Enter the elements:");

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

4
Programs on various Searching & Sorting Techniques

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

return n;

int bubblesort(int a[],int n)

int last,exchg,pass,temp,i;

last=n-1;

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

exchg=0;

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

if(a[i]>a[i+1])

temp=a[i];

a[i]=a[i+1];

a[i+1]=temp;

exchg+=1;

if(exchg==0)

return;

else

5
Programs on various Searching & Sorting Techniques

last=last-1;

display(int a[],int n)

int i;

printf("Elements after sorting are:\n");

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

printf("%d\t",a[i]);

6
Programs on various Searching & Sorting Techniques

3) Write a C program to implement Insertion sort algorithm?

#include<stdio.h>

#include<conio.h>

int readf(int []);

int insertionsort(int [],int );

display(int [],int );

main()

int a[50],n;

clrscr();

n=readf(a);

insertionsort(a,n);

display(a,n);

getch();

int readf(int a[])

int i,n;

printf("Enter the size of an array:");

scanf("%d",&n);

printf("Enter the array elements:");

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

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

7
Programs on various Searching & Sorting Techniques

return n;

int insertionsort(int a[],int n)

int i,j,index;

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

index=a[i], j=i;

while((j>0)&&(a[j-1]>index))

a[j]=a[j-1];

j-=1;

a[j]=index;

display(int a[],int n)

int i;

printf("Elements after the sorting are:");

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

printf("%d\t",a[i]);

8
Programs on various Searching & Sorting Techniques

4) Write a C program to implement Simple Merge sort algorithm?

#include<stdio.h>

#include<conio.h>

int readf1(int []);

int readf2(int []);

int mergesort(int [],int ,int [],int ,int []);

void display(int [],int );

main()

int a[50],b[50],c[50],n,k,m;

clrscr();

n=readf1(a);

m=readf2(b);

k=m+n;

mergesort(a,n,b,m,c);

display(c,k);

getch();

int readf1(int a[])

int i,n;

printf("Enter the size of first array:");

scanf("%d",&n);

9
Programs on various Searching & Sorting Techniques

printf("Enter elements of first array:");

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

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

return n;

int readf2(int b[])

int i,m;

printf("Enter the size of second array:");

scanf("%d",&m);

printf("Enter elements of second array:");

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

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

return m;

int mergesort(int a[],int n,int b[],int m,int c[])

int i,j,k;

i=0;j=0;k=0;

while((i<n)&&(j<m))

if(a[i]<=b[j])

10
Programs on various Searching & Sorting Techniques

c[k]=a[i];

i++;

k++;

else

c[k]=b[j];

j++;

k++;

while(j<m)

c[k]=b[j];

j++;

k++;

while(i<n)

c[k]=a[i];

i++;

11
Programs on various Searching & Sorting Techniques

k++;

void display(int c[],int k)

int i;

printf("Elements after sorting are:");

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

printf("%d\t",c[i]);

12
Programs on various Searching & Sorting Techniques

5) Write a C program to implement Quick sort algorithm?

#include<stdio.h>

#include<conio.h>

int readf(int []);

int quicksort(int [],int ,int );

display(int [],int );

main()

int a[50],n,lb,ub;

clrscr();

n=readf(a);

lb=0;

ub=n-1;

quicksort(a,lb,ub);

display(a,n);

getch();

int readf(int a[])

int i,n;

printf("Enter size of an array:");

scanf("%d",&n);

printf("Enter the elements:");

13
Programs on various Searching & Sorting Techniques

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

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

return n;

int quicksort(int a[],int lb,int ub)

int i,j,pivot,temp,temp1;

if(lb<ub)

i=lb;

j=ub;

pivot=a[lb];

while(1)

while(a[i]<=pivot)

i++;

while(a[j]>pivot)

j--;

if(i<j)

temp=a[i];

a[i]=a[j];

a[j]=temp;

14
Programs on various Searching & Sorting Techniques

else

break;

if(i>=j)

temp1=a[j];

a[j]=a[lb];

a[lb]=temp1;

quicksort(a,lb,j-1);

quicksort(a,j+1,ub);

display(int a[],int n)

int i;

printf("Elements after sorting are:");

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

printf("%d\t",a[i]);

15
Programs on various Searching & Sorting Techniques

SEARCHING TECHNIQUES

1) Write a program to implement Linear search (Sequential searching)

algorithm? [Both recursive & Non-recursive procedures]

#include<stdio.h>

#include<conio.h>

int linserch(int a[],int n,int key);

main()

int i,pos,n,key,a[100];

clrscr();

printf("no.of elements in the list:\n");

scanf("%d",&n);

printf("enter the element ot be searched:\n");

scanf("%d",&key);

printf("\nenter the elements into the list:\n");

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

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

pos=-1;

pos=linserch(a,n,key);

if(pos!=-1)

16
Programs on various Searching & Sorting Techniques

printf("\nthe key %d is found at location %d:\n",key,pos);

else

printf("\nthe key is not found in the list:");

getch();

/*function which performs linear searching(sequential searching*/

int linserch(int a[],int n,int key)

int i;

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

if(key==a[i])

return i;

return -1;

17
Programs on various Searching & Sorting Techniques

2) Write a program to implement Binary search (Sequential searching)

algorithm? [Both recursive & Non-recursive procedures]

#include<stdio.h>

#include<conio.h>

void bubblesort(int a[],int n);

int b_search(int a[],int n,int key,int low,int high);

int a[500],n,key,low,high;

int main()

int i,pos=-1;

clrscr();

printf("Enter the size:");

scanf("%d",&n);

printf("Enter the elements of an array'A':\n");

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

printf("\nEnter element %d:",i+1);

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

printf("Enter the element to be searched:\n");

scanf("%d",&key);

bubblesort(a,n);

18
Programs on various Searching & Sorting Techniques

low=0;

high=n-1;

pos=b_search(a,n,key,low,high);

if(pos!=-1)

printf("the key element %d is at position %d",key,pos);

else

printf("the key element is not found in the list");

getch();

void bubblesort(int a[],int n)

int i,j,temp;

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

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

if(a[i]>a[j])

temp=a[i];

a[i]=a[j];

a[j]=temp;

19
Programs on various Searching & Sorting Techniques

printf("The elements in sotred order are:\n");

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

printf("%d\t",a[i]);

printf("\n");

int b_search(int a[],int n,int key,int low,int high)

int mid,pos=-1;

if(low<=high)

mid=(int)((low+high)/2);

if(key==a[mid])

return mid;

if(key<a[mid])

pos=b_search(a,n,key,low,mid-1);

else if(key>a[mid])

pos=b_search(a,n,key,mid+1,high);

return pos;

20
Programs on various Searching & Sorting Techniques

21