>>> Searching and Sorting Algorithms

Searching and Sorting Algorithms

Searching and sorting algorithms are fundamental topics in computer science. They are widely used in various
applications, such as databases, web search engines, cryptography, artificial intelligence, and more. In this
lecture, we will learn about some of the most common searching and sorting algorithms, their properties, and
how to implement them in code.

Section 1: Searching algorithms

Searching algorithms are designed to find an element or a set of elements that satisfy some criteria from a
collection of data. For example, we may want to search for a name in a phone book, a word in a document, or a
product in an online store. There are different types of searching algorithms; in our syllabus, you need to know:

• Linear search
• Binary search
• Hash table search

You will also need to know how to implement a binary search tree.

In this chapter, we will only focus on linear and binary search.

1.1 Linear Search Time complexity: O(n)

A linear search is the simplest approach to search for an element in an array. It examines each element
sequentially from the beginning until it finds a match.

The search is terminated once the target element is located, or it reaches the end of the array.

Steps:

1. Define target value you want to search for in the array.

2. Iterate through the array from the starting index to the end. For each element in the array, compare it
with the target value.
3. If current element = target, return the current index and exit the loop.
4. If current element ≠ target, continue iterating.
5. If the end of the array is reached and a match is still not found, return a signal (e.g. -1), indicating that
the target value is not present in the array.

ASRJC H2 Computing 1
 >>> Searching and Sorting Algorithms
Python Implementation of Linear Search

def lin_search(arr, target):

for i in range(len(arr)):
if arr[i] == target:
return i
return -1

# Example
arr = [5, 9, 0, 1, 3, 6, 7]
result = lin_search(arr, 3)
if result == -1:
print("Target not found")
else:
print("Target is at index", result)

This algorithm is easy to implement and is appropriate if:

• the list contains few elements and

• we are searching for a single element in an unordered array.

1.2 Binary Search Time complexity: O(log n)

This is a fast search algorithm, which works on the principle of divide and conquer.

For this algorithm to work, the data collection needs to be in sorted form.

Binary search looks for a target item by comparing the middle element of the array. If a match occurs, the index
is returned. If the middle element is greater, then search in the sub-array to the left of the middle element.
Otherwise, search in the sub-array to the right.

Steps:

1. Define the target value (target) you want to search for. Also, initialise variables for leftmost (left) and
rightmost (right) indices of the search range.
Set left and right to the indices of the first and last elements in the array.
2. Check that left ≤ right. If not, target is not present in array and search is unsuccessful.

3. Calculate the midpoint index, mid = (left + right) DIV 2

4. Compare element at midpoint index with target.
5. If the midpoint element matches target, return midpoint index.
6. If midpoint element > target, update right to mid – 1 to search in the left half of the array.
If midpoint element < target, update left to mid + 1 to search in the right half of the array.
7. Repeat steps 2 – 6 until target is found or search range becomes invalid, i.e. left > right.
8. If target is not found, return a signal (-1) indicating an unsuccessful search.
ASRJC H2 Computing 2
 >>> Searching and Sorting Algorithms

Python Implementation of Binary Search

def bin_search(arr, target):

left = 0
right = len(arr) - 1

while left <= right: # check if search range is valid

mid = (left + right) // 2
mid_element = arr[mid]

if mid_element == target:
return mid # target found
elif mid_element < target:
left = mid + 1 # search right
else:
right = mid - 1 # search left

return -1 # target not found

# Example
arr = [1, 3, 5, 7, 9, 11, 13, 15] # must be a sorted array!
target = 3
result = bin_search(arr, target)
if result == -1:
print("Target not found")
else:
print("Target is at index", result)

Using an example: target = 10, arr = [1, 3, 5, 7, 9, 11, 13, 15]

left = 0, right = 7 arr[mid] = 7, target = 10
mid = (0 + 7) // 2 = 3
Since arr[mid] < target,
search in the right half of the array.
left = mid + 1 = 4
left = 4, right = 7 arr[mid] = 11, target = 10
mid = (4 + 7) // 2 = 5
Since arr[mid] > target,
search in the left half of the array.
right = mid – 1 = 4
left = 4, right = 4 arr[mid] = 9, target = 10
mid = (4 + 4) // 2 = 4
Since arr[mid] < target,
search in the right half of the array.
left = mid + 1 = 5
left = 5, right = 4 (invalid range) return -1, target not found

ASRJC H2 Computing 3
 >>> Searching and Sorting Algorithms
Binary search is a very efficient algorithm, but it requires the input array to be sorted.

For small datasets, difference in efficiencies between linear and binary search may not be significant. However,
if you need to perform multiple searches on the same data and if the dataset is large, the upfront cost of
sorting the data first and then applying binary search may be outweighed by the efficiency gained in
subsequent searches.

Section 2: Sorting algorithms

Sorting algorithms are fundamental in computer science. There are many applications –

• Searching: If the list is sorted, searching operations can be much faster.

• Selection: Finding the max/min/median is efficient if values are in sorted order.
• Analysing distribution: Sorting is often a preliminary step in generating histograms. It also helps us to
identify the distribution of values.
• Identifying duplicates: After sorting, adjacent elements can be compared to identify duplicates.

Here, we will be learning just 4 out of the many sorting algorithms.

2.1 Insertion Sort Time complexity: O(n2)

Insertion sort is a simple and efficient sorting algorithm.

It builds the sorted array one element at a time by repeatedly taking the next element and inserting it into its
correct position in the already sorted portion of the array.

Steps:

1. Assume the first element in the array is already sorted. Start from the second element.
2. Compare and insert:
- Compare current element with elements before it, from right to left.
- Keep shifting elements to the right until correct position for the current element is found.
- Insert current element into its correct position in the sorted part of the array.
3. Repeat step 2 for each element until the entire array is sorted.

ASRJC H2 Computing 4
 >>> Searching and Sorting Algorithms

Python Implementation of Insertion Sort

def insertion_sort(arr):
# loop from the second element until the last element
for i in range(1, len(arr)):
key_element = arr[i] # element to be inserted
j = i – 1 # initialise variable to be used to identify the correct position

while j >= 0 and arr[j] > key_element:

arr[j + 1] = arr[j] # shift the element to the right
j -= 1 # continue checking next element on the left

# once done shifting elements, insert key element in its correct position
arr[j + 1] = key_element

# Example
arr = [5, 9, 1, 7, 2, 12, 6, 3]
insertion_sort(arr)
print(arr)

Characteristics of insertion sort

Efficiency and simplicity
- It is one of the simplest algorithms with a simple implementation
- It performs reasonably well for small datasets.

In-place sorting
- It sorts the array by modifying it directly. Therefore, it does not require additional memory allocation
proportional to the input array size.

Stable sorting
- It preserves the relative order of equal elements in the sorted array.

Adaptive
- It performs well on nearly sorted or partially sorted arrays. Therefore it is useful in situations where
elements are continuously added to a sorted list and need to be maintained in a sorted order.

The worst case for insertion sort occurs when the array is initially in reverse order.

ASRJC H2 Computing 5
 >>> Searching and Sorting Algorithms
2.2 Bubble Sort (Non-Optimised) Time complexity: O(n2)
Bubble sort is another simple and intuitive algorithm. It repeatedly steps through the array, comparing adjacent
elements and swaps them if they are in the wrong order.

Steps:

1. Begin with the first element of the array.

2. Compare the current element with the next element in the array. If the current element is greater, swap
the two elements.
3. Move to the next pair of elements and repeat step 2.
4. Continue the process until the end of the unsorted array is reached. At the end of this pass, the largest
element has “bubbled up” to the end.
5. Repeat steps 2 – 4 for the remaining unsorted elements.

The following is an example. Notice that an array with length 5 requires a maximum of 4 passes.

Python Implementation of Bubble Sort (Non-Optimised Version)

def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # requires (n - 1) passes
for j in range(n - i - 1): # last i elements are already in place
if arr[j] > arr[j + 1]: # swap if the elements are not in order
arr[j], arr[j + 1] = arr[j + 1], arr[j]

# Example
arr = [5, 9, 1, 7, 2]
bubble_sort(arr)
print(arr)

Thinking point: What is one small change you can make to the code to produce an output in reversed order?

ASRJC H2 Computing 6
 >>> Searching and Sorting Algorithms
2.2.1 Bubble Sort (Optimised)
Let’s apply the algorithm to [21, 5, 3, 10, 8, 7, 20, 19, 15]. By adding a print statement in the outer for loop, we
can see the output after each pass:
Pass 1: [5, 3, 10, 8, 7, 20, 19, 15, 21]
Pass 2: [3, 5, 8, 7, 10, 19, 15, 20, 21]
Pass 3: [3, 5, 7, 8, 10, 15, 19, 20, 21]
Pass 4: [3, 5, 7, 8, 10, 15, 19, 20, 21]
Pass 5: [3, 5, 7, 8, 10, 15, 19, 20, 21]
Pass 6: [3, 5, 7, 8, 10, 15, 19, 20, 21]
Pass 7: [3, 5, 7, 8, 10, 15, 19, 20, 21]
Pass 8: [3, 5, 7, 8, 10, 15, 19, 20, 21]

Notice that several of the passes appear redundant.

In our 4th pass, no swaps are made. This means that our array is already sorted by then!

Therefore, we may want to keep track of whether any swaps are made. If no swaps are made in a pass, we have
achieved a sorted array and so we can exit our loop early.

Python Implementation of Bubble Sort (Optimised Version)

def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # requires max (n - 1) passes
swapped = False # flag to check if any swaps occur

for j in range(n - i - 1): # last i elements are already in place

if arr[j] > arr[j + 1]: # swap if the elements are not in order
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True

if not swapped: # array is already sorted

break

*** IMPORTANT NOTE ***

If Cambridge wants you to write the Bubble Sort algorithm, always give the OPTIMISED
version!

ASRJC H2 Computing 7
 >>> Searching and Sorting Algorithms
Characteristics of bubble sort
Simplicity
- Bubble sort is straightforward to implement. For small arrays, bubble sort is efficient, compared to
some of the sorting algorithms that use recursion (like quicksort or merge sort) which has overhead.

In-place sorting
- It sorts the array by modifying it directly. No additional memory allocation that is proportional to
the input array size is needed.

Stable sorting
- Preserves the relative order of equal elements in the sorted array.

Quite efficient for nearly sorted data

- Bubble sort can perform quite well when the data is already nearly sorted.
- The optimised bubble sort has an early exit mechanism (when no swaps are detected in a pass).

However, do note that bubble sort is inefficient for large arrays.

Similar to insertion sort, the worst case scenario would be when the input array is in reverse order. Maximum
number of comparisons and swaps are required to sort the array.

For a nearly sorted array, insertion sort is still generally more efficient compared to bubble sort. For such a case,
insertion sort’s approach of inserting one element at a time in its correct position is effective and requires fewer
comparisons and swaps.

Next, we look at two sorting algorithms that use recursion.

ASRJC H2 Computing 8
 >>> Searching and Sorting Algorithms
2.3 Quicksort Time complexity: O(n2)
Quicksort is a highly efficient and widely-used sorting algorithm based on the divide-and-conquer paradigm.
It divides the array into sub-arrays based on a pivot element and recursively sorts these sub-arrays.

Steps:

1. Choose a pivot element (e.g. first / last / middle element)

2. Create 3 sub-arrays: left with elements less than the pivot, middle with elements equal to the pivot,
right with elements greater than the pivot.
3. Recursively call itself on the sub-arrays left and right.
4. Combine the sorted left, middle, right sub-arrays and returns the sorted array.

In the example below, we choose the middle element as the pivot.

One Possible Implementation of Quicksort

def quicksort(arr):
if len(arr) <= 1: # base case
return arr

# Here, we choose pivot as the middle element, but you can choose others.
pivot = arr[len(arr) // 2]

left = []
middle = []
right = []

for element in arr:

if element < pivot:
[Link](element)
elif element == pivot:
[Link](element)
else:
[Link](element)

return quicksort(left) + middle + quicksort(right) # combine

# Example
arr = [5, 9, 1, 7, 2, 12, 6, 3]
print(quicksort(arr))
ASRJC H2 Computing 9
 >>> Searching and Sorting Algorithms
Remarks:
1. List comprehension could possibly be used to partition the elements:
left = [x for x in arr if x < pivot] # all elements smaller than pivot
middle = [x for x in arr if x == pivot] # all elements equal to pivot
right = [x for x in arr if x > pivot] # all elements greater than pivot

2. While the above implementation is not in-place, it is possible to write code for an in-place quicksort
implementation that does not require the creation of sub-arrays (left, middle, right).

The worst-case scenario for Quicksort occurs when the algorithm consistently choose the smallest or
largest element in the array as the pivot in each step. This results in highly imbalanced partitions, reducing
the efficiency of the algorithm.

Having said that, on average, Quicksort performs at O(n log n) time complexity.

In-place Quicksort using partition method

Depending on how the partitioning process is done, the relative order of equal elements may change. This is
especially the case if the partition method is used (refer to the last section). Quicksort focuses on rearranging
elements based on values in relation to the pivot without necessarily preserving the original order of the
elements. Therefore, Quicksort is generally considered not a stable sorting algorithm.

Choice of pivot

As mentioned, the pivot selection strategy is crucial to quicksort’s performance, as it directly relates to how
balanced the partitions will be. Here we discuss the main approaches:

• First or last element as pivot

This is the simplest approach. However, this performs terribly for nearly sorted or reverse sorted data,
leading to worst-case behaviour. Despite being easy to implement, it’s rarely used in practice.

• True median
The median is always the ideal pivot, as it splits the array into perfectly balanced partitions.
However, we are not able to directly identify the exact median of the array, unless we add an additional
layer of work, looping through the array (with O(n) time complexity) to identify it every time we perform
partitioning. Therefore, this approach is impractical for typical cases.

• Random pivot
Selecting a random element as the pivot is a popular strategy. The probability of hitting the worst case
is low due to the randomisation. Therefore, we expect O(n log n) time complexity for any input
distribution.

• Median-of-Three
This method examines the first, middle and last elements of the array, and chooses their median as the
pivot. It’s a good compromise between simplicity and effectiveness, often avoiding the worst case
scenario. Many quicksort implementations use this as their default strategy.

ASRJC H2 Computing 10
 >>> Searching and Sorting Algorithms
• Middle element

In the code example that we have for quicksort, we chose the middle element as the pivot. It’s simple
and performs better than choosing the first or last elements on sorted or reverse-sorted arrays.
However, it is still deterministic and predictable. Someone could construct an array where the middle
element is always a poor choice, leading to worst-case behaviour.

Exercise
Construct an array containing 16 distinct integers from 1 to 16 that would lead to maximum operations
(worst-case scenario) using the quicksort algorithm given in the lecture notes (where the middle element is
chosen as the pivot).

Possible answer: [1, 3, 5, 7, 9, 11, 13, 15, 16, 14, 12, 10, 8, 6, 4, 2]

ASRJC H2 Computing 11
 >>> Searching and Sorting Algorithms
2.4 Merge Sort Time complexity: O(n log n)
Merge sort is also an efficient algorithm based on the divide-and-conquer paradigm.

Steps:

1. Divide the array into smaller sub-arrays until each sub-array only has one element.
2. Merge the sub-arrays until a single sorted array is obtained.

Python Implementation of Merge Sort

def merge_sort(arr):
if len(arr) <= 1:
return arr # base case

# Divide array into 2 halves

mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]

# Recursively sort each half

left = merge_sort(left)
right = merge_sort(right)

# Merge the sorted halves

return merge(left, right)

def merge(left, right):

result = []
i = j = 0 # indices for left and right halves

while i < len(left) and j < len(right):

if left[i] < right[j]: # compare elements from left and right halves
[Link](left[i]) # append the smaller element
i += 1 # move to the next element in left half
else:
[Link](right[j])
j += 1

# Add any remaining elements

result = result + left[i:] + right[j:]

return result

# Example
arr = [5, 9, 1, 2, 12, 6]
print(merge_sort(arr))

ASRJC H2 Computing 12
 >>> Searching and Sorting Algorithms
Remark: Some might write the merge function as follows.

def merge(left, right):

result = []

while left and right: # while none of the two lists are empty
if left[0] < right[0]:
[Link]([Link](0))
else:
[Link]([Link](0))

# Add any remaining elements

result += left + right

return result

This version of the code, while having the benefit of being more concise, is less efficient.
Each time one element is removed from the front of a list (.pop(0)), all elements to the right have to be
shifted one position to the left. The time complexity for this operation is O(n), where n is the list length.
If the input array is large, this particular implementation would be very slow.

merge_sort(arr) is the main recursive function that

implements the algorithm. It divides the array into sub-arrays
and sorts them by recursively calling itself.

merge(left, right) is the helper function responsible for

merging two sorted sub-arrays. It compares elements from left
and right sub-arrays and merges them in the correct order
into a single sorted sub-array.

• Merge sort is an efficient algorithm, performing well on

large arrays with time complexity O(n log n).

• Time complexity remains the same regardless of the

order of the input array.

• It is a stable sorting algorithm.

• It is not an in-place algorithm. It requires additional

memory for subarrays created in the process, thus not
suitable for memory-constrained systems.

• Even if the array is nearly sorted, merge sort will still

need to do the full divide and merge, with no early exit
optimisation.

• Merge sort has significant overhead: recursive function

calls and array creation/copying. So for small arrays,
simpler algorithms like insertion sort are typically faster.

ASRJC H2 Computing 13
 >>> Searching and Sorting Algorithms
Section 3: Performance analysis of an algorithm
Time complexity
Time complexity quantifies the time taken by an algorithm in terms of the input size.

Note that it does NOT refer to the actual execution time on a machine.

We commonly consider the worst-case time complexity, and we consider only the asymptotic behaviour.
Therefore, we can use the “big O” notation to represent such worst-case time complexities. It describes an
upper bound on the growth rate of the time relative to the input size.

Below are some common growth rates, ranking from lowest to highest:

Complexity Name Is it good?

O(1) Constant Excellent!
O(log n) Logarithmic
O(n) Linear
O(n log n) Linear-logarithmic
O(n2) Quadratic
O(2n) Exponential
Terrible!
O(n!) Factorial

O(n!) O(2n) O(n2)

No. of operations

O(n log n)

O(n)

O(log n)
O(1)
Input size

Based on this chart, O(1), which stands for constant time complexity, is the best. If you see time complexities of
O(n2), O(2n), O(n!), you know that these are bad for large datasets.

ASRJC H2 Computing 14
 >>> Searching and Sorting Algorithms
Let’s look at each complexity with examples.

Constant Time Complexity O(1) Finding the first element in an array

Not dependent on the size of input. Finding the median in a sorted array

Logarithmic Time Complexity O(log n) Binary search algorithm

The input size decreases by half on each iteration.

Linear Time Complexity O(n) def sum_array(arr):

Running time increases linearly with the size of the total = 0
input. for element in arr:
total += element
return total

Quadratic Time Complexity O(n2) def sum_matrix(matrix):

When you perform nested iteration (loop in a loop), total = 0
time complexity is quadratic. for row in matrix:
for element in row:
total += element
return total

Exponential Time Complexity O(2n) def fib_r(n):

You get exponential time complexity when the if n < 2:
number of operations executed doubles with each return n
increment of the input size n. return fib_r(n - 1) + fib_r(n - 2)

A typical example would be the recursive Fibonacci

sequence.
Factorial Time Complexity O(n!) The brute-force approach to solve the Travelling
This happens when the number of operations required Salesman Problem has a time complexity of O(n!).
to solve a problem grows factorially with input size.
This occurs in algorithms that involve generating all
possible permutations of a set of elements.

ASRJC H2 Computing 15
 >>> Searching and Sorting Algorithms
Let’s discuss the time complexities of the algorithms that we have discussed in this chapter.

Linear search, O(n)

Since you have to go through each element sequentially to check if the current element matches the target,
the number of operations required is directly proportional to the size of the input.

If T(n) is the maximum number of comparisons required by the algorithm for an input size n,
T(n) = n.

Binary search, O(log n)

In each iteration, the search space is halved. So in this case,
T(n) = log2(n).

If an array has size 8, it requires a maximum of 3 comparisons to either find the target or to determine that it
is absent in the input array.

Insertion sort, O(n2)

Consider the worst-case scenario, when the input array is in reverse order.

We start with the second element. It has to be compared with the first element.
The third element has to be compared with the previous two elements.
…
The nth element has to be compared with the previous (n – 1) elements.

𝑛−1 1
T(n) = 1 + 2 + 3 + … + (n – 1) = 2
(1 + (𝑛 − 1)) = (𝑛2 − 𝑛).
2

The number of swaps for this worst-case scenario is the same as the number of comparisons.

For “big O” notation, we only consider the dominant term, which in this case is the quadratic term.
Therefore, it is O(n2).

Bubble sort, O(n2)

Again, we consider the worst-case scenario, when the input array is in reverse order.
For the first pass, n – 1 comparisons are required. For the second pass, n – 2 comparisons are required.
Adding up the number of comparisons,
1
T(n) = (n – 1) + (n – 2) + (n – 3) + … + 2 + 1 = 2 (𝑛2 − 𝑛).

Total number of swaps is also the same. Therefore, time complexity is also O(n2).

Quick sort, O(n2)

The number of comparisons depends on the choice of the pivot and how well it divides the array. The
partitioning takes O(n) time. As the Quicksort algorithm follows the divide and conquer paradigm, it typically
takes O(log n) time. Average overall time complexity is therefore O(n log n).

However, we now consider the worst-case scenario.

If the pivot chosen happens to be always the smallest or the largest element, then we are going to have
- the first partitioning: an array with size (n – 1) and an array with only the pivot.
ASRJC H2 Computing 16
 >>> Searching and Sorting Algorithms
- the second partitioning: an array with size (n – 2) and an array with only the pivot.
- …
- the final partitioning: an array with size 1 and an array with only the pivot.

The recursion tree effectively follows a linear structure with n levels.

• To mitigate such a worst-case scenario, we may opt for a variation, known as Randomised Quicksort. The
choice of pivot is made randomly, often leading to a more balanced partition, which means better
performance.

Merge sort, O(n log n)

At each level of recursion, the array is divided into two similar-sized sub-arrays. Therefore, the total number
of levels in the recursion tree is log2(n).
Time taken at each level of the recursion tree is O(n) due to the merging step.
Therefore, T(n) = O(n log n).

Space Complexity (excluded from syllabus)

Besides time complexity, computer scientists are also concerned about space complexity, which is a measure of
the amount of memory space an algorithm uses in relation to the input size.

Linear Search Space Complexity: O(1)

Binary Search They do not require extra memory that scales with the input size.

Insertion Sort Space Complexity: O(1)

Bubble Sort They can be performed in-place, meaning it rearranges the elements within the array
without using additional memory that scales with input size.

Quicksort Space Complexity: O(n) in the worst-case scenario.

In the worst-case, there will be n recursive calls, so the size of the recursion tree will be n.

Merge Sort Space Complexity: O(n). A temporary array is needed to store the merged elements.

ASRJC H2 Computing 17
 >>> Searching and Sorting Algorithms
Section 4: Quicksort continued – the Partition Method
For the quicksort algorithm, we have demonstrated the simple approach by creating two new subarrays to
store values smaller than and greater than the pivot value. This is easy to understand but uses extra memory.

If we want to conserve memory space, we might opt for an in-place partitioning, where elements are
rearranged within the original array.

Say we have the following initial array:

If we choose the rightmost element (i.e. 5) as the pivot, we hope to rearrange the elements so that we get:

Here we introduce the partition method, with the rightmost element chosen as the pivot:
def partition(arr, left, right):
pivot = arr[right]
i = left - 1
for j in range(left, right):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# insert pivot
arr[i + 1], arr[right] = arr[right], arr[i + 1]
return i + 1 # returns pivot index

def quicksort(arr, left, right):

if left < right:
pivot_index = partition(arr, left, right)
quicksort(arr, left, pivot_index - 1) # sort left
quicksort(arr, pivot_index + 1, right) # sort right

# Test
arr = [9, 3, 7, 1, 2, 8, 6, 5]
quicksort(arr, 0, len(arr) - 1)
print("Sorted array: ", arr)

We start with left = 0, right = 7.

Here, we shall use index i to mark the last position of the “≤ pivot” zone, while j will scan from left to right – 1.

Refer to the walkthrough on the next page to understand how this process works.

ASRJC H2 Computing 18
 >>> Searching and Sorting Algorithms
def partition(arr, left, right):
pivot = arr[right]
i = left - 1
for j in range(left, right):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# insert pivot
arr[i + 1], arr[right] = arr[right], arr[i + 1]
return i + 1 # returns pivot index

Initial state Execute:

partition(arr, 0, 7)

pivot = arr[7] = 5
i = left – 1 = –1
j=0

Currently, j = 0.
Perform comparison:
Is 9 ≤ 5? No.
Do NOT increment i and
do NOT swap

Proceed with j = 1.

Currently, j = 1.
Perform comparison:
Is 3 ≤ 5? Yes!
We found an element ≤ pivot.
Increment i, then
swap arr[i] with arr[j]

Proceed with j = 2.

Currently, j = 2.
Perform comparison:
Is 7 ≤ 5? No.
Do NOT increment i and
do NOT swap

Proceed with j = 3.

ASRJC H2 Computing 19
 >>> Searching and Sorting Algorithms
Currently, j = 3.
Perform comparison:
Is 1 ≤ 5? Yes!
We found an element ≤ pivot.
Increment i, then
swap arr[i] with arr[j]

Proceed with j = 4.

Currently, j = 4.
Perform comparison:
Is 2 ≤ 5? Yes!
We found an element ≤ pivot.
Increment i, then
swap arr[i] with arr[j]

Proceed with j = 5.

Currently, j = 5.
Perform comparison:
Is 8 ≤ 5? No.
Do NOT increment i and
do NOT swap

Proceed with j = 6.

Currently, j = 6. (final iteration)

Perform comparison:
Is 6 ≤ 5? No.
Do NOT increment i and
do NOT swap

Since we know that all elements

from index 0 to i = 2 are less
than or equal to 5, we should
put the pivot to the right of
that, i.e. at index i + 1.

So we swap arr[i + 1] with

arr[right].

Return the index of the pivot,

i.e. i + 1 = 3.

ASRJC H2 Computing 20
 >>> Searching and Sorting Algorithms
Quick exercises
1. For the previous example, show the state of the array for each of the subsequent steps, until the array is
completely sorted using quicksort.

2. Draw the trace table for the execution of partition(arr, 0, 9),

where arr = [19, 7, 3, 9, 4, 2, 11, 0, 23, 5]. The table headers should be as follows:

i j arr[j] pivot arr return value

3. The following shows the partition method for the case where the first element is selected as the pivot:

def partition_left_pivot(arr, left, right):

pivot = arr[left] # choose leftmost element as pivot
i = right + 1 # start from right end + 1

# Scan from right to left

for j in range(right, left, -1):
if arr[j] >= pivot: # elements >= pivot go to the right
i -= 1
arr[i], arr[j] = arr[j], arr[i]

# insert pivot
i -= 1
arr[left], arr[i] = arr[i], arr[left]
return i

Draw the trace table for the execution of partition_left_pivot(arr, 0, 9),

where arr = [19, 7, 3, 9, 4, 2, 11, 0, 23, 5]. The table headers should be as follows:

i j arr[j] pivot arr return value

Remarks on partition method:

• As mentioned previously, selecting the leftmost or the rightmost element as pivot is simple, but can lead to
worst-case O(n2) time complexity if the array is already sorted. Therefore, selecting a random pivot or a
median-of-three (median of first, middle, last elements) as the pivot can provide better performance.

• The partition operation is not stable – it does not preserve the relative order of equal elements.

ASRJC H2 Computing 21
 >>> Searching and Sorting Algorithms

Recap
• Searching Algorithms
Linear def lin_search(arr, target):
for i in range(len(arr)):
Search
if arr[i] == target:
O(n) return i
return -1

Binary def bin_search(arr, target):

left = 0
search
right = len(arr) - 1
O(log n)
while left <= right: # check if search range is valid
Array must mid = (left + right) // 2
already be mid_element = arr[mid]
sorted. if mid_element == target:
return mid # target found
Iterative elif mid_element < target:
version left = mid + 1 # search right
else:
right = mid - 1 # search left

return -1 # target not found

Recursive def bin_search(arr, target, left, right):

# invalid search range
version
if left > right:
return -1 # target not found

mid = (left + right) // 2

mid_element = arr[mid]

if mid_element == target:
return mid # target found
elif mid_element < target:
return bin_search(arr, target, mid + 1, right) # search right
else:
return bin_search(arr, target, left, mid - 1) # search left

# Test
bin_search([2, 7, 12, 15, 16, 19], 16, 0, 5)

- Data structures such as binary search trees (BST) and hash tables can also support efficient
searching.

ASRJC H2 Computing 22
 >>> Searching and Sorting Algorithms
• Sorting Algorithms
Insertion sort def insertion_sort(arr):
# loop from the second element until the last element
O(n2)
for i in range(1, len(arr)):
key_element = arr[i] # element to be inserted
- In-place j = i – 1
- Stable sort
- Adaptive while j >= 0 and arr[j] > key_element:
arr[j + 1] = arr[j] # shift the element to the right
j -= 1

arr[j + 1] = key_element # insert key element

Bubble sort def bubble_sort(arr):

n = len(arr)
(optimised)
for i in range(n - 1):
O(n2) swapped = False

- In-place for j in range(n - i - 1):

- Stable sort if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True

if not swapped: # no swaps occurred, so array is sorted

break

Quicksort def quicksort(arr):

# base case
O(n2)
if len(arr) <= 1:
return arr
- Unstable sort
pivot = arr[randint(0, len(arr) – 1)] # random pivot

left = []
middle = []
right = []

for element in arr:

if element < pivot:
[Link](element)
elif element == pivot:
[Link](element)
else:
[Link](element)

return quicksort(left) + middle + quicksort(right) # combine

ASRJC H2 Computing 23
 >>> Searching and Sorting Algorithms
Merge sort def merge_sort(arr):
# base case
O(n log n)
if len(arr) <= 1:
return arr
- Stable sort
- NOT in-place # divide array into 2 halves
- NOT mid = len(arr) // 2
left = arr[:mid]
adaptive right = arr[mid:]

# recursively sort each half

left = merge_sort(left)
right = merge_sort(right)

# merge the sorted halves

return merge(left, right)

def merge(left, right): # helper function

result = []
i = j = 0

while i < len(left) and j < len(right):

if left[i] < right[j]:
[Link](left[i])
i += 1 # move to the next element in left half
else:
[Link](right[j])
j += 1 # move to the next element in right half

# Add remaining elements

result = result + left[i:] + right[j:]

return result

ASRJC H2 Computing 24