Sorting Algorithms

Question 1

What is the fundamental algorithm for bubble sort?

Answer 1

1. Start at leftmost X
2. If X > Y, swap them
3. Move to right

Question 2

Why is the number of iterations in a bubble sort n-1

Answer 2

Bubble sort compares the current position to the left.
Maximum number of possible comparisons is n-1

If you attempted to compare at n, you’d be trying to access n+1 which doesn’t exist

Question 3

What is bubble sorts key invariant?

Answer 3

That after each traversal of the array, the largest unsorted element gets to its final place.

Question 4

What are the two optimizations that can be used to turn Bubble Sort into BubbleSort 2?

Answer 4

1. Avoid comparing sorted elements - this uses the invariant (after each traversal, the largest unsorted element gets to the final place)

Effectively, set the inner loop to loop from 0 to mark, which initally equals n-1, and each traversal decrease mark by 1

2. Check for early sort - if the array is sorted, no swaps will occur, so if swapped remains false for a full traversal, then exit the loop

Question 5

Is Bubble Sort 2 Incremental?

Answer 5

Depends - if you add an element at the end of the array, it isn’t
- this is because the algorithm compares forwards,
- so to move an element back, the algorithm will need to traverse the entire array to move an element back. (so it could be 3 iterationsto move an element back 3 places)

If you add the element at the front:
- Will only need maximum 2 traversals
- will move the element to the correct position in the first traversal
- second traversal is to confirm the list is sorted
- so it is incremental if you add it to the front
- but also consider the cost of shifting each element forward O(n)

Question 6

Is Bubble Sort 2 Stable?

Answer 6

Yes - because the comparison is > and not >=, so elements will maintain their order.

If the comparison was >=, then it would not be stable, as if you had [1,3,3], the 2nd and 3rd ‘3’s would be swapped

Question 7

Key Algorithm of a Selection Sort

Answer 7

In every iteration:
1. Start at the leftmost unsorted element, and set it as the current min
2. Traverse the remainder of the unsorted, find the minimum element (if it’s greater than the current)
3. Swap it with the leftmost unsorted element

Question 8

Is Selection Sort incremental?

Answer 8

No - it assumes that the elements left of the mark are sorted, and so it will not traverse those elements. This means that the algorithm will not correctly handle a new element.

It would need to do the entire sort again

Question 9

Is Selection Sort stable?

Answer 9

No - as it may swap non-consecutive numbers, meaning that it’s possible that two equal numbers end up with a change in their relative order

think if you had 14(1), 14(2), 13 -> after a traversal, it would be 13, 14(2) and 14(1)

Question 10

Key Algorithm of Insertion Sort

Answer 10

Split the list in 2:
- Part S (Sorted) which contains elements already sorted (initially is the first element always)
- Part U (Unsorted), everything else

Then, extend S by taking any element from U, and inserting it in S whilst maintaining the order

Each Iteration therefore:
- store the first unsorted value X in a temporary place
- shift all sorted elements bigger than X (inside S), one position to the right
- Copy X into the newly freed space

Question 11

Invariants of Insertion Sort

Answer 11

Elements in Sorted, grow by 1 in each iteration

Elements in S may not be in their final position (others may move in between them later)

Question 12

Number of iterations required for insertion sort

Answer 12

n-1, need to compare at every element

Question 13

Is an Insertion Sort incremental?

Answer 13

Yes, we can add an element at the end, and it’ll be correctly sorted.

This is because of the invariant, all elements in S are sorted, but may not be in their final position

Adding at the front will not work (as it should be sorted relative to the array)

Question 14

Is an Insertion Sort stable?

Answer 14

Yes, because we only move elements that are > than the temp, meaning that elements will maintain their relative order.

The only time that elements can get out of order, is when we shuffle to the right, and re-insert from the temp.

If we changed it to >=, then elements of the same value would possibly be swapped.

Question 15

Bubble Sort Best&Worst Complexity (+ explanation)

Answer 15

Best Case: O(n), where the array is already sorted, will only require one iteration to determine no swaps occur (mark 2)

Worst Case: O(n^2), where the elements are sorted in reverse order, and n^2 iterations are required

Question 16

Selection Sort Best&Worst Complexity (+ explanation)

Answer 16

Best & Worst is O(n^2). At each step, the algorithm identifies the minimum element and places it in its correct position. However, the minimum element cannot be determined until the entire array is traversed.

Question 17

Insertion Sort Best&Worst Complexity (+ explanation)

Answer 17

Worst Case is O(n^2): The array is in reverse order, so the loop will need to run n^2

Best Case is O(n): The array is sorted, so the inner loop will never run

Question 18

Selection Sort, what to be careful of when swapping

Answer 18

If mark represents the first non-sorted element, then make sure you are swapping with mark-1

Question 19

Insertion Sort, what to be careful of when swapping

Answer 19

make sure to set array[i+1] = tmp