Searching and Sorting


Searching:


This is the process by which one searches the group of elements for the desired element. There are different methods of searching but let us deal two popular methods of searching and they are linear search and binary search.

Linear Search:


This is one of the simplest techniques for searching an unordered table for a particular element.

In this each and every entry in the table is checked in a sequential manner until the desired element is found.


Binary Search:
In binary search the basic requirement is the elements of the array should have been sorted alphabetically or numerically in the ascending order.

In this technique the approximate middle entry of the array is located, and its key value is examined. If its value is too high, then the key value of the middle entry of the first half of the table is examined and the procedure is repeated on the first half until the required element is found or the search interval becomes empty. If the value is too low then the key of the middle entry of the second half of the array is tried and the procedure is repeated on the second half. The procedure continues until the desired key is found or the search interval becomes empty.


Program to find an element m in an array a of n elements and print it's position in the array.

/* C program to search an element using linear / binary search*/

#include <stdio.h>
#include <conio.h>
void main( )
{
int m,i, n, j, temp, flg, low, middle, high, a[100];

char ch;
clrscr( );
flg=0;
printf("Enter the size of the array \n");
scanf("%d",&n);
printf("Enter the elements of the array \n");
for (i=1; i<=n;i++)
{
scanf("%d", &a[i]);
}
do
{
printf("\nEnter the number which you want to search :");
scanf("%d", &m);
printf ("\nPress 'l' for linear search and 'b' for binary search :");
ch=getch( );
switch(ch)
{
case 'l':
for (i=1; i<=n;i++)
{
            if(a[i]==m)
              {
              flg=1;
              break;
                        }
}
if(flg== 1)
{
printf("\nThe element is found and the position is: %d",i);
printf("\n");
}
else
printf("\nElement is not found \n");
break;
case 'b':
for (i=1; i<=n-1;i++)
{
for (j=i+1;j<=n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("\nThe sorted list is \n");
for (i=1; i<=n;i++)
{
printf("%d ",a[i]);

}
low=1;
high=n;
while (low<=high)
{
middle=(low+high)/2;
if(a[middle] == m)
{
flg = 1;
break;
}
else
{
if(a[middle]<m)
{
low=middle+1;
}
else
{
high=middle-1;
}
}
}
if(flg == 1)
printf("\nThe element is found and the position is : %d", middle);
else
printf("\nThe element is not found \n");
break;
default:
printf("\nWrong selection \n");
break;
}
flushall();
printf("\nPress 'Y' to continue and any other key to discontinue : ");
ch=getch( );
}while (ch == 'Y');
getch( );
}



Output:


Note:
Sorting is discussed next. For binary search to work the array should be in the ascending order.


Sorting:
This is the operation of arranging the elements of a table into some sequential order according to ordering criteria. The sort is performed according to the key value of each of the elements. Depending on the structure of the key, elements can be sorted numerically, alphabetically or alphanumerically. For example in numerical sorting, the elements are arranged in ascending or descending order according to the numerical value of each of the elements.
There are different techniques to perform the sorting. We are discussing bubble sort in comparison with the selection sort technique.



Bubble sort differs from selection sort. In this instead of finding smallest element and then performing an interchange two elements are interchanged soon after discovering that they are out of order.
When the approach is used during the first pass the first and second element a[1] and a[2] are compared if they are out of order then the two elements are inter changed. This process is repeated for array of elements a[2] and a[3], a[3] and a[4] until a[n-1] and a[n].
This process causes elements with smaller values to bubble up the array and hence the name bubble sort. Thus after the 1st pass the largest element will be at the nth position and on each of the successive pass the element with next largest value will be placed in position n-1, n-2 ... so on. Where a is an array of n elements.


/* C program to sort the numbers using bubble sort*/

#include <stdio.h>
#include <conio.h>
void main( )
{
int i, j, temp, n, num, ar[100];
char ch;
clrscr( );
do
{
printf ("\nEnter the size of the array \n");
scanf ("%d", &n);
printf("Enter the elements of the array \n");
for (i=1; i<=n;i++)
{
scanf("%d", &ar[i]);
}
printf("   Select the option \n");
printf("1. Ascending order: \n");
printf("2. Descending order: \n");
scanf("%d",&num);
switch(num)
{
case 1:
for (i=1; i<=n-1;i++)
{
for (j=1; j<=n-i;j++)
{
if(ar[j]>ar[j+1])
{
temp=ar[j];
ar[j]=ar[j+1];
ar[j+1]=temp;
}
}
}
printf("Sorted array in ascending order is \n");
for (i=1; i<=n;i++)
{
printf("%d ",ar[i]);
}
break;

case 2:

for (i=1; i<=n-1;i++)
{
for (j=1; j<=n-i;j++)
{
if(ar[j]<ar[j+1])
{
temp=ar[j];
ar[j]=ar[j+1];
ar[j+1]=temp;
}
}
}
printf("\nSorted array in descending order is \n");
for (i=1; i<=n;i++)
{
printf("%d ",ar[i]);
}
break;
default:
printf("Wrong selection \n");
break;
}
printf("\n Press 'Y' to continue and any other key to terminate : ");
flushall( );
ch=getch( );
}while (ch == 'Y');
getch( );
} Output:



Handling of Character Strings << Previous
Next >> User Defined Functions

Our aim is to provide information to the knowledge seekers.

Support us generously

comments powered by Disqus


















Footer1