Unit – 5

Basic Algorithms

5.1 Searching (Linear Search, Binary Search Etc.)

Sorting and Searching are fundamental operations in computer science. Sorting refers to the operation of arranging data in some given order. Searching refers to the operation of searching the particular record from the existing information.

Consider a database of banking system where information of all customers such as name, contact number, address, account number is stored. If a manager wants to search for a record of a particular customer, he has to look for that record from among all records that has been stored in a database. This process of looking up for a particular record in a database is referred as searching.

If records in a banking database are not ordered properly it will be very difficult for a manager to search for a specific record. On the contrary if all record are arranged in order according to some criteria like names in alphabetical order or account numbers in ascending order, searching becomes easy and fast. The process of ordering the records in a data base is called sorting. Thus for efficient searching sorting is necessary.

Linear Search

Given a collection of objects, the goal of search is to find a particular object in this collection. The objects have key values on which search is performed and data values which correspond to the information one wishes to retrieve once an object is found. For example, a telephone book is a collection of names on which one searches and telephone numbers which correspond to the data being sought. The collection of objects is often stored in a list or an array. Given a collection of objects in an array A[1.. n], the ith  element A[i] corresponds to the key value of the ith  object in the collection. The input to a search algorithm is an array of objects A, the number of objects n, and the key value being sought x.

 Thus Algorithm for Linear Search is

 1. start at one end of the list

 2. if the current element is not equal to the search target, move to the next element,

 3. stop when a match is found or the opposite end of the list is reached.

 Function for Linear search is

 If element is found this function returns index of that element otherwise it returns –1.

Example : we have an array of integers, like the following:

 Let’s search for the number 7. According to function for linear search index for element 7 should be returned. We start at the beginning and check the first element in the array.

 First element is 9.Match is not found and hence we move to next element i.e 6.

 Again match is not found so move to next element i.e.7.

 We found the match at the index position 2. Hence output is 2.

 If we try to find element 10 in above array, it will return –1,as 10 is not present in the array.

Complexity Analysis of Linear Search:

 Let us assume element x is to be searched in array A of size n.

 An algorithm can be analyzed using following three cases.

 1. Worst case

 2. Average case

 3. Best case

 1. Worst case :In Linear search worst case happens when element to be searched is not present. When x is not present, the linear search function compares it with all the elements of A one by one. The size of A is n and hence x is to be compared with all n elements. Thus, the worst case time complexity of linear search would be O(n).

 2. Average case : In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs. Following is the value of average case time complexity.

 3. Best Case : In linear search , the best case occurs when x is present at the first location. So time complexity in the best case would be O(1).

Merits :

 1. Simple and easy to implement

 2. It works well even on unsorted arrays.

 3. It is memory efficient as it does not require copying and partitioning of the array being searched.

Demerits :

1. Suitable only for small number of values.
2. It is slow as compared to binary search.

Binary Search

 Binary Search requires sorted array.

 Steps to perform binary search on sorted array A of size n are as follows.

 1. Initialize lower and upper limit of array to be searched Low=0,High= n–1.

 2. Find the middle position

  Mid=(Low + High)/2

 3. Compare the input key value with the key value of the middle element of the array. It has 3 possibilities.

Case 1 : If keys match then return mid and print element found.

Case 2 : If key is less than middle element then element is present in left half of array. Update High and goto step 2. 

Case 3 : If key is greater than middle element then element is present in right half of array. Update Low and goto step 2. 

Case 4:if(Low>High)

Example 1 :Let array A= {–1, 5, 6, 18, 19, 25, 46, 78, 102, 114}. We want to find element ‘6’ using binary search.

Solution:

 Step 1 : Low=0, High= 9

 Step 2 :Mid=(Low + High)/2

 Mid = (0+9)/2 =4.5 i.e 4. It means middle element is located at position 4. So A[Mid] is 19.Thus

 Low=0

 Mid=4

 High=9   

 Step 3 :Compare 6 with 19. It satisfies case 2 of step 3. so High= 4–1=3 and element is present in left half of array. We can ignore right half of array.

 Repeat step 2. So mid= (0+3)/2 = 1.5 i.e 1. mid is at position 1. Element 5 is present at position 1.

 Low = 0

 Mid = 1

 High = 3

 Again compare 5 with 6. It satisfies case 3 of step 3. so

 Low = 1+1=2.  

 Repeat step 2. Mid= (2+ 3)/2= 2.5 i.e 2 .Mid is at position 2. Element 6 is at position 2.

 Low=2

 Mid=2

 High=3  

 Compare 6 with 6.

 Match is found. Return the position and print element found.

Example 2 : Find 103 in {–1, 5, 6, 18, 19, 25, 46, 78, 102, 114} using Binary Search.

Step 1 : Low=0

High=9

Step 2 :Mid=(0+9)/2=4

 So middle element is 19.

Step 3 : Compare(103,19)

 103>19 hence element is located at right half of array and we can ignore left half of array. Update Low and recalculate mid.

    Low = 4+1=5

    High = 9 

    Mid = (5+9)/2=7

 Middle element is 78. Compare(103,78)

 103>78. Recalculate Low and Mid

    Low = 7+1=8

    High = 9

    Mid = (8+9)/2=8

 Middle element is 102. Compare(103,102)

 103>102. Recalculate Low and Mid.

    Low = 8+1=9

    High = 9

 Here Low=High and match is not found hence we conclude that element is not present in array.

Example 3 : Find 44 in A={5,12,17,23,38,44,77,84,90} using binary search.

Step 1: Low=0

  High=8

  Mid=(0+8)/2=4

 Middle element is 38. Compare(44,38)

 44>38.Thus element is located at right half of array and we can ignore left half of array. Recalculate Low and Mid.

    Low = (4+1)= 5

    High = 8

    Mid = (5+8)/2=6.5 i.e 6

 Middle element is 77. Compare(44,77)

 44<77. Recalculate High and Mid.

 Low=5

    High = 6–1=5

    Mid = (5+5)/2=5

 Middle element is 44. Compare(44,44)

 Match is Found. Return index and print “Element Found.”

 Algorithm for Recursive Binary Search

Complexity Analysis of Binary Search :

 Assume our array size is 16.

 When n= 16 BinarySearch is called to reduce size to n=8.

 When n= 8 BinarySearch is called to reduce size to n=4.

 When n= 4 BinarySearch is called to reduce size to n=2.

 When n= 2 BinarySearch is called to reduce size to n=1 .

 Thus we see that BinarySearch function is called 4 times

 i.e. 4 elements of the array were examined for n =16.

 Note that 16 = 24

 Let us consider a more general case where

 n is still a power of 2. Let us say n =2k

 After k searches, the while loop is executed k times and n reduces to size 1. Let us assume that each run of the while loop involves at most 4 operations.

 Thus total number of operations: 4k.

 The value of k can be determined from the expression

    2k = n

 Taking log of both sides

    k = log n

 Thus total number of operations = 4 log n.

 We conclude that the time complexity of the Binary search method is O(log n), which is much more efficient than the Linear Search method.

Merits :

 Binary Search is fast and efficient.

 Suitable for large number of values.

Demerits :

 Binary search works only on sorted array or list.

5.2 Basic Sorting Algorithms (Bubble, Insertion And Selection)

Bubble Sort     

Steps to perform Bubble sort are as follows.

Assume we want to sort the elements in ascending order and no two elements are equal.

1. Compare first element with second element. If first element is greater than next element, we interchange their position accordingly. i.e first element is moved to second element’s position and second element is moved to first element’s position. If No, then we don’t interchange any elements. 

2. The element in second position is compared with element in third position and the process of interchanging elements is performed if second is greater than third element. The whole process of comparing and interchanging is repeated till last element. When the process gets completed, the largest element in array will get placed in the last position of the array.

Let us consider array A of size n. Then Algorithm for Bubble sort is

1. Set i to 0.

2. Set j to 0.

3. if(A[j]>A[j+1])

swap A[j],A[j+1]

4. Increment j

5. if j<(n–1–i) goto step 3

6. Increment i

7. if(i<n–1) goto step  2.

Example 1 : Suppose the following numbers are stored in an array A:

 We apply bubble sort to array A. We discuss each pass separately.

Pass 1

 1. Compare j[0] and j[1]. Since 32 < 51, the list is not altered.

 2. Compare j[1] and j[2] Since 51 > 27, interchange 51 and 27 as follows:

 Array A becomes

 3. Compare j[2] and j[3]. Since 51 < 85, array is not altered.

 4. Compare j[3] and j[4]. Since 85 > 66, interchange 85 and 66 as follows:

 Array A becomes

 5. Compare j[4] and j[5]. Since 85 > 23, interchange 85 and 23 as follows:

 Array A becomes

 6. Compare j[5] and j[6]. Since 85 > 13, interchange 85 and 13 as follows:

 7. Compare j[6] and j[7]. Since 85 > 57, interchange 85 and 57 as follows:

 Array A becomes

 At the end of this first pass, the largest number, 85, has moved to the last position. However, the rest of the numbers are not sorted, even though some of them have changed their positions.

 Pass 2 will move second last number at second last position, Pass 3 will move third last number at third last position and so on. Here we show array after every pass.

Pass 2 :

Pass 3 :

Pass 4:

Pass 5 :

Pass 6 :

 Hence the array is sorted in 6 passes.

 We will see one more example

Example 2 : Apply Bubble Sort on array A= {5,3,1,9,8,2,4,7}. 

Pass 2 :i=2 

Pass 3 :

Pass 4 :

 This array gets sorted in 4 passes only.

Example : Apply Bubble Sort on array A= {23,78,45,8,32,56}

Pass 1 :

Pass 2 :

Pass 3 :

 This array is sorted in 3 passes.

Complexity Bubble sort:

 Suppose we have a list with n elements, and each element perform n – 1 comparisons with elements to its left, and swap, if necessary.

 Best Case: If the list is already sorted, only one iteration is performed  and complexity is O(1).

 Average and Worst case: For n elements at most n – 1 swap operations is performed in each pass. The worst and average case complexity is O(n2).

Selection Sort

 Assume we want to sort list in ascending order. Selection sort finds the smallest element from unsorted list and swap it with the element in first position. Then it finds second smallest element and swap it with element at second position. This process is repeated till entire list is sorted in ascending order. Each time we swap elements,  we say that we  have completed a sort pass. A list of  n elements requires  n–1 passes to completely  rearrange the data.

 Procedure for every pass is as follows.

 Pass 1 : Find the position P of the smallest in the list of N elements A[l], A[2], . . . , A[N], and then interchange A[P] and A[1] . Then A[1] is sorted.

 Pass 2 : Find the position P of the smallest in the sublist of N –1 elements A[2], A[3],. . . , A[N], and then interchange A[P]and A[2]. Then A[l], A[2] is sorted.

 Pass 3 : Find the position P of the smallest in the sublist of N–2  elements A[3], A[4], . . . , A[N], and then interchange A[P] and A[3]. Then: A[l], A[2] , A[3] is sorted.

 Pass N –1 :Find the position P of the smaller of the elements A[N –1), A[N], and then interchange A[P] and A[N–1]. Then: A[l], A[2], . . . , A[N] is sorted. Thus A is sorted after N –1 passes.

Example 1 :

Fig. 4.2 : Original List

 We will apply selection sort on this list.

 Unsorted sublist has 25 as a smallest element and 79 is located at second position. Hence we swap 25 and 79.

After Pass 5 :

Thus list is sorted.

We will see one more example.

Apply selection sort on array A= {77,30,40,10,88,20,65,56}

Output:

 Enter number of elements

 5

 Enter 5 integers

 4

 1

 7

 5

 9

 Sorted list in ascending order

 1

 4

 5

 7

 9

Complexity of Selection Sort :

In selection sort outer for loop is executed n–1 times. On the kth time through the outer loop, initially the sorted list holds

k–1 elements and unsorted portion holds n–k+1 elements.  In inner for loop 2 elements are compared each time.

Thus, 2*(n–k) elements are examined by the inner loop during the k th pass through the outer loop. But k ranges from 1 to n–1.

Total number of elements examined is:

T(n) = 2*(n –1) + 2*(n–2) + 2*(n–3) + .. + 2*(n–(n–2))

 + 2*(n–(n–1))

    = 2*((n–1) + (n–2) + (n–3) + ... + 2 + 1)

 (or 2*(sum of first n–1 integers)

    = 2*((n–1)*n)/2)

    = n2 – n, so complexity of algorithm is O(n2).

Insertion Sort 

 Insertion Sort reads all elements from 1 to n and inserts each element at its proper position. This sorting method works well on small list of elements. 

 Procedure for each pass is as follows.

Pass 1 :

 A[l] by itself is trivially sorted.

Pass 2 :

 A[2] is inserted either before or after A[l] so that: A[l], A[2] is sorted.

Pass 3 :

 A[3] is inserted into its proper place so that: A[l], A[2], A[3] is sorted.

Pass 4 :

 A[4] is inserted into its proper place A[l], A[2], A[3], A[4] is sorted.

Pass N :

 A[N] is inserted into its proper place in  so that:

 A[l], A[ 2 ] , . . . , A[ N ] is sorted

Example :We will apply insertion sort on original list of Fig.3.Assume we are arranging elements in ascending order.

Fig. 4.3 : Original List

Output  :

 Enter number of elements

 5

 Enter 5 integers

 9

 4

 2

 5

 3

 Sorted  list in ascending order

 2

 3

 4

 5

 9

Complexity of Insertion Sort :

 Worst Case Complexity: In the worst case, for each i we do (i – 1) swaps inside the inner for–loop–therefore, overall number of swaps (when i goes from 2 to n in the outer for loop) is

    T(n) = 1 + 2 + 3 +...+(I – 1) +....+ n – 1

     = n  (n – 1)/2

     = O(n2)

 Average case Complexity is O(n2).

 Best Case Complexity is O(n).

5.3 Finding Roots Of Equations

Algorithm:

Step 1: Start

Step 2: Read a,b,c

Step 3: Initialize d <- (b*b) – (4*a*c)

Step 4: Initialize r<- b/2*a

Step 5: if d>0 go to step 6

Step 6: r1 = r+(sqrt(d)/2*a) and r2 = r-(sqrt(d)/2*a)

Step 7: print roots are real and distinct first root r1, second root r2

Step 8: if d=0 go to step 9

else go to step 10

Step 9: print roots are real and equal -r

Step 10 : d= -d

Step 11: im = sqrt(d)/2*a

Step 12: print roots are imaginary, first root r+iim, second root r-iim

Step 13: stop

Program:

void main()

{

float a,b,c,r,d,r1,r2,im;

clrscr();

printf(“\n\t Quadratic Eqution\n\n Enter the coefficients\n”);

scanf(“%f%f%f”, &a,&b,&c);

d= (b*b) –(4*a*c);

r=b/2*a

if(d>0)

{

r 1 = -r + (sqrt (d)/2*a)

r2 = -r - + (sqrt (d)/2*a)

printf(“\n Roots are real and distinct \n\n first root\t: %.2f\n\n second root\t:%.2f \n”,r1,r2);

}

else if(d==0)

printf(“\n Roots are real and equal \n\n roots =:%.2f,-r);

}

else

{

d=-d;

im=sqrt(d)/2*a;

printf(“\nRoots are imaginary \n\nfirst root\t;%.2f\n\nsecond root\t:%.2f-i%.2f”,r,im,r,im);

}

getch();

}

5.4 Notion Of Order Of Complexity Through Example Programs (No Formal Definition Required)

To express the running time complexity of algorithm three asymptotic notations are available. Asymptotic notations are also called as asymptotic bounds. Notations are used to relate the growth of complex function with the simple function. Asymptotic notations have domain of natural numbers. These notations are as follows

1. Big-oh notation: Big-oh notations can be express by using ‘o’ symbol. This notation indicates the maximum number of steps required to solve the problem. This notation expresses the worst case growth of an algorithm. Consider the following diagram in which there are two functions f(x) and g(x). f(x) is more complex than the function g(x).

Fig. 3.7

In the above diagram out of two function f(n) and g(n), more complex function is f(n), so need to relate its growth as compare to simple function g(n). More specifically we need one constant function c(n) which bound function f(n) at some point n0. Beyond the point ‘n0’ function c*g(n) is always greater than f(n).

Now f(n)=Og(n)if there is some constant ‘c’ and some initial value ‘n0’. such that f(n)<=c*g(n) for all n>n0

 In the above expression ‘n’ represents the input size

 f(n) represents the time that algorithm will take

 f(n) and g(n) are non-negative functions.

 Consider the following example

Fig. 3.8

In the above example g(n) is ‘’n’ and f(n) is ‘2n+1’ and value of constant is 3. The point where c*g(n) and f(n) intersect is ‘’n0’. Beyond ‘n0’ c*g(n) is always greater than f(n) for constant ‘3’. We can write the conclusion as follows

 f(n)=O g(n)    for constant ‘c’ =3 and ‘n0’=1

 such that f(n)<=c*g(n) for all n>n0

2. Big-omega notation: Big-omega notations can be express by using ‘Ω’ symbol. This notation indicates the minimum number of steps required to solve the problem. This notation expresses the best case growth of an algorithm. Consider the following diagram in which there are two functions f(n) and g(n). f(n) is more complex than the function g(n).

Fig. 3.9

In the above diagram out of two function f(n) and g(n), more complex function is f(n), so need to relate its growth as compare to simple function g(n). More specifically we need one constant function c(n) which bound function f(n) at some point n0. Beyond the point ‘n0’ function c*g(n) is always smaller than f(n).

Now f(n)=Ωg(n)if there is some constant ‘c’ and some initial value ‘n0’. such that c*g(n) <= f(n)for all n>n0

 In the above expression ‘n’ represents the input size

 f(n) represents the time that algorithm will take

 f(n) and g(n) are non-negative functions.

 Consider the following example

In the above example g(n) is ‘2n’ and f(n) is ‘2n-2’ and value of constant is 0.5. The point where c*g(n) and f(n) intersect is ‘’n0’. Beyond ‘n0’ c*g(n) is always smaller than f(n) for constant ‘0.5’. We can write the conclusion as follows

 f(n)=Ω g(n)    for constant ‘c’ =0.5 and ‘n0’=2

 such that  c*g(n)<= f(n) for all n>n0

Fig. 3.10

Big-theta notation: Big-theta notations can be express by using ‘Ɵ’ symbol. This notation indicates the exact number of steps required to solve the problem. This notation expresses the average case growth of an algorithm. Consider the following diagram in which there are two functions f(n) and g(n). f(n) is more complex than the function g(n).

Fig. 3.11

In the above diagram out of two function f(n) and g(n), more complex function is f(n), so need to relate its growth as compare to simple function g(n). More specifically we need one constant function c1 and c2 which bound function f(n) at some point n0. Beyond the point ‘n0’ function c1*g(n) is always smaller than f(n) and c2*g(n) is always greater than f(n).

 Now f(n)= g(n) if there is some constant ‘c1 and c2’ and some initial value ‘n0’. such that c1*g(n) <= f(n)<=c2*g(n)for all n>n0

 In the above expression ‘n’ represents the input size

 f(n) represents the time that algorithm will take

 f(n) and g(n) are non-negative functions.

 f(n)= g(n) if and only if f(n)=O g(n) and f(n)=Ω g(n)

 Consider the following example

Fig. 3.12

In the above example g(n) is ‘2n’ and f(n) is ‘3n-2’ and value of constant c1 is 0.5 and c2 is 2. The point where c*g(n) and f(n) intersect is ‘’n0’. Beyond ‘n0’ c1*g(n) is always smaller than f(n) for constant ‘0.5’ and c2*g(n) is always greater than f(n) for constant ‘2’. We can write the conclusion as follows

 f(n)=Ω g(n)    for constant ‘c1’ =0.5 , ‘c2’ = 2 and ‘n0’=2

 such that  c1*g(n)<= f(n)<=c2*g(n) for all n>n0

Reference

• Brian W. Kernighan And Dennis M. Ritchie, The C Programming    Language, Prentice Hall Of India

• YashwantKanetkar, Let Us C, Bpb Publication