Simple C Programs Using Sorting and Searching

SIMPLE C PROGRAMS USING SORTING & SEARCHING

1. To sort an array of elements

Sorting is the process of arranging elements either in ascending or in descending order. Sorting can be done on numbers, characters, strings and records. Sorting reduces time, for example, it is relatively easy to look up the required book from library from the catalogue, because the names in the catalogue have been sorted into alphabetical order.

Consider an array a[0], a[1], …………. a[n‒1]. This is said to be in ascending order, if a[i] <= a[j] for all i<=j,

If this condition is not satisfied for a value of 'i' and a value of ‘j', the number in a[i] and a[j] must be interchanged to achieve ascending order.

/* Program to sort an array of elements */

#include <stdio.h>

void main()

{

int i,n,t,j,a[10];

printf("\nEnter Upper limit....");

scanf("%d", &n);

printf("\nEnter elements....");

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

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

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

{

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

       {

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

          {

                t=a[i];

                a[i]=a[j];

                a[j]=t;

           } /* for */

        } /* for */

} /* for */

printf("\nNumbers in Ascending order\n");

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

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

} /* main */

OUTPUT

Enter Upper limit....6

Enter elements....5 1 4 6 2 3

Numbers in Ascending order 1 2 3 4 5 6

EXPLANATION: The above program refers to the sorting of elements. The program reads the upper limit value 'n' from the keyboard. The variable a[] reads the value from keyboard according to upper limit n through for loop structure. The i and j for loop checks the given number and prints the number in ascending order through another for loop i as mentioned above as output.

2. Bubble Sort

Bubble sort is the one of the easiest sorting methods. In this method, each data item is compared with its neighbor and if it is a descend sorting, then the bigger number is moved to the top of all, the smaller numbers are slowly moved to the bottom position, hence it is also called as the exchange sort.

This can be compared to the way the small bubbles moves upwards through soda water, they become bigger and bigger until they reach the surface, that is why, this method is called bubble sorting.

If you are sorting the data in Increasing/Ascending order, using Bubble sorting method, first A(1) and A(2) are compared, if A(1) is bigger than A(2) then both the numbers are interchanged. Otherwise next A(2) and A(3) are compared.

This comparing and interchanging will go on until all the elements are compared and interchanged.

/* Bubble sort using function */

#include <stdio.h>

void bubble (int n, int x[ ]);

void main()

{

int i,n,a[10]; /* Local definitions */

/* Statements */

printf("Enter upper limit \n");

scanf("%d", &n);

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

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

bubble (n,a);

printf ("After sorting");

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

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

} /* main */

void bubble (int n, int x[])

{

int i, item, temp;

       for (item = 0; item <n‒1; ++item)

       {

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

              {

                     if(x[i] < x[item])

                     {

                     temp = x[item];

                     x[item]=x[i];

                     x[i] = temp;

                     } /* if */

              } /* for */

       } /* for */

return;

} /* bubble */

OUTPUT

Enter upperlimit : 5

1  5  3   4   2

After Sorting 1 2 3 4 5

EXPLANATION: Program reads n elements to the array and sort the array of elements using bubbles sort method.

3. Insertion sort

The principal of Insertion sort is quite simple. Each successive element in the array to be sorted and inserted into its proper place with respect to the other already sorted element. We start with the second element and put it in its correct place, so that the first and second elements of the array are in order. This process continues until all the elements have been sorted.

Every repetition of insertion sort removes and element from the input data inserting into correct position in the already sorted list, until no input elements remain.

/* Program to sort an element using Insertion sort */

#include <stdio.h>

#include <conio.h>

main()

{

int i,j,k,x,a[100];   /* Local definitions */

printf("Element to be inserted");

scanf("%d", &x);

i=0;

while(x!=‒99)

{

       k=i‒1;

      while((x<a[k])&&(k> =0))

     {

            a[k+1]=a[k];

            ‒ ‒k;

       } /* while */

a[k+1]=x;

printf("Array after inserting %d\n",x);

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

          printf("%5d",a[j]);

printf("\n");

printf("\n Element to be inserted (‒99 to stop)?");

scanf("%d", &x);

printf("\n");

++i;

} /* while */

printf("The final sorted array\n");

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

      printf("%5d\n",a[j]);

} /* main */

OUTPUT

Element to be inserted 5

Array after inserting 5:

Element to be inserted(‒99 to stop)?  3

Array after inserting 3:

3    5

Element to be inserted(‒99 to stop)?  4

Array after inserting 4:

3  4  5

Element to be inserted(‒99 to stop)? 2

Array after inserting 2:

2  3  4   5

Element to be inserted(‒99 to stop)?   1

Array after inserting 1:

1  2  3   4  5

Element to be inserted(‒99 to terminate)?  ‒99

EXPLANATION: Program reads an element into an array, whenever the value entered into an array it compares the corresponding array element and the value will be moved to its appropriate position in an array.

4. Selection Sort

The idea of Selection Sort is rather simple. It basically determines the minimum or maximum   of the list and swaps it with the element at the index where it is supposed to be. The process is repeated in such a way that the nth minimum or maximum element is swapped with the element at the n‒1^th index of the list. The below is an implementation of the algorithm in C.

The principle of selection sort is different. If the array contains 'n' elements to be sorted in their correct sequence, the first element is compared with the remaining (n‒1) elements and which is the lower element, place that element in first position. Then the second element from the array is taken and compared with the remaining (n‒2) elements. If an element with a value less than that of the second element is found in the (n‒2) elements, it is swapped with the second element of the array and so on. Continue this process until all the elements in an array are sorted.

 /* Program to sort an element using selection sort */

#include <stdio.h>

void main()

{

int i,j,k,n,min, a[100]; /* Local definitions */

printf(' "Enter Number of elements in array... ");

scanf("%d", &n);

printf("Enter Elements... ",n);

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

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

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

{

        min=i;

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

        {

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

                        min=j;

        } /* for */*

        if(i!=min)

        {

                k=a[i];

                a[i]=a[min];

                a[min]=k;

        } /* if */

} /* for */

printf("\nSorted Array (Selection Sort) is...\n");

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

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

printf("\n");

} /* main */

OUTPUT:

Enter Number of elements in array... 9

Enter Elements... 56 326 85 42 156 845 66 1 55

Sorted Array (Selection Sort) is...

1 42 55 56 66 85 156 326 845

EXPLANATION: Program reads n values from input, and sorts accordingly to the election sort criteria as mentioned in introduction and prints the elements in sorted eria as mentioned in introducent an the elements in order.