Unit - 3

Syllabus
❑ Analysis of Searching and Sorting

❑ Searching- Linear Search, Binary Search

❑ Sorting-Bubble Sort, Selection Sort, Insertion Sort

Searching
Searching
There are several searching algorithm available like: Linear search, Binary search, BST search,
AVL tree search operation, Hashing etc. Out of these searching algorithm the two basic and
popular algorithm in searching are:
I. Linear Search
II. Binary Search

Linear Search:
This Method searches for an element by visiting all the elements sequemtially until the key
element to be searches is found or the array traversal finishes.
The given array can be sorted or unsorted.
Worst-case time-complexity is O(n)
Searching
Algorithm : Linear Search
int linearSearch(int *A, int size, int key)
{
for(int i=0; i<size; i++)
{
if(A[i])==key)
return i;
}
return -1;
}
Searching
Linear Search: Analysis
Best case Time complexity : O(1)
Average case Time complexity : O(n)
Worst case Time complexity : O(n)

The time complexity of linear search is O(n) because every element in the array is compared
only once.
Searching
Binary Search:
This Method searches for an element by breaking the search space into half each time it
finds the wrong element. This method can only be applicable to a sorted array. The search
continue towards either side of the mid, based on whether the element to be searched is
lesser or greater than the mid element of the current search space.
Worst-case time-complexity is O(logn).
Searching
Algorithm : Binary Search
int binarySearch(int *A, int size, int key)
{
int low, mid, high;
low=0; high=(size-1)
//Keep searching until low<=high
while(low<=high)
{
mid=(low+high)/2;
if(A[mid] == key)
return mid;
else if (A[mid] < key)
low = mid+1;
else
high = mid-1;
}
return -1;
}
Searching
Binary Search : Analysis
In the first pass, number of comparison require is : n/2
In the first pass, number of comparison require is : n/22
In the first pass, number of comparison require is : n/23
…
…
…
We go till, number of comparison will be : 1
Therefore, we have to find the value of k for which n/2𝑘 = 1

K= logn

Hence, Time complexity of Binary Search is O(logn)

In Best case it can be O(1), if the key lies in the middle.
Sorting
Sorting
Introduction:
o Sorting of data means arranging the given set of data in some
specified order.

o The primary benefit of Sorting data is in Searching.

o Sorting methods can be divided into two parts – Internal Sorting and
External Sorting.
• In internal sorting- the data that is going to be sorted will be in
the main memory.
• In external sorting- data will be on auxiliary storage, like tape,
floppy disk etc.

o No sorting technique is best, it all depends on the type of data,

situation and complexity.
Sorting
Efficiency Parameter of a sorting technique:
o To know which sorting technique will be best for a particular problem,
we will go for some parameters for getting this knowledge.

o First parameter is execution time, second is space and third is coding

time.

o Efficiency criteria can be known by mathematical analysis that it has

of O(n), O(nlogn) or O(𝑛2 ). Still now, there is no sorting technique
which is of O(n). All sorting technique are between O(nlogn) to O(𝑛2 ).
Sorting
Characteristics of a sorting technique:

o Recursive vs Iterative sorting algorithm.

o Stable vs Unstable sorting algorithm..

o Adaptive vs Non-adaptive sorting algorithm..

 Sorting
Recursive algorithm:

o Recursion is a method of solving a problem by breaking it down into smaller sub-

problems.
o Each sub-problem is solved in the same way as the original problem.
o A recursive function calls itself, creating a call stack.
o The final answer is returned when the stack is popped completely.

Iterative algorithm:

An iterative algorithm executes steps in iterations. It aims to find successive

approximation in sequence to reach a solution. They are most commonly used in linear
programs where large numbers of variables are involved.
Sorting
Recursive algorithm: Advantage

o Recursion can make code more straightforward and concise

o Recursion can reduce time complexity in some cases
o Recursion is very useful to solve complex problems.

Recursive algorithm: Disadvantage

o Recursive function can be slower than non-recursive function.

o Recursive function takes more space than iterative program.
o Recursive calls can be complex to understand and debug.
o Recursive function needs a base case to avoid infinite recursion.
Sorting
Stable Sorting algorithm:
A stable sorting algorithm preserves the relative order of elements with equal values in
the sorted output. This is useful when the order of equal elements is important, such as
when performing multiple rounds of sorting.
Examples of stable sorting algorithms: Insertion sort, Merge sort, Bubble sort

Examples of unstable sorting algorithms: Quick sort, Selection sort, Heap sort:
Sorting
Adaptive Sorting algorithm:

In adaptive sorting algorithm, if the data is already sorted, the algorithm will not
reorder the elements. As a result, it reduces the number of iterations and improves
execution speed.
Example of Adaptive Sorting algorithms: Insertion Sort, Quick sort, Bubble Sort
In the case of adaptive sorting algorithms, if the array is already sorted it takes linear
time to perform sorting i.e., O(N) time.
Sorting
Adaptive Sorting algorithm:
Non-Adaptive Sorting Algorithms:
The sorting algorithms in which the order of elements of the data doesn’t affect the
time complexity of the sorting algorithms are known as non-adaptive sorting
algorithms.
In a non-adaptive algorithm, the time complexity remains the same for any order of
the array. A non-adaptive sorting algorithm tries to force all the items into sorted
order.
Example of Non-adaptive sorting algorithms: Selection sort, Merge sort, Heap sort
Sorting
Sorting algorithm: Advantages
• Efficiency: Sorting algorithms help in arranging data in a specific order, making it
easier and faster to search, retrieve, and analyze information.
• Improved Performance: By organizing data in a sorted manner, algorithms can
perform operations more efficiently, leading to improved performance in various
applications.
• Simplified data analysis: Sorting makes it easier to identify patterns and trends in
data.
• Reduced memory consumption: Sorting can help reduce memory usage by
eliminating duplicate elements.
• Improved data visualization: Sorted data can be visualized more effectively in charts
and graphs.
Sorting
Sorting algorithm: Disadvantages
• Insertion: If we wish to keep data sorted, then insertion operation becomes costly as
we have to maintain sorted order. If we do not have to maintain sorted order, we
can simply insert at the end.
• Algorithm selection: Choosing the most appropriate sorting algorithm for a given
dataset can be challenging.
• For a lot of problems hashing works better than sorting, for example, finding
distinct elements, finding a pair with given sum.
Sorting
Sorting algorithm:
There are several sorting algorithms:

❖ Bubble sort ❖ Merge sort

❖ Insertion sort ❖ Bucket sort
❖ Selection sort ❖ Radix sort
❖ Heap sort ❖ Count sort
❖ Quick sort ❖ Shell sort
Sorting
Sorting algorithm: Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the
adjacent elements if they are in the wrong order. This algorithm is not suitable for large
data sets as its average and worst-case time complexity are quite high [O(n2)]

o We sort the array using multiple passes. After the first pass, the maximum element
goes to end (its correct position). Same way, after second pass, the second largest
element goes to second last position and so on.

o In a pass, we consider only the remaining elements and compare all adjacent and
swap if larger element is before a smaller element. If we keep doing this, we get the
largest (among the remaining elements) at its correct position.
Sorting
Sorting algorithm: Bubble Sort Example:

Void bubbleSort(int *A, int n) 7 11 9 2 17 4

{
int temp;
for(int j = 0 ; i < (n-1) ; i++)
{
for(int j = 0 ; j < (n-i-1) ; j++)
{
if(A[j] > A[j+1])
swap(A[j] , A[j+1])
}
}
}
Sorting
Bubble Sort : Analysis
Number of comparison required in the first pass: (n-1)
Number of comparison required in the first pass: (n-2)
Number of comparison required in the first pass: (n-3)
…
…
…
Number of comparison required in the final pass: 1
_______________________________________________________
Therefore, Total number of comparison required to sort the entire array =
(n-1)+(n-2)+(n-3)+…………+3+2+1
𝑛(𝑛−1)
= = O(𝑛2 )
2
Best case Time complexity: O(1) Non-recursive
Average case Time complexity: O(𝒏𝟐 ) Not adaptive
Worst case Time complexity: O(𝒏𝟐 ) Stable
Sorting Void selectionSort(int *A, int n)
{
Sorting algorithm: Selection Sort
for(i=0 ; i < n-1 ; i++)
{
smallest = i;
for(k=i+1 ; k<n ; k++)
{
if(A[smallest] > A[k])
smallest = k
}
if(i != smallest)
{
swap(A[i], A[smallest])
}
}
}
Sorting
Sorting algorithm: Selection Sort

Not Stable
Not Adaptive
Time Complexity O(𝒏𝟐 )
Sorting Void insertionSort(int *A, int n)
Sorting algorithm: Insertion Sort {
int key, j;
for(i=1; i<=n-1; i++)
{
key = A[i]
j=j-1
while( A[j] > key and j>=0)
{
A[ j+1 ] = A[ j ]
j = j-1
}
A[ j+1 ] = key
}
}
Sorting
Sorting algorithm: Insertion Sort

Stable
Adaptive
Time Complexity O(𝒏𝟐 )
 Learn Implement

THANK YOU !
Adapt Explore

Think