Chapter Five

Simple Sorting and

Searching Algorithms
 Searching
Is a process of finding an element in a list of items or determining that
the item is not in the list.
To keep things simple, we shall deal with a list of numbers.
A search method looks for a key, arrives by parameter.
By convention, the method will return the index of the element
corresponding to the key or, if unsuccessful, the value -1
There are two simple searching algorithms:
 Sequential Search, and
 Binary Search
 a) Sequential Searching (Linear)
The easiest way to find our number is to start at the beginning
and compare our number (which we will call the target) to
each number in the list. If we reach our target, then we are
done. This method of searching is called Linear Searching.
Here is the algorithm:
1. Start with the first item in the list.
2. Compare the current item to the target
3. If the current value matches the target then we declare
victory and stop.
4. If the current value is not equal to key so go to the
second one loc=loc+1 repet until u get equal
 Cont..
0 1 2 3 4 5 6 7 8 n=9
A= 12 34 2 56 37 67 13 47
equal
Algorithm Let A be an array of n elements, A[1],A[2],A[3], ...... A[n]. “key” is the
element to be searched. Then this algorithm will find the location “loc” of key
in A.
For(loc =0;loc<n;loc++)
{
If(A[loc]==key)
Printf(“element found at index %d” ,A[loc])
}
else
Cout <<“element is not found\n”
 Binary Searching
Binary search is a fast search algorithm .This search
algorithm works on the principle of divide and conquer.
For this algorithm to work properly, the data collection
should be in the sorted form.
Assume sorted data
Use Divide and conquer strategy (approach).
Binary search is an extremely efficient algorithm when it is
compared to linear search. Binary search technique searches
“data” in minimum possible comparisons. Suppose the
given array is a sorted one, otherwise first we have to sort
the array elements.
Then apply the following conditions to search a “data”.
Binary search looks for a particular item by comparing the
middle most item of the collection.
Algorithm:
i. In a binary search, we look for the key in the middle of the
list. If we get a match, the search is over
ii. If the key is greater than the element in the middle of the list, we
make the top (upper) half the list to search.
iii. If the key is smaller, we make the bottom (lower) half the list to
search.
Algorithm/pseudocode
The pseudocode of binary search algorithms should look like this
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 0,Set upperBound = n
Cont..
while x not found
if upperBound < lowerBound
EXIT: x does not exists.
else
set midPoint = (lowerBound + upperBound)/ 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while
 Show How Binary Search Works? With e.g.
• For a binary search to work, it is mandatory for the target array to be
sorted. We shall learn the process of binary search with a pictorial
example
The following is our sorted array and let us assume
that we need to search the location of value key=31 using binary search.

First, we shall determine half of the array by using this formula

mid = low + high / 2
Here it is,( 0 + 9) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.
 Cont..
• Now we compare the value stored at location 4, with the value
being searched, i.e. 31. We find that the value at location 4 is 27,
which is not a match. As the value is greater than 27 and we have a
sorted array, so we also know that the target value must be in the
upper portion of the array.

We change our low to mid + 1 and find the new mid value again.
newlow = mid + 1=4+1=5
mid = (newlow + upper) / 2
mid=5+9/2=7.5
Our new mid is 7 now. We compare the value stored at location 7 with
our target value 31.
 Cont..
• The value stored at location 7 is not a match, rather it is more than
what we are looking for. So, the value must be in the lower part
from this location.Hence, we calculate the mid again. This time it is
5. if A[midPoint] > x

set upperBound = midPoint – 1

upperbound=7-1=6 mid=oldlow+newupper/2
Mid=(5+6)/2=5.55

We compare the value stored at location 5 with our target value. We

find that it is a match.
We conclude that the target value 31 is stored at location 5.
 2. Sorting Algorithm
Sorting: is a process of reordering a list of items in either increasing or
decreasing order/Sorting: an operation that segregates items into groups
according to specified criterion. Sorting is used to arrange names and
numbers in meaningful ways.
A={3162134590}
A={0112334569}
Some of sorting mechanism
i. Bubble Sort
ii. Selection Sort
iii. Insertion sort
 I. Bubble sort
Repetitively compares adjacent pairs of elements and swaps if
necessary. In bubble sort, each element is compared with its adjacent
element. If the first element is larger than the second one, then the
positions of the elements are interchanged, otherwise it is not changed.
Then next element is compared with its adjacent element and the same
process is repeated for all the elements in the array until we get a sorted
array.
Algorithm:
1. Scan the array ,swapping adjacent pairs of elements if they are not
in relative order This bubbles up the largest element to the end.
2. Scan the array again bubbling up the second largest element
3. Repeat until all elements are in order.
4. Continue as above until you have no unsorted elements on the left
5. The example below have 4 round until it sorted one
 Example of bubble sort

7 2 8 5 4 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8
2 7 8 5 4 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8
2 7 8 5 4 2 5 7 4 8 2 4 5 7 8 (done)
2 7 5 8 4 2 5 4 7 8

2 7 5 4 8
Cont..
1. Input n numbers of an array A
2. Initialize i = 0 and repeat through step 4 if (i < n-1)
3. Initialize j = 0 and repeat through step 4 if (j < n – i – 1)
4. If (A[j] > A[j + 1])
(a) Swap = A[j]
(b) A[j] = A[j + 1]
(c) A[j + 1] = Swap
5. Display the sorted numbers of array A
6. Exit.
 Cont..
Implementation:
void bubble_sort(list[])
{
int i,j,temp;
for(i=0;i<n; i++){
for(j=n-1;j>i; j--){
if(list[j]<list[j-1]){
temp=list[j];
list[j]=list[j-1];
list[j-1]=temp;
}//swap adjacent elements
}//end of inner loop
}//end of outer loop
}//end of bubble_sort
II. Selection Sort: Idea
To repetitively pick up the smallest element from unsorted group and
put it to sorted one.
Selection sort algorithm finds the smallest element of the array and
interchanges it with the element in the first position of the array. Then
it finds the second smallest element from the remaining elements in
the array and places it in the second position of the array and so on…
1. We have two group of items: sorted group, and unsorted group
2. Initially, all items are in the unsorted group. The sorted group is
empty.
Basic Idea:
1. Loop through the array from i=0 to n-1.
2. Select the smallest element in the array from i to n
3. Swap this value with value at position i.
 Algorithm
1. Select the “best” (eg. smallest) item from the unsorted group,
then put the “best” item at the end of the sorted group.
2. Repeat the process until the unsorted group becomes empty.
• Let A be a linear array of ‘n’ numbers, A [1], A [2], A [3],...... A
[n].
Step 1: Find the smallest element in the array of n numbers A[1],
A[2], ...... A[n]. Let LOC is the location of the smallest number in the
array. Then interchange A[LOC] and A[1] by swap = A[LOC];
A[LOC] = A[1]; A[1] = Swap.
Step 2: Find the second smallest number in the sub list of n – 1
elements A [2] A [3] ...... A [n – 1] (first element is already sorted).
Now we concentrate on the rest of the elements in the array. Again A
[LOC] is the smallest element in the remaining array and LOC the
corresponding location then interchange A [LOC] and A [2].Now A
[1] and A [2] is sorted, since A [1] less than or equal to A [2].
 Cont..
Step 3: Repeat the process by reducing one element each from the array
Selection Sort pick largest element

5 1 3 4 6 2

5 1 3 4 6 2
Selection Sort
5 1 3 4 2 6
Comparison

Data Movement

Sorted

5 1 3 4 2 6

Largest

2 1 3 4 5 6
Selection Sort
2 1 3 4 5 6
Comparison 
Largest
Data Movement

Sorted

2 1 3 4 5 6

Largest
 Selection Sort
2 1 3 4 5 6

Largest Comparison

Data Movement

Sorted

1 2 3 4 5 6
 Selection Sort

1 2 3 4 5 6
DONE!
Implementation
void selectionSort(int list[ ] ) {
int minIndex, temp;
for (int i = 0; i <= n - 2; i++) {
minIndex = i;
for (j = i + 1; j <= n-1; j++)
if (list[j] < list[minIndex])
minIndex = j;
if (minIndex != i) {
temp = list[i];
list[i] = list[minIndex];
list[minIndex] = temp;
}}}
Algorithm selection sort
1. Input n numbers of an array A
2. Initialize i = 0
smallest=i
3. Initialize j = i + 1
4. if ( a[smallest}>a[j]])
(a) smallest=j
5. if (smallest! = i)
(a) swap = a[i]
(b) a[i] = a[smallest]
(c) a[smallest] = swap
6. display “the sorted numbers of array A”
7.exit
 III. INSERTION SORT
• Insertion sort algorithm sorts a set of values by inserting
values into an existing sorted file. Compare the second
element with first, if the first element is greater than
second, place it before the first one. Otherwise place is
just after the first one. Compare the third value with
second. If the third value is greater than the second value
then place.
• It just after the second. Otherwise place the second value
to the third place. And compare third value with the first
value. If the third value is greater than the first value place
the third value to second place, otherwise place the first
value to second place. And place the third value to first
place and so on.
 Cont..
1. The left most value can be said to be sorted relative to itself.
Thus, we don’t need to do anything.
2. Check to see if the second value is smaller than the first one.
If it is, swap these two values. The first two values are now
relatively sorted.
3. Next, we need to insert the third value in to the relatively
sorted portion so that after insertion, the portion will still be
relatively sorted.
4. Remove the third value first. Slide the second value to make
room for insertion. Insert the value in the appropriate
position.
5. Now the first three are relatively sorted.
6. Do the same for the remaining items in the list.
 Algorithm for insertion sort
1. Input an array A of n numbers
2. Initialize j = 1 and repeat
through steps 4 If (j < n )
(a) Swap = A [j],
3. Initialize i = j – 1 Repeat the
step 3 if (Swap < A[i] and (i>= 0))
(a) A [i+1] = A [i]
(b) i = i-1
4. A [i +1] = Swap
5. Exit
 Cont..
• This is an in-place comparison-based sorting algorithm. Here, a sub-
list is maintained which is always sorted.
• For example, the lower part of an array is maintained to be sorted.
An element which is to be 'insert'ed in this sorted sub-list, has to find
its appropriate place and then it has to be inserted there.
• Hence the name, insertion sort. The array is searched sequentially
and unsorted items are moved and inserted into the sorted sub-list (in
the same array).
• This algorithm is not suitable for large data sets as its average and
worst case complexity are of Ο(n2), where n is the number of items.
• How Insertion Sort Works?
We take an unsorted array for our example.

Insertion sort compares the first two elements.

It finds that both 14 and 33 are already in ascending order. For now,
14 is in sorted sub-list.
 Cont.
• Insertion sort moves ahead and compares 33 with 27.

And finds that 33 is not in the correct position.

It swaps 33 with 27. It also checks with all the elements of sorted sub-
list. Here we see that the sorted sub-list has only one element 14, and
27 is greater than 14. Hence, the sorted sub-list remains sorted after
swapping.
By now we have 14 and 27 in the sorted sub-list. Next, it compares
33 with 10.

• These values are not in a sorted order.

So we swap them.

However, swapping makes 27 and 10 unsorted.

 Hence, we swap them too.

Again we find 14 and 10 in an unsorted order.

This process goes on until all the unsorted values are

covered in a sorted sub-list. Now we shall see some
programming aspects of insertion sort.
cont.
 C++ implementation
void insertion_sort(int list[]){
int temp;
for(int i=1;i<n;i++){
temp=list[i];
for(int j=i; j>0 && temp<list[j-1];j--)
{ // work backwards through the array finding where temp
should go
list[j]=list[j-1];
list[j-1]=temp;
}//end of inner loop
}//end of outer loop
}//end of insertion_sort
 Chapter 6: Recursion
Content to be discussed
1. Recursive definitions
2. Function calls and recursive
implementation
3. Tail recursion and Non tail recursion
4. Indirect recursion and direct
5. Nested and non nested recursive
6. Excessive recursive
 Recursive and recursive function
Recursive Definition – one that defines something in terms of itself
A recursive function is a function which either calls itself or is in a
potential cycle of function calls.
Int max()
{
:
Max();
}One can view this mathematically in a directed call graph.
void A()
{ A();
return;
}A() is a recursive function since it directly calls itself.
The second part of the definition refers to a cycle (or potential cycle if
we use conditional statements) which involves other functions.
CMSC 202 36
 Cont..
This can be viewed in the following three functions:
Int C()
{ A();
return;
}
Int B()
{
C(); return; }
Int A()
{ B();
return; }
 Iterative definition
Is a process where in a set of instructions or structures are repeated in a
sequence a specified number of times or until a condition is met.
When the first set of instructions is executed again, it is called an
iteration.
A program is called recursive when an entity calls itself. A program
is call iterative when there is a loop (or repetition).
Factorials of number can be iterative
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
int factorial (int n)
{
int i, result;
result = 1;
for (i = 1; i <= n; i++) {
result = result * i;
} return ( result );
}
38
 Recursive Factorial
factorials of number can be also recursive.
N! = 1 if N = 0
= N * (N-1)! Otherwise
int factorial ( int n)
{
if (n == 0)
return (1);
return (n * factorial(n - 1) );
}Types of Recursive Methods 1. Direct and Indirect Recursive
Methods
2. Nested and Non-Nested Recursive Methods

3. Tail and Non-Tail Recursive Methods

4. Tree Recursive Methods

39
5. Excessive Recursion
 1. Direct Recursion
If function explicitly calls itself it is called directly recursive. When the
method invokes itself it is direct. Example:
int testfunc( int num)
{if (num == 0)
return 0;
Else
return (testfunc(num-1));}
Here, the function ‘testfunc’ calls itself for all positive values of num.
eg2 Int foo (int x)
{
if ( x <= 0 ) return x;
return foo ( x – 1);
}
 2. Indirect Recursion:
This occurs when the function invokes other method which again
causes the original function to be called again.
If a method ‘X’ , calls method ‘Y’, which calls method ‘Z’ which again
leads to ‘X’ being invoked is called indirect recursive or mutually
recursive as well. Fun(){somecode ;--fun2();somecode}
fun2(){somecode;--fun();somecode;}

Example:
int testfunc1( int num)
{if (num == 0)
return 0;
Else return (testfunc2(num-1));
}
int testfunc2(int num2)
{ return testfunc1( num2-1); }
 Cont..
Write program to print numbers from 1 to 10when number is odd add 1
when number is even subtract 1.
Void odd()
Void even()
Int n=1
Void odd(){ void even()
If(n<=10) if(n<=10)
{ {
Cout<<n+1; cout<<n-1;
N++ n++;
Even(); odd();
}return ;} }return;}
Output=2,1,4,3,5,8,7.10,9
 3. Nested Recursive Methods
• Nested recursion occurs when a method is not only defined in
terms of itself; but it is also used as one of the parameters :
Example:
int fun(int n) fun(96) ----fun(107) fun(97)
{ : : :
If(n>100) False true false
Return n-10; =97
else
Else return fun(fun(n+11));it become(fun(fun(107)===fun(fun(108)
}
let fun(95)
95>100F so fun(95+11)
Fun(106)
106>100;true;
N-10
106-10=96……
 4. Tail and Non-Tail Recursive Methods
A method is tail recursive if in each of its recursive cases it executes
one recursive call and if there are no pending operations after that call.
Example 1:F(3) void f1(int n){
cout<<n <<" ";
Output 3,2,1 if(n > 0)
f1(n - 1);
}
Tail recursive method has the recursive call as the last statement in
the function. Non-Tail Recursive Methods
Example of non-tail recursive methods: if the recursive call is not last
thing done by function after returning back there is something left to
evaluate. After each recursive call there is a pending cout<<n <<" ";
Note the “pending operation” (namely the multiplication) to be performed on return
from each recursive call void f4(int n){
• Example 1: if f(3) if (n > 0)
f4(n - 1);
• Output 1,2,3 cout<<n <<" ";
}
Cont..
Reading assignment one and understand more
detail about
A. Tree Recursive Methods
B. Excessive Recursion(Fibonacci )
 Summarize
Bubble sort - is a simple and stable sorting algorithm which
can be used to sort a small number of items.
• Algorithm's best-case complexity is O(n).
• Algorithm's worst-case complexity is O(n2).
• Algorithm's average-case complexity is O(n2).
Insertion sort - is a simple and stable sorting algorithm that
is relatively efficient for small lists and mostly sorted lists.
• Algorithm's best-case complexity is O(n).
• Algorithm's worst-case complexity is O(n2).
• Algorithm's average-case complexity is O(n2).
 Cont..
Selection sort - is not a stable sorting algorithm, inefficient for large
lists . Algorithm's best-case complexity is O(n2).
• Algorithm's worst-case complexity is O(n2).
• Algorithm's average-case complexity is O(n2).
Time complexity linear search
In the best case, f (n) = O(1)
So in best case the order of time complexity for linear search is.
O(1)
worst case f (n) = (n)= O(n)
In the Average case, then f (n) = [(n/2].=O(n)
Binary search
Best case - O (1) comparisons
Worst case - O (log n) comparsions
Average case - O (log n) comparsions