2. 3. 3 Sorting Algorithms

Question 1

Keep in mind

Answer 1

For any sort make sure you check what the question is asking, it can easily catch you out by doing descending order rather than ascending order.

Question 2

Bubble Sort

Answer 2

• Makes comparisons, swaps between pairs of elements
• Algorithm compares first element in array with second element
• If they are in wrong order, switch places else algorithm moves on
• Process repeats till end of array is reached (Largest element in last position of array)
• This is referred to as a “pass” of the algorithm
• An array with n elements, algorithm will perform n passes through the data
• Clear that Bubble sort prone to wasting time by doing unnecessary checks
• Time complexity of O(n^2)
• Example in next flashcard demonstrates this

Question 3

Pseudocode for Bubble Sort

Answer 3

• A = Array of data
• for i = 0 to A.length - 1:
• noSwap = True
• for j = 0 to A. length - (i + 1):
• if A[j] > A[j+1]:
• temp = A[j]
• A[j] = A[j+1]
• A[j+1] = temp
• noSwap = False
• if noSwap:
• break
• return A

Question 4

Example of a Bubble Sort

Answer 4

• Use Bubble Sort to arrange following elements into ascending order
• |4| |9| |1| |6| |7|
• 4 and 9 compared, stay in place, 9 and 1 compared, switch places
• |4| |1| |9| |6| |7|
• 9 and 6 compared, switch places, 9 and 7 compared, switch places
• |4| |1| |6| |7| |9|
• This is the end of first pass, second pass begins
• 4 and 1 compared, switch places
• |1| |4| |6| |7| |9|
• Everything else compared again, marks end of second pass
• Another 2 passes occur ending on pass 5 (remember 5 elements 5 passes)

Question 5

Insertion Sort

Answer 5

• Places elements into a sorted sequence
• First element compared to element on the left
• Second element compared to element on the left, if it is smaller swap
• Moves on to the third, same process occurs again
• Keep in mind that a pass still occurs even if no swap were made
• Each time a pass occurs, the sorted list increases by one value

Question 6

Pseudocode for Insertion Sort

Answer 6

• A = Array of data
• for i = 1 to A.length - 1:
• elem = A[i]
• j = i − 1
• while j > 0 and A[j] > elem:
• A[j+1] = A[j]
• j = j − 1
• A[j+1] = elem

Question 7

Example of an Insertion Sort

Answer 7

• |4||9||1||6||7|
• Algorithm ignores first element as it is a part of the “sorted list”, starts with second element
• Second element compared to 4, bigger, stays in place, one pass occurs everything remains in place
• |4||9||1||6||7|
• Third element compared to 9, smaller, swaps places, compared to 4, smaller, swaps places
• |1||4||9||6||7|
• Fourth element compared to 9, smaller swaps places, compared to 4, bigger, stays in place
• |1||4||6||9||7|
• Fifth element compared to 9, smaller, swaps places, compared to 6, bigger, stays in place
• |1||4||6||7||9|
• Left with our sorted list
• Each time a pass occurs, the sorted list increases by one value

Question 8

Merge Sort

Answer 8

• Example of a class of algorithms known as “divide and conquer”
• Pseudocode below is not an exact implementation but demonstrates how it works
• Merge sort splits array evenly into smaller arrays till there is one value per array (isolation)
• The arrays are then “merged” back together in the desired order (Alphabetic, ascending, descending)
• It is more efficient than bubble and insertion sort with a worse case complexity of 0(n logn)

Question 9

Pseudocode for Merge Sort

Answer 9

• A = Array of data
• MergeSort (A)
• if A.length <= 1:
• return A
• else:
• mid = A.length / 2
• left = A[0…mid]
• right = A[mid+1…A.length-1]
• leftSort = MergeSort(left)
• rightSort = MergeSort(right)
• return Merge(leftSort, rightSort)

Question 10

Example of a Merge Sort

Answer 10

• Sort the following array using a merge sort in ascending order
• |7||4||2||6|
• |7||4| |2||6|
• |7| |4| |2| |6|
• |4||7| |2||6|
• |2||4||6||7|

Question 11

Quick Sort

Answer 11

• An element is selected, often the central element known as the pivot
• Elements smaller than pivot placed in array to the left of the pivot, others placed right of the array
• Process repeated recursively on each new array till every element is either an old pivot or an array of length 1
• Not particularly fast, time complexity of O(n^2)

Question 12

Example of a Quick Sort

Answer 12

• Sort the following list using a quick sort in ascending order
• |9||4||7||8||6||3||1||5||2|
• Central element is first pivot, pivot is 6
• Elements compared from left to right, larger than pivot placed in array to the right, smaller than pivot placed in array to the left
• Array on the left is |4||3||1||5||2| and consists of 5 elements
• Array on the right is |9||7||8| and consists of 3 elements
• 6 is now an old pivot and is the correct place, new pivot selected for each array
• Pivot for array on left is 1 and pivot for array on right is 7
• No elements smaller than 1, no new left array, 4 elements greater than 1 creating new array on the right
• New array on the right of 1 is |4||3||5||2| and consists of 4 elements
• No elements smaller than 7, no new left array, 2 elements greater than 7 creating new array on right
• New array on right of 7 is |8||9| and consists of 2 elements
• Elements 1, 6 and 7 are all old pivots leaving us with a 4-element list and a 2-element list
• The same process repeats till we are left with the sorted list
• |1||2||3||4||5||6||7||8||9|

Question 13

Example with just workings

Answer 13

• Bold black border means that element is the new pivot
• Shaded in black element means the element is an old pivot
• As we can see, sort stops because all that’s left is single element arrays and old pivots