ALGORITHM
In this comprehensive guide, we will explore fundamental algorithms and data structures essential for computer
science students progressing from secondary school to A-level studies. By the end of this chapter, you should be
able to:
Understand and implement linear and binary search algorithms.
Comprehend the conditions necessary for the effective use of binary search.
Analyze how the performance of binary search varies with the number of data items.
Understand insertion sort and bubble sort methods.
Recognize that the performance of a sorting routine may depend on the initial order of the data and the
number of data items.
Understand and use Abstract Data Types (ADTs).
Implement ADTs from other ADTs.
Describe and implement the following ADTs: stack, queue, linked list, dictionary, binary tree.
Write algorithms to:
o Implement an insertion sort.
o Implement a bubble sort.
o Find an item in each of the following: linked list, binary tree.
o Insert an item into each of the following: stack, queue, linked list, binary tree.
o Delete an item from each of the following: stack, queue, linked list.
Understand that a graph is an example of an ADT.
Describe the key features of a graph and justify its use for a given situation.
Understand that different algorithms performing the same task can be compared using criteria such as
time taken to complete the task and memory used.
Understand Big O notation for time and space complexity.
1. Search Algorithms
1.1 Linear Search
Definition: Linear search, also known as sequential search, involves checking each element in a list one by one
until the desired element is found or the list ends.
Algorithm:
1. Start from the first element of the list.
2. Compare the current element with the target value.
3. If they match, return the index of the current element.
4. If not, move to the next element.
5. Repeat steps 2-4 until the element is found or the list ends.
Implementation in Python:
python
CopyEdit
def linear_search(arr, target):
for index, value in enumerate(arr):
if value == target:
return index
return -1
Time Complexity: O(n), where n is the number of elements in the list. In the worst case, the algorithm checks
every element.
Space Complexity: O(1), as it uses a constant amount of extra space.
1.2 Binary Search
Definition: Binary search is an efficient algorithm for finding an item from a sorted list by repeatedly dividing
the search interval in half.
Conditions for Use:
The list must be sorted.
Random access to elements is possible.
Algorithm:
1. Initialize two pointers, low at the start and high at the end of the list.
2. While low is less than or equal to high:
o Calculate the middle index: mid = (low + high) // 2.
o If the middle element matches the target, return mid.
o If the target is less than the middle element, adjust high to mid - 1.
o If the target is greater, adjust low to mid + 1.
3. If the element is not found, return -1.
Implementation in Python:
python
CopyEdit
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Time Complexity: O(log n), as the search space is halved with each step.
Space Complexity: O(1) for the iterative approach; O(log n) for the recursive approach due to the call stack.
Performance Analysis: Binary search is significantly faster than linear search for large datasets, but it requires
the data to be sorted. In contrast, linear search does not require sorted data but is less efficient for large lists.
geeksforgeeks.org
2. Sorting Algorithms
2.1 Insertion Sort
Definition: Insertion sort builds the final sorted array one item at a time, with the assumption that the initial
portion of the array is already sorted.
Algorithm:
1. Start with the second element (index 1).
2. Compare it with elements before it and insert it into its correct position.
3. Repeat for all elements until the array is sorted.
Implementation in Python:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1]
::contentReference[oaicite:1]{index=1}
In computer science, sorting algorithms are fundamental tools used to arrange data in a specific order, typically
ascending or descending. Two of the most basic sorting algorithms are Insertion Sort and Bubble Sort.
Understanding these algorithms provides a foundation for more advanced topics in computer science.
Insertion Sort
Insertion Sort is a simple and intuitive algorithm that builds the final sorted array one item at a time. It's
analogous to the way you might sort playing cards in your hands: you take one card and insert it into its correct
position relative to the already sorted cards.
How Insertion Sort Works:
1. Start with the first element: Assume the first element is already sorted.
2. Pick the next element: Take the next element from the unsorted portion.
3. Compare and shift: Compare this element with the elements in the sorted portion, shifting all larger
elements one position to the right to make space.
4. Insert: Insert the element into its correct position.
5. Repeat: Repeat steps 2-4 until all elements are sorted.
Example:
Consider the array: [5, 2, 4, 6, 1, 3]
Initial array: [5, 2, 4, 6, 1, 3]
First pass: 2 is compared with 5 and inserted before it. Array becomes: [2, 5, 4, 6, 1, 3]
Second pass: 4 is placed between 2 and 5. Array becomes: [2, 4, 5, 6, 1, 3]
Third pass: 6 remains in place as it's greater than 5.
Fourth pass: 1 is moved to the front. Array becomes: [1, 2, 4, 5, 6, 3]
Fifth pass: 3 is placed between 2 and 4. Final sorted array: [1, 2, 3, 4, 5, 6]
Algorithm Implementation:
Here's a simple implementation of Insertion Sort in Python:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
Performance:
Time Complexity:
o Best Case: O(n) – occurs when the array is already sorted.
o Average and Worst Case: O(n²) – happens when the array is in reverse order or randomly
ordered.
Space Complexity: O(1) – requires a constant amount of additional memory space.
Insertion Sort is efficient for small datasets or nearly sorted arrays but becomes less efficient as the size of the
dataset increases.
Advantages of Insertion Sort:
Simple and easy to implement.
Stable sorting algorithm.
Efficient for small lists and nearly sorted lists.
Space-efficient as it is an in-place algorithm.
Adoptive. the number of inversions is directly proportional to number of swaps. For example, no swapping
happens for a sorted array and it takes O(n) time only.
Disadvantages of Insertion Sort:
Inefficient for large lists.
Not as efficient as other sorting algorithms (e.g., merge sort, quick sort) for most cases.
Applications of Insertion Sort:
Insertion sort is commonly used in situations where:
The list is small or nearly sorted.
Simplicity and stability are important.
Used as a subroutine in Bucket Sort
Can be useful when array is already almost sorted (very few inversions)
Since Insertion sort is suitable for small sized arrays, it is used in Hybrid Sorting algorithms along with other
efficient algorithms like Quick Sort and Merge Sort. When the subarray size becomes small, we switch to
insertion sort in these recursive algorithms. For example IntroSort and TimSort use insertions sort.
geeksforgeeks.org
Bubble Sort
Bubble Sort is another straightforward sorting algorithm that repeatedly steps through the list, compares
adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted.
How Bubble Sort Works:
1. Start at the beginning: Compare the first two elements.
2. Swap if necessary: If the first element is greater than the second, swap them.
3. Move to the next pair: Continue comparing each pair of adjacent elements, swapping as needed, until
the end of the list is reached.
4. Repeat: Repeat the process for the entire list until no swaps are needed, indicating that the list is sorted.
Example:
Consider the array: [5, 1, 4, 2, 8]
First pass:
o Compare 5 and 1; swap. Array becomes: [1, 5, 4, 2, 8]
o Compare 5 and 4; swap. Array becomes: [1, 4, 5, 2, 8]
o Compare 5 and 2; swap. Array becomes: [1, 4, 2, 5, 8]
o Compare 5 and 8; no swap.
Second pass:
o Compare 1 and 4; no swap.
o Compare 4 and 2; swap. Array becomes: [1, 2, 4, 5, 8]
o Compare 4 and 5; no swap.
o Compare 5 and 8; no swap.
Third pass: No swaps needed; array is sorted.
Algorithm Implementation:
Here's a simple implementation of Bubble Sort in Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
Performance:
Time Complexity:
o Best Case: O(n) – occurs when the array is already sorted.
o Average and Worst Case: O(n²) – happens when the
Advantages of Bubble Sort:
Bubble sort is easy to understand and implement.
It does not require any additional memory space.
It is a stable sorting algorithm, meaning that elements with the same key value maintain their relative order in
the sorted output.
Disadvantages of Bubble Sort:
Bubble sort has a time complexity of O(n2) which makes it very slow for large data sets.
Bubble sort has almost no or limited real world applications. It is mostly used in academics to teach different
ways of sorting.
