2.3.1 Sorting Algorithms

Question 1

Bubble sort

Answer 1

Makes comparisons and swaps between pairs of elements

The largest element in the unsorted part of the input is said to “bubble” to the top of
the data with each iteration of the algorithm

Starts at the first element in an array and compares it to the second

If they are in the wrong order, the algorithm swaps the pair

The process is then repeated for every adjacent pair of elements in the array,
until the end of the array is reached

This is one pass of the algorithm

For an array with n elements, the algorithm will perform n passes through the data

After n passes, the input is sorted and can be returned

Question 2

Bubble sort (analysis)

Answer 2

Can be modified to improve efficiency

A flag recording whether a swap has occurred is introduced

If a full pass is made without any swaps, then the algorithm terminates

With each pass, one fewer element needs comparing as the n largest elements are
in position after the nth pass

Bubble sort is a fairly slow sorting algorithm, with a time complexity of O(n2)

Question 3

Insertion sort

Answer 3

Places elements into a sorted sequence

In the ith iteration of the algorithm the first i elements of the array are sorted

Warning: although the i elements are sorted, they are not the ismallest
elements in the input!

Starts at the second element in the input, and compares it to the element to its left

When compared, elements are inserted into the correct position in the sorted
portion of the input to their left

This continues until the last element is inserted into the correct position, resulting in
a fully sorted array

Has the same time complexity as bubble sort, O(n2)

Question 4

Merge sort

Answer 4

Example of a “divide and conquer” algorithm

Formed from two functions. MergeSort and Merge

MergeSort divides its input into two parts and recursively calls MergeSort
on each of those two parts until they are of length 1

Merge is then called

Merge puts groups of elements back together in a special way, ensuring that
the final group produced is sorted

The exact implementation of merge isn’t required, but knowledge of how it works is

A more efficient algorithm than bubble sort and insertion sort, with a worst case time
complexity of O(n logn)

Question 5

Quick sort

Answer 5

Works by selecting an element, often the central element (called a pivot), and
dividing the input around it

Elements smaller than the pivot are placed in a list to the left of the pivot and others
are placed in a list to the right

This process is then repeated recursively on each new list until all elements in the
input are old pivots themselves or form a list of length 1

Quick sort isn’t particularly fast, with time complexity O(n2)