ALGORITHMS AND COMPLEXITY ANALYSIS
CSC 315
NOTE 3: SEARCHING AND SORTING ALGORITHMS
1.0 Introduction
Sorting and searching are two of the most frequently needed algorithms in program design.
Common algorithms have evolved to take account of this need. Since computers were
created, users have devised programs, many of which have needed to do the same thing. As a
result, common algorithms have evolved and been adopted in many programs.
Two algorithms often used are searches and sorts:
searches allow a set of data to be examined and for a specific item to be found
sorts allow a data set to be sorted into order
Methods of searching include:
linear search
binary search
Methods of sorting include:
bubble sort
merge sort
insertion sort
quicksort
radix sort
selection sort
2.0 Bubble Sort
Bubble Sort, also known as Exchange Sort, is a simple sorting algorithm. It works by
repeatedly stepping throughout the list to be sorted, comparing two items at a time and
swapping them if they are in the wrong order. The pass through the list is duplicated until no
swaps are desired, which means the list is sorted.
This is the easiest method among all sorting algorithms
Algorithm
We assume list is an array of n elements. We further assume that swap function swaps the
values of the given array elements
1
begin BubbleSort(list)
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort
2.1 How Bubble Sort Works
1. The bubble sort starts with the very first index and makes it a bubble element. Then it
compares the bubble element, which is currently our first index element, with the next element.
If the bubble element is greater and the second element is smaller, then both of them will swap.
After swapping, the second element will become the bubble element. Now we will compare
the second element with the third as we did in the earlier step and swap them if required. The
same process is followed until the last element.
2. We will follow the same process for the rest of the iterations. After each of the iteration, we
will notice that the largest element present in the unsorted array has reached the last index.
For each iteration, the bubble sort will compare up to the last unsorted element.
Once all the elements get sorted in the ascending order, the algorithm will get terminated.
Consider the following example of an unsorted array that we will sort with the help of the
Bubble Sort algorithm:
Initially,
16 36 24 37 15
Pass 1:
Compare a0 and a1
16 30 24 37 15
As a0 < a1, so the array will remain as it is
Compare a1 and a2
16 36 24 37 15
Now a1 > a2, so we will swap both of them.
16 24 36 37 15
Compare a2 and a3
16 24 36 37 15
As a2 < a3 so the array will remain as it is.
2
Compare a3 and a4
16 24 36 37 15
Here a3 > a4, so we will again swap both of them.
16 24 36 15 37
Pass 2:
Compare a0 and a1
16 24 36 15 37
As a0 < a1 so the array will remain as it is.
Compare a1 and a2
16 24 36 15 37
Here, a1 < a2, so the array will remain as it is.
Compare a2 and a3
16 24 36 15 37
In this case, a2 > a3, so both of them will get swapped.
16 24 15 36 37
Pass 3:
Compare a0 and a1
16 24 15 36 37
As a0 < a1, so, the array will remain as it is.
Compare a1 and a2
16 24 15 36 37
Now a1 > a2, so, both of them will get swapped.
16 15 24 36 37
Pass 4:
Compare a0 and a1
16 15 24 36 37
Here, a0 > a1, so we will swap both of them.
15 16 24 36 37
Hence the array is sorted as no more swapping is required.
2.2.1 Complexity Analysis of Bubble Sort
Input: Given n input elements.
Output: Number of steps incurred to sort a list.
Logic: If we are given n elements, then in the first pass, it will do n-1 comparisons; in the second
pass, it will do n-2; in the third pass, it will do n-3 and so on. Thus, the total number of
comparisons can be found by;
3
Therefore, the bubble sort algorithm encompasses a time complexity of O(n2) and a space
complexity of O(1) because it necessitates some extra memory space for temp variable for
swapping.
2.2.2 Time Complexities:
Best Case Complexity: The bubble sort algorithm has a best case time complexity of O(n) for
the already sorted array.
Average Case Complexity: The average-case time complexity for the bubble sort algorithm is
O(n2), which happens when 2 or more elements are in jumbled, i.e., neither in the ascending
order nor in the descending order.
Worst Case Complexity: The worst-case time complexity is also O(n2), which occurs when we
sort the descending order of an array into the ascending order.
2.2.3 Advantages of Bubble Sort
1. Easily understandable.
2. Does not necessitate any extra memory.
3. The code can be written easily for this algorithm.
4. Minimal space requirement than that of other sorting algorithms.
2.2.4 Disadvantages of Bubble Sort
1. It does not work well when we have large unsorted lists, and it necessitates more resources
that end up taking so much of time.
2. It is only meant for academic purposes, not for practical implementations.
3. It involves the n2 order of steps to sort an algorithm.
2.3 Selection Sort Algorithm
The selection sort enhances the bubble sort by making only a single swap for each pass
through the rundown. In order to do this, a selection sort searches for the biggest value as it
makes a pass and, after finishing the pass, places it in the best possible area. Similarly, as
with a bubble sort, after the first pass, the biggest item is in the right place. After the second
pass, the following biggest is set up. This procedure proceeds and requires n-1 goes to sort n
item since the last item must be set up after the (n-1)th pass.
4
2.3.1 Algorithm: Selection Sort (A)
selectionSort(array, size)
repeat (size - 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
if element < currentMinimum
set element as new minimum
swap minimum with first unsorted position
end selectionSort
2.3.2 How Selection Sort works
1. In the selection sort, first of all, we set the initial element as a minimum.
2. Now we will compare the minimum with the second element. If the second element turns
out to be smaller than the minimum, we will swap them, followed by assigning to a
minimum to the third element.
3. Else if the second element is greater than the minimum, which is our first element, then we
will do nothing and move on to the third element and then compare it with the minimum.
We will repeat this process until we reach the last element.
4. After the completion of each iteration, we will notice that our minimum has reached the
start of the unsorted list.
5. For each iteration, we will start the indexing from the first element of the unsorted list. We
will repeat the Steps from 1 to 4 until the list gets sorted or all the elements get correctly
positioned.
6. Consider the following example of an unsorted array that we will sort with the help of the
Selection Sort algorithm.
A[ ] = (7, 4, 3, 6, 5).
A[ ] =
5
6
7
2.3.3 Complexity Analysis of Selection Sort
Input: Given n input elements.
Output: Number of steps incurred to sort a list.
Logic: If we are given n elements, then in the first pass, it will do n-1 comparisons; in the
second pass, it will do n-2; in the third pass, it will do n-3 and so on. Thus, the total number of
comparisons can be found by;
Therefore, the selection sort algorithm encompasses a time complexity of O(n2) and a space
complexity of O(1) because it necessitates some extra memory space for temp variable for
swapping.
2.3.4 Time Complexities:
Best Case Complexity: The selection sort algorithm has a best case time complexity of
O(n2) for the already sorted array.
Average Case Complexity: The average-case time complexity for the selection sort
algorithm is O(n2), in which the existing elements are in jumbled ordered, i.e., neither in
the ascending order nor in the descending order.
Worst Case Complexity: The worst-case time complexity is also O(n2), which occurs
when we sort the descending order of an array into the ascending order.
2.3.5 Advantages of Selection Sort
It is an in-place algorithm. It does not require a lot of space for sorting. Only one extra
space is required for holding the temporal variable.
It performs well on items that have already been sorted
2.3.6 Disadvantage of selection sort
As the input size increases, the performance of selection sort decreases.
3.0 Conclusion
The sorting problem enables us to find better algorithms that would help arrange the numbers in
a list or sequence in any order. Ascending order is when it is arranged from Smallest to Biggest
while Descending order is when the list is arranged from biggest item to the smallest item. We
looked at the case of the bubble sort and the Selection sort algorithms which are well suited for
sorting a small-sized list efficiently.
