ICS 103: Computer Programming in C

Handout-14

Topic: 1-D Array

(Sorting & Searching in 1-D Array)

 

Instructor: M. Waheed Aslam

 

Objective:

·        Learn the Bubble Sort and Linear search algorithms for 1-D Array.

 

What is Sorting?

·        Sorting is the re-arrangement of a collection of data according to some key-field.

·        We shall consider only Bubble Sort of sorting methods in this Lecture.

 

Bubble sort:

The bubble sort algorithm is one of the simplest sorting algorithms:

It involves following steps:

·        Compare adjacent pairs of an array.

·         If the first is larger than the second, interchange the two elements.

·         Repeat the above two steps until the array is sorted in increasing order.

 After one pass, the element with the largest key has been “bubbled” to the end of the list. The procedure continues by successively increasing the starting point in the list by 1.

 

44

 

33

 

33

 

22

 

33

 

44

 

22

 

33

 

55

 

22

 

44

 

44

 

22

 

55

 

75

 

55

 

       Original Array         pass1                 pass2               pass3             

 

Total number of pass required in bubble sort algorithm =n-1

 

Total number of comparisons required in first pass =n-1

Total number of comparisons required in second pass =n-2

Total number of comparisons required in third pass =n-3

-       - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- -- - -- - - -  -

-       - -   -   -   -  -  -       -    -          -       -        -       -     -       -

Total number of comparisons required in the (n-1)’s  pass = n-(n-1)=1

 

Where n is size of the list (or Array).

 

Algorithm for bubble sort:

 

void b_sort(int x[], int size)

{

int pass, comp, temp;

for(pass=1; pass<=size-1; pass++)

        for(comp=1; comp<=size-pass; comp++)

                if(x[comp-1]>x[comp])

                         {

                         temp=x[comp-1];

                         x[comp-1]=x[comp];

                         x[comp]=temp;

                         }

return;

}

 

Solved Problem #1 (for bubble sort):

#include<stdio.h>

#include<conio.h>

 

void b_sort(int x[], int size)

{

int pass, comp, temp;

for(pass=1; pass<=size-1; pass++)

        for(comp=1; comp<=size-pass; comp++)

                if(x[comp-1]>x[comp])

                         {

                         temp=x[comp-1];

                         x[comp-1]=x[comp];

                         x[comp]=temp;

                         }

return;

}

 

void main()

{

int i, size;

int list[10];

clrscr();

printf("Enter size of list which is to be sorted : ");

scanf("%d",&size);

printf ("Enter % d  elements of the list from key board : \n",size);

printf("-----------------------------------------------------\n");

 

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

{

         scanf("%d", &list[i]); // to read array from key board

}

 

b_sort(list,size); // Function call

 

printf("\nThe sorted list is : \n");

printf("*******************************");

 

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

{

         printf("\n %d", list[i]);

}

return ;

}

Sample Output:

 

 

 

What is searching?

·        Searching means scanning though a list of items or records to find a particular one exists.

·        It usually requires the user to specify the target item or target key.

·        If the target item is found, the record or its location is returned, otherwise, an appropriate message or flag is returned.

·        Basic searching algorithms are: Linear search (or Sequential Search) and Binary Search.

·        Linear Search can be used for sorted and unsorted data both.

·        Binary Search can be used only for sorted data. If we have sorted list of data use of binary search is more efficient in comparison to linear search.

·        We shall consider only Linear Search of Searching methods in this Lecture.

 

 

 

 

 

Linear Search:

·        This involves searching through the list sequentially until the target item is found or the list is exhausted.

·        If the target is found, its location is returned, otherwise a flag such as

        –1 is returned.

 

Algorithm  for Linear Search:

Let given a sorted or unsorted array, determine whether a given value or item or data is present in the array or not:

 

int lin_search (int list[], int size, int target)

{

int loc=0;

while(loc<size && list[loc] != target)

          loc++;

if(list[loc]==target)

        return loc;

else

        return -1;

}

 

Solved Problem #2: (For linear search)

#include<stdio.h>

#include<conio.h>

int lin_search (int list[], int size, int target)

{

int loc=0;

while(loc<size && list[loc] != target)

          loc++;

if(list[loc]==target)

        return loc;

else

        return -1;

} // end of lin_search function

 

void main( )

{

int  size, key, LOC, i;

int list[10];

clrscr(); // it is used to clear screen

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

 

scanf("%d", &size);

printf ("Enter % d  elements of the list from key board : \n", size);

printf("-------------------------------------------------------------------\n");

 

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

{

         scanf("%d", &list[i]); // to read array from key board

}

printf("-------------------------------------------------------------------\n");

printf("Please Input target or key value which you want to search in list :");

scanf("%d", &key);

 

LOC = lin_search(list, size, key); // Function call

 

if(LOC !=-1)

{

printf("\nThe location of target %d in list of array is  : %d\n ", key,LOC);

printf("\n\n\t(Dear, Remember position of first array value counted from 0)");

}

else

printf("\nDear Sorry , target %d not found in list of array",  key);

 

return;

} // end of main

 

Sample Output: