Searching and sorting
4.1 SEARCHIN.
L
L
et us assume that we have a sequential file and we wish to retrieve an element matching with key
‘k’, then, we have to search the entire file from the beginning till the end to check whether the
element matching k is present in the file or not.
There are a number of complex searching algorithms to serve the purpose of searching. The linear
search and binary search methods are relatively straight forward methods of searching.
4.1.1 Sequential searc.
In this method, we start to search from the beginning of the list and examine each element till the end
of the list. If the desired element is found we stop the search and return the index of that element. If the
item is not found and the list is exhausted the search returns a zero value.
In the worst case the item is not found or the search item is the last (nth) element. For both situations
we must examine all n elements of the array.
The algorithm for sequential search is as follows,
Algorithm : sequential search
Input : A, vector of n elements
K, search element
Output : j –index of k
BSIT 41 Algorithms
Chapter 4 - Searching and Sorting
Method : i=1
While(i<=n)
{
if(A[i]=k)
{
write(“search successful”)
write(k is at location i)
exit();
}
else
i++
if end
while end
write (search unsuccessful);
algorithm ends.
4.1.2 Binary Searc.
Binary search method is also relatively simple method. For this method it is necessary to have the
vector in an alphabetical or numerically increasing order. A search for a particular item with X resembles
the search for a word in the dictionary. The approximate mid entry is located and its key value is examined.
If the mid value is greater than X, then the list is chopped off at the (mid-1)th location. Now the list gets
reduced to half the original list. The middle entry of the left-reduced list is examined in a similar manner.
This procedure is repeated until the item is found or the list has no more elements. On the other hand, if
the mid value is lesser than X, then the list is chopped off at (mid+1)th location. The middle entry of the
right-reduced list is examined and the procedure is continued until desired key is found or the search
interval is exhausted.
The algorithm for binary search is as follows,
Algorithm : binary search
Input : A, vector of n elements
K, search element
BSIT 41 Algorithms
Output : low –index of k
Method : low=1,high=n
While(low<=high-1)
{
mid=(low+high)/2
if(k<a[mid])
high=mid
else
low=mid
if end
}
while end
if(k=A[low])
{
write(“search successful”)
write(k is at location low)
exit();
}
else
write (search unsuccessful);
if end;
Algorithm ends.
4.2 SORTIN.
One of the major applications in computer science is the sorting of information in a table. Sorting
algorithms arrange items in a set according to a predefined ordering relation. The most common types of
data are string information and numerical information. The ordering relation for numeric data simply
Chapter 4 - Searching and Sorting
involves arranging items in sequence from smallest to largest and from largest to smallest, which is called
ascending and descending order respectively.
The items in a set arranged in non-decreasing order are {7,11,13,16,16,19,23}. The items in a set
arranged in descending order is of the form {23,19,16,16,13,11,7}
Similarly for string information, {a, abacus, above, be, become, beyond}is in ascending order and {
beyond, become, be, above, abacus, a}is in descending order.
There are numerous methods available for sorting information. But, not even one of them is best for all
applications. Performance of the methods depends on parameters like, size of the data set, degree of
relative order already present in the data etc.
4.2.1 Insertion Sortin.
The first class of sorting algorithm that we consider comprises algorithms that sort by insertion. An
algorithm that sorts by insertion takes the initial, unsorted sequence,
S = {s1:ss ... n }, and computes a series of sorted sequences S'0: S' :...: S , as follows:
2: 3 s 1' n
1. The first sequence in the series, S' is the empty sequence. i.e., = {} .
0 S'0
2. Given a sequence S'0 in the series, for 0 £ i £ n , the next sequence in the series,
S' i+1 , is obtained by inserting the (i + 1)th element of the unsorted sequence
' i+1 into the correct position in S'.
Si
Each sequence , i £ n , contains the first i elements of the unsorted sequence S.
S' i 0 £
Therefore, the final sequence in the series, S' n , is the sorted sequence we seek. i.e.,
S ' = S' n .
Fig. 4.1 illustrates the insertion sorting algorithm. The figure shows the progression of the
insertion sorting algorithm as it sorts an array of ten integers. The array is sorted in place.
I.e., the initial unsorted sequence, S, and the series of sorted sequences, S'0: ' :...: S' n , ,
S 1
occupy the same array.
In the ith step, the element at position i in the array is inserted into the sorted sequence
S' i which occupies array positions 0 to (i-1). After this is done, array positions 0 to i
contain the i+1 elements of S' i+1 . Array positions (i+1) to (n-1) contain the remaining n-i1
elements of the unsorted sequence S.
BSIT 41 Algorithms
As shown in Fig. 4.1, the first step (i=0) is trivial—inserting an element into the empty list involves no
work. Altogether, n-1 non-trivial insertions are required to sort a list of n elements.
Fig. 4.1 Insertion sort
Algorithm : Insertion Sort
Input : n, Size of the input domain
a[1..n], array of n elements
Output : a[1..n] sorted
Chapter 4 - Searching and Sorting
Method
for j= 2 to n in steps of 1 do
item = a[j]
i = j-1
while((i>=1) and (item<a[i])) do
a[i+1] = a[i]
i = i-1
while end
a[i+1] = item
for end
Algorithm ends
4.2.2 Selection Sortin.
Such algorithms construct the sorted sequence one element at a time by adding elements to the sorted
sequence in order. At each step, the next element to be added to the sorted sequence is selected from the
remaining elements.
Because the elements are added to the sorted sequence in order, they are always added at one end.
This is what makes selection sorting different from insertion sorting. In insertion sorting elements are
added to the sorted sequence in an arbitrary order. Therefore, the position in the sorted sequence at which
each subsequent element is inserted is arbitrary.
Both selection sorts described in this section sort the arrays in place. Consequently, the sorts are
implemented by exchanging array elements. Nevertheless, selection differs from exchange sorting because
at each step we select the next element of the sorted sequence from the remaining elements and then we
move it into its final position in the array by exchanging it with whatever happens to be occupying that
position.
Straight Selection Sortin.
The simplest of the selection sorts is called straight selection . Fig.4.2 illustrates how straight selection
works. In the version shown, the sorted list is constructed from the right (i.e., from the largest to the
smallest element values).
BSIT 41 Algorithms
At each step of the algorithm, a linear search of the unsorted elements is made in order to determine
the position of the largest remaining element. That element is then moved into the correct position of the
array by swapping it with the element which currently occupies that position.
Fig. 4.2 Selection sort
For example, in the first step shown in Fig 4.2, a linear search of the entire array reveals that 9 is the
largest element. Since 9 is the largest element, it belongs in the last array position. To move it there, we
swap it with the 4 that initially occupies that position. The second step of the algorithm identifies 6 as the
largest remaining element an moves it next to the 9. Each subsequent step of the algorithm moves one
element into its final position. Therefore, the algorithm is done after n-1 such steps.
Chapter 4 - Searching and Sorting
Algorithm : Selection Sort
Input : n, Size of the input domain
a[1..n], array of n elements
Output: a[1..n] sorted
Method:
for i
= 1 to n in steps of 1 do
j = i
for k
= i+1 to n in steps of 1 do
if(a[k]< a[j]) then j = k
for end
Interchange a[i] and a[j]
For end
Algorithm ends.
Two more sorting algorithms are discussed in the next chapter.
SUMMAR.
In this chapter two techniques for checking whether an element is presented in the list of elements is
presented. Linear search is best employed when data searching operation is used minimally. But when
data searching on the same data set has to be done several times then it is better to sort that data set and
apply binary search. Binary search reduces the effort in searching as in case of Linear search. The
chapter also presents some sorting techniques in sequel to searching. Selection sort is simplest of all
sorting algorithms and it goes for the selection of the largest element at each iteration. Insertion sort builds
a sorted list by inserting elements to a small sub sorted list.
EXERCIS.
1.
What are the serious short comings of the binary search method and sequential search method.
2.
Consider a data set of nine elements {10, 30, 45, 54, 56, 78, 213, 415, 500} and trace the linear search algorithm
to find whether the keys 30, 150, 700 are present in the data set or not.
3.
Trace the Binary search algorithm on the same data set and same key elements of problem 2.
4.
Try to know more sorting techniques and make a comparative study of them.
5.
Hand Simulate Insertion Sort on the data set { 13 , 45 , 12, 9 , 1, 10, 40}
6.
Implement all the algorithms designed in the chapter.
Chapter 5
Recursio.
5.1 WHAT IS RECURSION.
W
W
e look at the concept of recursion, which is one of the very powerful programming concepts,
supported by most of the languages. At the same time, it is also a fact that most beginners are
confused by the way it works and are unable to use it effectively. Also, some languages may
not support recursion. In such cases, it may become necessary to rewrite recursive functions into non-
recursive ones. All these and many other aspects are dealt with in this chapter.
Recursion is an offshoot of the concept of subprograms. A subprogram as we know is the concept of
writing separate modules, which can be called from other points in the program or other programs. Then
came a concept wherein any subprogram can call any other subprogram. The control goes to the called
subprogram, performs the assigned tasks and comes back to the caller programs.
Then comes the question – can a program call itself? Theoretically it is possible. If so, where do we
use them normally? A subprogram is called to perform a function, which the caller subprogram cannot
perform itself. But if the caller program calls itself, what purpose does it serve? The answer is, the
subprogram no doubt, calls itself, but with a different value of the parameter. In fact, in most cases, the
calling continues until some specific value of the parameter is reached.
We now understand that recursion is a process of defining a process/ problem/ an object in terms of
itself. Recursion is one of the applications of stacks. The recursive mechanisms are extremely powerful,
but even more importantly; many times they can express an otherwise complex process, very clearly.
Any program can be written using recursion. Of course, the recursive program in that case could be
tougher to understand. Hence, recursion can be used when the problem itself can be defined recursively.
The general procedure for any recursive algorithm is as follows,
1. Save the parameters, local variables and return addresses.
BSIT 41 Algorithms
Chapter 5 - Recursion
2. If the termination criterion is reached perform final computation and go to step 3, otherwise
perform final computations and go to step 1.
3. Restore the most recently saved parameters, local variables and return address and go to the
latest return address.
5.2 WHY DO WE NEED RECURSION.
When iteration can be easily used and also supported by most programming languages, why do we
need recursion at all? The answer is that iteration has certain demerits as is made clear below:
1. Mathematical functions such as factorial and fibonacci series generation can be easily
implemented using recursion than iteration.
2. In iterative techniques looping of statement is very much necessary.
5.3 WHEN TO USE RECURSION.
Recursion can be used for repetitive computations in which each action is stated in terms of previous
result. There are two conditions that must be satisfied by any recursive procedure.
1. Each time a function calls itself it should get nearer to the solution.
2. There must be a decision criterion for stopping the process.
In making the decision about whether to write an algorithm in recursive or non-recursive form, it is
always advisable to consider a tree structure for the problem. If the structure is simple then use non-
recursive form. If the tree appears quite bushy, with little duplication of tasks, then recursion is suitable.
Recursion is a top down approach to problem solving. It divides the problem into pieces or selects out
one key step, postponing the rest. Whereas, iteration is more of a bottom up approach. It begins with what
is known and from this constructs the solution step by step.
Let us now look at some basic examples which are often devised using recursion.
5.4 FACTORIAL OF A POSITIVE INTEGE.
The factorial of a number ‘n’ = n * (n-1) * (n-2)* … * 3 * 2 * 1. An iterative way of obtaining the
factorial of a given number is to put a ‘for’ loop to repeat the multiplication n times. We start with 1, then
evaluate 1 * 2, then that product * 3, ….*(n-1). The factorial of a number can also be obtained recursively.
BSIT 41 Algorithms
Suppose we are asked to evaluate N!. If we somehow know (N-1)! then we can evaluate N! = N*(N1)!.
But how do we get (N-1)!? The same logic can be employed to evaluate (N-1)! = (N-1) * (N-2)!.
The problem of finding the factorial of a given number can be recursively defined as
*
-
.
1
Thus, the algorithm developed to compute the factorial of a given number is
Algorithm: Factorial
Input: n, the integer value whose factorial is to be computed
ìíî
Output: factorial of n
Method:
If (n==1) then
Return (1)
Else
Return (n * factorial (n-1)
If end
Algorithm ends
The students are advised to try various values of n to actually see how the method works.
5.5 FINDING THE NTH FIBONACCI NUMBE.
As already introduced in Chapter 3, a Fibonacci series is a sequence of integers 0,1,1,2,3,5…… i.e.,
The Fibonacci sequence starts from 0, 1 and after that each new term will be the sum of the previous two
terms. .We shall here, at finding out what could be the nth Fibonacci number in the series. For instance, if
we say the first Fibonacci number then it is 0. The second Fibonacci number is 1. Thus, if the 6th Fibonacci
number asked then we are expected to produce the number 5. In general, if kth Fibonacci number is
expected then that can be obtained by summing up (k-1)th and (k-2)th fibonacci numbers. This process
can be recursively done and finally one can obtain the kth Fibonacci number.
Thus, following is the recursive algorithm designed to find the nth Fibonacci number
Algorithm: Fibonacci
Input: n, the position at which the Fibonacci number has to be computed
Factorial
(
1)
if
1
n
n
n
Factorial (n) [where n is a positive integer] =
if n
1
=
Chapter 5 - Recursion
Output: nth Fibonacci number
Method:
If (n==0)
Return (0)
Else
If (n == 1)
Return (1)
Else
Return (Fibonacci (n-1) + Fibonacci (n-2))
If end
If end
Algorithm ends
Again, the correctness can be checked for various input values.
We use a third example, though normally this method is not used to explain recursion, nevertheless it is
a very useful method.
5.6 SUM OF FIRST N INTEGER.
The sum of the integers to n is the sum of the integers through n -1 + n. The sum of the integers to n
-1 is the sum to n -2 to n -1, etc. Eventually, we know that the sum of the first positive integer is 1.
Therefore, we can define a terminating condition for some small subset of the problem. The recursive
algorithm to achieve this is as follows
Algorithm : SumPosInt
Input : n, the upper limit
Output : Sum of first n positive integers
Method:
if (n <= 0) // We only want positive integers
return 0;
BSIT 41 Algorithms
else
if (n == 0) // Our terminating condition
return 1;
else
return (n + SumPosInt( n -1 ); // recursive step
if end
if end
Algorithm ends
5.7 BINARY SEARC.
Binary search method as explained earlier is a process of searching for the presence or absence of a
key element in the sorted list. The approximate mid entry is located and its key value is examined. If the
mid value is greater than X, then the list is chopped off at the (mid-1)th location. Now the list gets reduced
to half the original list. The middle entry of the left-reduced list is examined in a similar manner. Thus, one
can always think of using a recursive algorithm to solve the same.
The recursive algorithm for binary search is as follows,
Algorithm : binary search
Input : A, vector of n elements
K, search element
Low, the lower limit
High, the upper limit //initially low=1 and high=n the number of elements
Output : the position of the K
Method : if (low <= high)
mid=(low+high)/2
if( a[mid] == K)
return(mid)
else
Chapter 5 - Recursion
if (a[mid]< K)
Binary search(A, K, Low, mid)
else
Binary Search(A, K, High, mid)
if end
if end
else
return(0)
if end
Algorithm ends.
5.8 MAXIMUM AND MINIMUM IN THE GIVEN LIST OF .
ELEMENT.
Here the problem is to find out the maximum values in a give list of n data elements. The recursive
algorithm designed to serve this purpose is as follows.
Algorithm: Max-Min
Input: p, q, the lower and upper limits of the dataset
max, min, two variables to return the maximum and minimum values in the list
Output: the maximum and minimum values in the data set
Method:
If (p = q) Then
max = a(p)
min = a(q)
Else
If ( p – q-1) Then
If a(p) > a(q) Then
BSIT 41 Algorithms
max = a(p)
min = a(q)
Else
max = a(q)
min = a(p)
If End
Else
m ¬ (p+q)/2
max-min(p,m,max1,min1)
max-min(m+1,q,max2,min2)
max f large(max1,max2)
min fsmall(min1,min2)
If End
If End
Algorithm Ends.
5.9 MERGE SOR.
Sorting as stated in Chapter 4, is a process of arranging a set of given numbers in some order. The
basic concept of merge sort is like this. Consider a series of n numbers, say A(1), A(2) ……A(n/2) and
A(n/2 + 1), A(n/2 + 2) ……. A(n). Suppose we individually sort the first set and also the second set. To
get the final sorted list, we merge the two sets into one common set.
We first look into the concept of arranging two individually sorted series of numbers into a common
series using an example:
Let the first set be A = {3, 5, 8, 14, 27, 32}. Let the second set be B = {2, 6, 9, 15, 18, 30}.
The two lists need not be equal in length. For example the first list can have 8 elements and the second
5. Now we want to merge these two lists to form a common list C. Look at the elements A(1) and B(1),
A(1) is 3, B(1) is 2. Since B(1) < A(1), B(1) will be the first element of C i.e., C(1)=2. Now compare
A(1) =3 with B(2) =6. Since A(1) is smaller then B(2), A(1) will become the second element of C. C[ ]
= {2, 3}
Chapter 5 - Recursion
Similarly compare A(2) with B(2), since A(2) is smaller, it will be the third element and so on. Finally,
C is built up as C[ ]= {2, 3, 5, 6, 8, 9, 14, 15, 18, 27, 30, 32}.
However the main problem remains. In the above example, we presume that both A & B are originally
sorted. Then only they can be merged. But, how do we sort them in the first? To do this and show the
consequent merging process, we look at the following example. Consider the series A= (7 5 15 6 4). Now
divide A into 2 parts (7, 5, 15) and (6, 4). Divide (7, 5, 15) again as ((7, 5) and (15)) and (6, 4) as ((6) (4)).
Again (7, 5) is divided and hence ((7, 5) and (15)) becomes (((7) and (5)) and (15)).
Now since every element has only one number, we cannot divide again. Now, we start merging them,
taking two lists at a time. When we merge 7 and 5 as per the example above, we get (5, 7) merge this with
15 to get (5, 7, 15). Merge this with 6 to get (5, 6, 7, 15). Merging this with 4, we finally get (4, 5, 6, 7 and
15). This is the sorted list.
You are now expected to take different sets of examples and see that the method always works.
We design two algorithms in the following. The main algorithm is a recursive algorithm (some what
similar to the binary search algorithm that we saw earlier) which calls at times the other algorithm called
MERGE. The algorithm MERGE does the merging operation as discussed earlier.
Algorithm: MERGESORT
Input: low, high, the lower and upper limits of the list to be sorted
A, the list of elements
Output: A, Sorted list
Method:
If (low<high)
mid¬ (low + high)/2
MERGESORT(low, mid)
MERGESORT (mid, high)
MERGE(A, low, mid, high)
If end
Algorithm ends
You may recall that this algorithm runs on lines parallel to the binary search algorithm. Each time it
divides the list (low, high) into two lists(low, mid) and (mid+1, high). But later, calls for merging the two
lists.
BSIT 41 Algorithms
Algorithm: Merge
Input: low, mid, high, limits of two lists to be merged i.e., A(low, mid) and A(mid+1, high)
A, the list of elements
Output: B, the merged and sorted list
Method:
h = low, i = low, j = mid + 1;
While ((h dŠ mid) and (j dŠ high)) do
If (A(h) dŠ A(j) )
B(i) = a(h);
h = h+1;
else
B(i) = A(j);
j = j+1;
If end
i = i+1;
If (h > mid)
For k = j to high
B(i) = A(k);
i = i+1;
For end
Else
For k = h to mid
B(i) = A(k);
i = i+1
For end
If end
While end
Algorithm ends