Unit 4: Searching and Sorting

Algorithms

Lecturer: Shimirwa Aline Valerie

 Searching and Sorting Searching is used to find the location where
an element is available. There are two types of
Algorithms search techniques. They are:
1. Linear or sequential search
 There are basically two aspects of computer
programming. One is data organization also commonly 2. Binary search
called as data structures. Till now we have seen about Sorting allows an efficient arrangement of
data structures and the techniques and algorithms used elements within a given data structure. It is a
to access them. way in which the elements are organized
 The other part of computer programming involves systematically for some purpose. For example,
choosing the appropriate algorithm to solve the a dictionary in which words is arranged in
problem. alphabetical order and telephone director in
which the subscriber names are listed in
 Data structures and algorithms are linked each other. alphabetical order.
After developing programming techniques to represent
information, it is logical to proceed to manipulate it. There are many sorting techniques out of
This unit introduces this important aspect of problem which we will study the following.
solving.  Bubble sort
 Selection sort
 Quick sort and Heap sort
 Linear Search algorithm
 Linear Search is defined as a sequential search
algorithm that starts at one end and goes through each
element of a list until the desired element is found,
otherwise the search continues till the end of the data
set.
In Linear Search Algorithm:
 Every element is considered as a potential match for
the key and checked for the same.
 If any element is found equal to the key, the search is
successful and the index of that element is returned.
 If no element is found equal to the key, the search
yields “No match found”.
 How Does Linear Search  Step 2: Comparing key with next element
arr[1]. Since not equal, the iterator moves to
Algorithm Work? the next element as a potential match.
 Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90,
40} and key = 30
 Step 1: Start from the first element (index 0) and
compare key with each element (arr[i]). Comparing
key with first element arr[0]. Since not equal, the Step 3: Now when comparing arr[2] with
iterator moves to the next element as a potential match. key, the value matches. So the Linear Search
Algorithm will yield a successful message and
return the index of the element when key is
found (here 2).
 Implementation of Linear
Search Algorithm:
Pseudocode:
 Complexity Analysis of Advantages of Linear Search:
Linear search can be used irrespective of
Linear Search whether the array is sorted or not. It can be used
on arrays of any data type.
Time Complexity: Does not require any additional memory.
It is a well-suited algorithm for small datasets.
 Best Case: In the best case, the key might be present at
the first index. So the best case complexity is O(1) Drawbacks of Linear Search:
Linear search has a time complexity of O(n),
 Worst Case: In the worst case, the key might be
which in turn makes it slow for large datasets.
present at the last index i.e., opposite to the end from
Not suitable for large arrays.
which the search has started in the list. So the worst-
case complexity is O(n) where N is the size of the list.
 Average Case: O(n)
 Binary Search Algorithm In this binary search algorithm:
Divide the search space into two halves by finding
the middle index “mid”
 Binary Search is defined as a searching
algorithm used in a sorted array by repeatedly
dividing the search interval in half. The idea of
binary search is to reduce the time complexity to O(log
n). Compare the middle element of the search space
 To apply Binary Search algorithm The data structure with the key.
must be sorted. If the key is found at middle element, the process is
terminated.
If the key is not found at middle element, choose
which half will be used as the next search space.
• If the key is smaller than the middle element, then
the left side is used for next search.
• If the key is larger than the middle element, then
the right side is used for next search.
This process is continued until the key is found or
the total search space is exhausted.
How does Binary Search
work? Key is less than the current mid 56. The search
space moves to the left.
 To understand the working of binary search, consider
the following illustration:
 Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56,
72, 91}, and the target = 23.
 First Step: Calculate the mid and compare the mid Second Step: If the key matches the value of
element with the key. If the key is less than mid
the mid element, the element is found and stop
element, move to left and if it is greater than the mid
search.
then move search space to the right.
 Key (i.e., 23) is greater than current mid
element (i.e., 16). The search space moves
to the right.
 How to Implement Binary
Search?
 The Binary Search Algorithm can be implemented in
the following two ways
 Iterative Binary Search Algorithm
 Recursive Binary Search Algorithm

Iterative Binary Search Algorithm

 When implementing Binary Search Algorithm using
iterative approach, we use a while loop to continue the
process of comparing the key and splitting the search
space in two halves.
 How to Implement Binary
Search? cont..
Recursive Binary Search Algorithm
 When implementing Binary Search Algorithm using
recursive approach, we create a recursive function and
compare the mid of the search space with the key.
 And based on the result either return the index where
the key is found or call the recursive function for the
next search space.
 Complexity Analysis of Binary Drawbacks of Binary Search:
• The array should be sorted.
Search • Binary search requires that the data structure
being searched be stored in contiguous memory
 Time Complexity: locations.
• Best Case: O(1) • Binary search requires that the elements of the
• Average Case: O(log n) array be comparable, meaning that they must be
• Worst Case: O(log n) able to be ordered.

 Advantages of Binary Search: Applications of Binary Search:

 Binary search is faster than linear search, especially for  Binary search can be used as a building block for
large arrays. more complex algorithms used in machine
learning, such as algorithms for training neural
 More efficient than other searching algorithms with a
networks.
similar time complexity, such as interpolation search or
exponential search.  It can be used for searching a database.
 Binary search is well-suited for searching large datasets
that are stored in external memory, such as on a hard
drive or in the cloud.
 Bubble Sort is the simplest sorting
algorithm that works by repeatedly swapping
Bubble sort algorithm the adjacent elements If they are in the wrong
order. In this algorithm:
 What is Sorting algorithm?  traverse from left and compare adjacent
A Sorting Algorithm is used to rearrange a given array or elements and the higher one is placed at
list of elements according to a comparison operator on the right side.
elements. The comparison operator is used to decide the  In this way, the largest element is moved
new order of elements in the respective data structure. to the rightmost end at first.
 For Example: The below list of number is sorted in  This process is then continued to find the
increasing and decreasing order. second largest and place it and so on until
the data is sorted.
 2. Second Pass:

How does Bubble Sort

Work?
 Let us understand the working of bubble sort with the
help of the following illustration:
 Let take Input: arr[] = {6, 3, 0, 5}.
1. First pass:
3. Third Pass:
 Implementation of Bubble
Sort
 Here is the implementation of the bubble sort. It can be
optimized by stopping the algorithm if the inner loop
didn’t cause any swap.
 Time Complexity:
• Best Case: O(n)
• Average Case: O(n2)
• Worst Case: O(n2)
 When using insertion sort, the array is
virtually split into a sorted and an unsorted
Insertion Sort Algorithm part. Values from the unsorted part are picked
and placed at the correct position in the sorted
 Insertion sort is a simple sorting algorithm that works part.
similar to the way you sort playing cards in your
hands.
 We assume that the first card is already sorted then, we
select an unsorted card. If the unsorted card is greater
than the card in hand, it is placed on the right
otherwise, to the left. In the same way, other unsorted
cards are taken and put in their right place
 How does insertion sort Now, the first two elements are sorted. Take
the third element and compare it with the
work? elements on the left of it. Placed it just behind
the element smaller than it. If there is no
 Suppose we need to sort the following array. element smaller than it, then place it at the
beginning of the array.

 The first element in the array is assumed to be sorted.

Take the second element and store it separately in key.
Compare key with the first element. If the first
element is greater than key, then key is placed in front
of the first element.
 How does insertion sort
work? Cont..
 Similarly, place every unsorted element at its correct
position.
 Implementation of insertion
Sort
 Here is the implementation of the insertion sort.
 Time Complexity:
• Best Case: O(n)
• Average Case: O(n2)
• Worst Case: O(n2).

 When is the Insertion Sort algorithm used?

 Insertion sort is used when number of elements is
small. It can also be useful when the input array is
almost sorted, and only a few elements are
misplaced in a complete big array.
 Selection Sort Algorithm
Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the
smallest (or largest) element from the unsorted portion of the list and moving it to the sorted
portion of the list.
 How does Selection Sort
Algorithm work? Second Pass:
For the second position, where 25 is present,
 Lets consider the following array as an example: arr[]
again traverse the rest of the array in a
= {64, 25, 12, 22, 11}. sequential manner.
 First pass: After traversing, we found that 12 is the
 For the first position in the sorted array, the whole second lowest value in the array and it should
array is traversed from index 0 to 4 sequentially. The appear at the second place in the array, thus
first position where 64 is stored presently, after swap these values.
traversing whole array it is clear that 11 is the lowest
value.
 Thus, replace 64 with 11. After one iteration 11, which
happens to be the least value in the array, tends to
appear in the first position of the sorted list.
 How does Selection Sort Fourth pass:
Similarly, for fourth position traverse the rest
Algorithm work? Cont.. of the array and find the fourth least element in
Third Pass: the array

 Now, for third place, where 25 is present again traverse As 25 is the 4th lowest value hence, it will
the rest of the array and find the third least value place at the fourth position.
present in the array.
 While traversing, 22 came out to be the third least
value and it should appear at the third place in the
array, thus swap 22 with element present at third
position.
Fifth Pass:
At last the largest value present in the array
automatically get placed at the last position in
the array
The resulted array is the sorted array.
 Selection sort Implementation
 Time Complexity: The time complexity of Selection Sort
is O(n2) as there are two nested loops:
 One loop to select an element of Array one by one =
O(n)
 Another loop to compare that element with every other
Array element = O(n)
 Therefore overall complexity = O(n) * O(n) = O(n*n) =
O(n2)
 Advantages of Selection Sort Algorithm
 Simple and easy to understand.
 Works well with small datasets.
 Disadvantages of the Selection Sort Algorithm
 Selection sort has a time complexity of O(n^2) in the worst
and average case.
 Does not work well on large datasets.
 Does not preserve the relative order of items with equal keys
which means it is not stable.
 Quick Sort algorithm There are many different versions of quick Sort
that pick the pivot in different ways.
 Quick Sort is a sorting algorithm based on the Divide  Always pick the first element as a pivot.
and Conquer approach that picks an element as a pivot  Always pick the last element as a pivot.
and partitions the given array around the picked pivot
by placing the pivot in its correct position in the sorted  Pick a random element as a pivot.
array.  Pick the median as the pivot
 The key process in quick Sort is a partition(). The
target of partitions is to place the pivot (any element
can be chosen to be a pivot) at its correct position in
the sorted array and put all smaller elements to the left
of the pivot, and all greater elements to the right of the
pivot.
 Partition is done recursively on each side of the pivot
after the pivot is placed in its correct position and this
finally sorts the array.
 Quick Sort by picking the
first element as the Pivot. Pseudo code for partition() function
 The key function in quick sort is a partition. The target of
partitions is to put the pivot in its correct position if the
array is sorted and the smaller (or equal) to its left and
higher elements to its right and do all this in linear time.
Partition Algorithm:
 Use a recursive function (say quickSort) to initialize the
function.
 Call the partition function to partition the array and inside
the partition function do the following
 Take the first element as pivot and initialize and
iterator k = high.
 Iterate in a for loop from i = high to low+1:
• If arr[i] is greater than pivot then
swap arr[i] and arr[k] and decrement k.
 After the iteration is swap the pivot with arr[k].
 Return k-1 as the point of partition.
 Now recursively call quickSort for the left half and right
half of the partition index.
 Illustration of partition() Second Partition:
cont.. low = 0, high = 4, pivot = arr[low] = 2
Similarly initialize k = high = 4;
 Consider: arr[] = { 7, 6, 10, 5, 9, 2, 1, 15, 7 }
The correct position of 2 becomes index 1. And
 First Partition: low = 0, high = 8, pivot = arr[low] = 7 the left part is only one element and the right
Initialize index of right most element k = high = 8. part has {6, 5, 7}.
 Traverse from i = high to low:
 if arr[i] is greater than pivot:
 Swap arr[i] and arr[k].
 Decrement k;
 At the end swap arr[low] and arr[k]. On the other hand partition happens on the
 Now the correct position of pivot is index 5 segment [6, 8] i.e., the array {10, 9, 15}.
Here low = 6, high = 8, pivot = 10 and k = 8.
The correct position of 10 becomes index 7 and
the right and left part both has only one element.
 Illustration of partition() The total array becomes sorted in this way. Check
cont.. the below image for the recursion tree

Third partition:
 Here partition the segment {6, 5, 7}. The low = 2, high
= 4, pivot = 6 and k = 4.
 If the same process is applied, we get correct position
of 6 as index 3 and the left and the right part is having
only one element.
 Implementation of Quick
sort
Time Complexities
 Worst Case Complexity :O(n2)
It occurs when the pivot element picked is either the greatest
or the smallest element.
This condition leads to the case in which the pivot element
lies in an extreme end of the sorted array. One sub-array is
always empty and another sub-array contains n - 1 elements.
Thus, quicksort is called only on this sub-array.
However, the quicksort algorithm has better performance for
scattered pivots.
 Best Case Complexity: O(n log n)
It occurs when the pivot element is always the middle
element or near to the middle element.
 Average Case Complexity O(n log n)
It occurs when the above conditions do not occur.
 Merge Sort Working Rule
Merge Sort Algorithm The concept of Divide and Conquer involves
three steps:
 Merge sort is one of the most efficient sorting 1.Divide the problem into multiple subproblems.
algorithms. It works on the principle of Divide and 2.Solve the Sub Problems. The idea is to break down
Conquer based on the idea of breaking down a list the problem into atomic subproblems, where they
into several sub-lists until each sub list consists of a are actually solved.
single element and merging those sub list in a manner 3.Combine the solutions of the subproblems to find
that results into a sorted list. the solution of the actual problem.
 An array of Size ‘N’ is divided into two parts ‘N/2’ So, the merge sort working rule involves the
size of each. then those arrays are further divided till following steps:
we reach a single element. The base case here is 1.Divide the unsorted array into subarray, each
reaching one single element. containing a single element.
 When the base case is hit, we start merging the left part 2.Take adjacent pairs of two single-element array
and merge them to form an array of 2 elements.
and the right part and we get a sorted array at the end.
Merge sort repeatedly breaks down an array into 3.Repeat the process till a single sorted array is
obtained.
several subarrays until each subarray consists of a
single element and merging those subarrays in a
manner that results in a sorted array.
 How does Merge Sort Work?
 Let’s sort this array using merge sort:

Array = {70,50,30,10,20,40,60}
 We repeatedly break down the array in two parts, the
left part, and the right part. the division takes place
from the mid element. We divide until we reach a
single element and then we start combining them to
form a Sorted Array.
 Implementation of Merge
Sort
Time Complexity:
 The list of size N is divided into a max of Logn parts,
and the merging of all sub lists into a single list takes
O(N) time thus:
 Best Case Time Complexity: O(n*log n)
 Worst Case Time Complexity: O(n*log n)
 Average Time Complexity: O(n*log n)
 The time complexity of MergeSort is O(n*Log n) in all
the 3 cases (worst, average and best) as the mergesort
always divides the array into two halves and takes
linear time to merge two halves.
 Advantage and drawbacks of Drawbacks of Merge Sort
Merge Sort Space complexity: Merge sort requires
additional memory to store the merged sub-
Advantages of Merge Sort arrays during the sorting process.

 Stability: Merge sort is a stable sorting algorithm, Not in-place: Merge sort is not an in-place
which means it maintains the relative order of equal sorting algorithm, which means it requires
elements in the input array. additional memory to store the sorted data. This
can be a disadvantage in applications where
 Guaranteed worst-case performance: Merge sort has memory usage is a concern.
a worst-case time complexity of O(n log n), which Not always optimal for small datasets: For
means it performs well even on large datasets.
small datasets, Merge sort has a higher time
 Parallelizable: Merge sort is a naturally parallelizable complexity than some other sorting algorithms,
algorithm, which means it can be easily parallelized to such as insertion sort. This can result in slower
take advantage of multiple processors or threads. performance for very small datasets.
 Radix Sort Algorithm

 Radix Sort is a linear sorting algorithm that sorts

elements by processing them digit by digit. It is an
efficient sorting algorithm for integers or strings with
fixed-size keys.
 Rather than comparing elements directly, Radix Sort
distributes the elements into buckets based on each
digit’s value. By repeatedly sorting the elements by
their significant digits, from the least significant to the
most significant, Radix Sort achieves the final sorted
order.
 The key idea behind Radix Sort is to exploit the
concept of place value. It assumes that sorting numbers
digit by digit will eventually result in a fully sorted
list.
 How does Radix Sort
Algorithm work?
 To perform radix sort on the array:
 [170, 45, 75, 90, 802, 24, 2, 66], we follow these steps:
 Step 1: Find the largest element in the array, which is
802. It has three digits, so we will iterate three times,
once for each significant place.
 Step 2: Sort the elements based on the unit place digits
(X=0). We sort the digits at each significant place.
Sorting based on the unit place:
 Perform counting sort on the array based on the
unit place digits.
 The sorted array based on the unit place is [170,
90, 802, 2, 24, 45, 75, 66].
 How does Radix Sort
Algorithm work? cont..
 Step 3: Sort the elements based on the tens place
digits.
Sorting based on the tens place:
 Perform counting sort on the array based
on the tens place digits.
 The sorted array based on the tens place is
[802, 2, 24, 45, 66, 170, 75, 90].
 How does Radix Sort
Algorithm work? cont..
 Step 4: Sort the elements based on the hundreds place
digits.
Sorting based on the hundreds place:
 Perform counting sort on the array based on the
hundreds place digits.
 The sorted array based on the hundreds place is [2,
24, 45, 66, 75, 90, 170, 802].
 How does Radix Sort
Algorithm work? cont..
 Step 5: The array is now sorted in ascending order.
The final sorted array using radix sort is:
[2, 24, 45, 66, 75, 90, 170, 802].
 Implementation of Radix
Sort
 Time Complexity:
 Radix sort is a non-comparative integer sorting
algorithm that sorts data with integer keys by
grouping the keys by the individual digits which
share the same significant position and value. It has
a time complexity of O(d * (n + b)), where d is the
number of digits, n is the number of elements, and b
is the base of the number system being used.
 In practical implementations, radix sort is often
faster than other comparison-based sorting
algorithms, such as quicksort or merge sort, for large
datasets, especially when the keys have many digits.
However, its time complexity grows linearly with
the number of digits, and so it is not as efficient for
small datasets.