1

Searching:

Is a process of verifying whether the given element is available in the given set of elements
or not. Types of Searching techniques are:
1. Linear Search
2. Binary Search
3. Fibonacci Search
1. Linear Search
In linear search, search process starts from starting index of array. i.e. 0th index of array
and end’s with ending index of array. i.e. (n-1)th index. Here searching is done in Linear fashion
(Sequential fashion).

Algorithm Linearsearch(a<array>, n, ele)

Input: a is an array with n elements, ele is the element to be searcheD)
Output: Position of required element in array, if it is available.
1. found = 0
2. i =0
3. while(i < n)
a) if(ele == a[i])

i) found = 1
ii) print( element found at ith position)
iii) break
b) end if
c) i = i +1
4. end loop
5. if( found == 0)
a) print( required element to be search is not available)
6. end if
End Linearsearch

I Year-II Semester 2023-24 IT

 2

Algorithm Linearsearch_Recurssion(a<array>, i, n, ele)

Input: a is an array with n elements, ele is the element to be searched, i is starting index of array
and n is the ending index.
Output: Position of required element in array, if it is available.
1. found = 0
2. if(i<n)
a) if(a[i] == ele)
i) found = 1
ii) print( element found at ith position)
b) end if
c) Linearsearch_Recurssion(a, i+1, n, ele)
4. end if
5. if( found == 0)
a) print( required element to be search is not available)
6. end if
End Linearsearch_Recurssion

2. Binary Search
The input to binary search must be in ascending order. i.e. set of elements be in
ascending order.
Searching process in Binary search as follows:
 First, the element to be search is compared with middle element of array.

 If the required element to be searched is equal to middle element of array then Successful
Search.
 If the required element to be searched is less than the middle element of array, then
search in LEFT side of the midpoint of the array.
 If the required element to be search is greater than middle element of array, then search
in RIGHT side of the midpoint of the array.

I Year-II Semester 2023-24 IT

 3

Algorithm Binarysearch(a<array>, n, ele)

Input: a is an array with n elements, ele is the element to be searcheD)
Output: Position of required element in array, if it is available.
1. found = 0
2. low = 0
3. high = n-1
4. while(low <= high)
a) mid = (low+high )/2.
b) if(ele == a[mid])
i) print(required element was found at mid position)
ii) found = 1
iii) break
c) else if(ele < a[mid])
i) high = mid - 1
d) else if(ele > a[mid])
i) low= mid + 1
e) end if
5. end if
6. if(found == 0)
a) print(required element is not available)
7. end if
End Binarysearch

Algorithm Binarysearch_Recursion(a<array>,ele, low, high)

Input: a is array with n elements, ele is the element to be searched, low is starting index, high is
ending index of array.
Output: Position of required element in array, if it is available.

I Year-II Semester 2023-24 IT

 4

1. found = 0
2. if(low <= high)
a) mid = (low+high )/2.
b) if(ele == a[mid])
i) print(required element was found at mid position)
ii) found = 1
c) else if(ele < a[mid])
i) Binarysearch _Recursion(a,ele,low,mid-1)
d) else if(ele > a[mid])
i) Binarysearch_Recursion(a,ele,mid+1,high)
e) end if
3. end if
4. if(found == 0)
a) print(required element to be search is not available)
5. end if
End Binarysearch_Recursion
Sorting: Sorting means arranging the elements either in ascending or descending order.
There are two types of sorting.
1. Internal Sorting.
2. External Sorting.
1. Internal Sorting: For sorting a set of elements, if we use only primary memory (Main
memory), then that sorting process is known as internal sorting. i.e. internal sorting deals with
data stored in computer memory.
2. External Sorting: For sorting a set of elements, if we use both primary memory (Main
memory) and secondary memory, then that sorting process is known as external sorting. i.e.
external sorting deals with data stored in files.
Different types of sorting techniques.
1. Bubble sort
2. Insertion sort
3. Selection sort
4. Merging sort
5. Quick sort
6. Radix sort

I Year-II Semester 2023-24 IT

 5

1. Bubble sort:
 In bubble sort for sorting n elements, we require (n-1) passes (or) iterations and in each
pass compare every element with its successor. i.e. ith index element will compare with
(i+1)th index element, if they are not in ascending order, then swap them.
 Here for each pass, the largest element is moved to height index position of array to be
sort.
Process:
1. In pass1, a[0] and a[1] are compared, then a[1] is compared with a[2], then a[2] is
compared with a[3] and so on. Finally a[n-2] is compared with a[n-1]. Pass1 involves (n-
1) comparisons and places the biggest element at the highest index of the array to be
sorteD)
2. In pass2, a[0] and a[1] are compared, then a[1] is compared with a[2], then a[2] is
compared with a[3] and so on. Finally a[n-3] is compared with a[n-2]. Pass2 involves (n-
2) comparisons and places the biggest element at the highest index of the array to be
sorteD)
3. In pass (n-1), a[0] and a[1] are compareD) After this step all the elements of the array are
arranged in ascending order.

Eg: sort the elements 72, 85, 4, 32 and 16 using Bubble sort.

0 1 2 3 4
Pass 1 72 85 24 32 16
72 85 24 32 16 (0, 1) No Exchange
72 24 85 32 16 (1, 2) Exchange
72 24 32 85 16 (2, 3) Exchange
72 24 32 16 85 (3, 4) Exchange

Pass 2 72 24 32 16 85
24 72 32 16 85 (0, 1) Exchange
24 32 72 16 85 (1, 2) Exchange
24 32 16 72 85 (2, 3) Exchange

I Year-II Semester 2023-24 IT

 6

Pass 3 24 32 16 72 85
24 32 16 72 85 (0, 1) No Exchange
24 16 32 72 85 (1, 2) Exchange

Pass 4 24 16 32 72 85
16 24 32 72 85 (0, 1) Exchange

Sorted List is 16 24 32 72 85

Algorithm Bubblesort(a<array>, n)
Input: a is an array with n elements to be sort.
Output: array elements in ascending order.
1. for( i = 0 to n-1)
a) for( j = 0 to n-i-1)
i) if ( a[j] > a[j+1] )
A) t = a[j]
B) a[j] = a[j+1]
C) a[j+1] = t
ii) end if
b) end j for loop
2. end i for loop
End Bubblesort
2. Insertion sort
 In the insertion sort, initially consider the 0th index element value as only sorted element,
and then take remaining elements of the given set one by one.
 For every pass, compare unsorted elements one by one with sorted list.
 If sorted list value is GREATER than the unsorted element value, then move sorted list
element to next index.
 Continue the above moving process up to sorted list element value is LESS than given
unsorted element value.
 Continue the above process for all the elements in the given array.

I Year-II Semester 2023-24 IT

 7

Algorithm insertionsort(a<array>, n)
Input: a is array with n elements to be sorteD)
Output: array elements in ascending order.
1. i = 1
2. while( i < n)
a) x = a[i] /* x is unsorted element */
b) j = i -1
c) while( j >= 0 && a[j] > x )
i) a[j+1] = a[j]
ii) j = j -1
d) end loop
e) a[j+1] = x
f) i = i + 1
3. end loop
End insertionsort
Eg: sort the elements 15,10, 8, 46, 32 using Insertion sort. Where x is an unsorted
element

0 1 2 3 4 x
Sorted ele > unsorted ele. TRUE. i.e. 15>10.
Pass 1 15 10 8 46 32 10
So move 15 from 0th index to 1st index
15 8 46 32
Last index is 0th index.
10 15 8 46 32
So place x value in 0th index

0 1 2 3 4 x
Sorted ele > unsorted ele. TRUE. i.e. 15 > 8
Pass 2 10 15 8 46 32 8
So move 15 from 1st index to 2nd index
Sorted ele > unsorted ele. TRUE. i.e. 10 > 8
10 15 46 32
So move 10 from 0thindex to 1stindex
10 15 46 32
Last index is 0th index.
8 10 15 46 32
So place x value in 0th index

0 1 2 3 4 x
Sorted ele> unsorted ele. FALSE. i.e. 15>46 is
Pass 3 8 10 15 46 32 FALSE
46

I Year-II Semester 2023-24 IT

 8

So place x value in next index of sorted element

8 10 15 46 32

Pass 4 0 1 2 3 4 x
Sorted ele> unsorted ele. TRUE. i.e. 46 > 32
8 10 15 46 32 32
So move 46 from 3rdindex to 4thindex
Sorted ele> unsorted ele. FALSE. i.e. 15 >32 is
8 10 15 46 FALSE
So place x value in next index of sorted element
8 10 15 32 46
Now all the elements are sorted

3. Selection Sort
In selection sort first find the smallest element in the array and place it in to the array to
the 0 position. Then find the second smallest element in the array and place it in 1 st position.
th

Repeat this procedure until array is sorteD)

Process:
 In Pass1, find the position of the smallest element in the array and then swap a[pos] and
a[0]. Now a[0] is sorteD)
 In Pass2, find the position of the smallest element in sub array of n-1 elements, then swap
a[pos] and a[1]. Now a[1] is sorteD)
 In Pass n-1, find the position of the smallest element from a[n-2] and a[n-1], then swap
a[pos] and a[n-21]. So that a[0], a[1], a[2], a[3], ......... , a[n-1] is sorteD)

Eg: sort the elements 15, 10, 11, 41, 3 using selection sort
0 1 2 3 4 pos
th
Pass 1 15 10 11 41 3 pos is initially assigned at 0 index 0
15 10 11 41 3 a[1] < a[pos] is TRUE. So pos =1 1
15 10 11 41 3 a[2] < a[pos] is FALSE. So No change in pos 1
15 10 11 41 3 a[3] < a[pos] is FALSE. So No change in pos 1
15 10 11 41 3 a[4] < a[pos] is TRUE. So pos =4 4
Now swap a[pos] and a[0]
0 1 2 3 4
3 10 11 41 15
Now a[0] is sorted

I Year-II Semester 2023-24 IT

 9

0 1 2 3 4 pos
st
Pass 2 3 10 11 41 15 Now pos is assigned at 1 index 1
3 10 11 41 15 a[2] < a[pos] is FALSE. So No change in pos 1
3 10 11 41 15 a[3] < a[pos] is FALSE. So No change in pos 1
3 10 11 41 15 a[4] < a[pos] is FALSE. So No change in pos 1
Now swap a[pos] and a[1]
0 1 2 3 4
3 10 11 41 15
Now a[1] is sorted

0 1 2 3 4 pos
Pass 3 3 10 11 41 15 Now pos is assigned at 2ndindex 2
3 10 11 41 15 a[3] < a[pos] is FALSE. So No change in pos 2
3 10 11 41 15 a[4] < a[pos] is FALSE. So No change in pos 2
Now swap a[pos] and a[2]
0 1 2 3 4
3 10 11 41 15
Now a[2] is sorted

0 1 2 3 4 pos
rd
Pass 4 3 10 11 41 15 Now pos is assigned at 3 index 3
3 10 11 41 15 a[4] < a[pos] is TRUE. So pos = 4 4
Now swap a[pos] and a[3]
0 1 2 3 4
3 10 11 15 41
Now all the elements are sorted

Algorithm selectionsort (a<array>, n)

Input: a is an array with n elements to be sorteD)

Output: array elements in ascending order.
1. i = 0
2. while( i < n)
a) pos = i
b) j = i+1
c) while ( j < n)
I Year-II Semester 2023-24 IT
 10

i) if ( a[j] < a[pos] )

A) pos = j
ii) end if
iii) j = j +1
d) end loop
e) t = a[pos]
f) a[pos] = a[i]
g) a[i] =t
h) i= i+1
3. end loop
End selectionsort

I Year-II Semester 2023-24 IT