LAB #10
Sorting & Searching in 1-D Array
© Manzur Ashraf
Objective: Learn
the Bubble Sort
and Linear search 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 lab.
Bubble sort:
The
bubble sort algorithm is one of the simplest sorting algorithm.
It involves :
- 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 (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 Example#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 ;
}
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
algorithm 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 lab.
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;
}
Exercise
- Read random integer
data from the keyboard in 1-D array and then sort that data using Bubble Sort algorithm.
- Write a user defined
function for linear search in an integer 1-D array and
obtain the result(index of the target) of the
search using the return statement. Write a main function to test this.