1b

The main idea of Bubble Sort

A sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order, continuing until no swaps are needed.

Start by comparing the first pair of elements and swap them if the first element is greater than the second (assuming ascending order). Repeat for all pairs in the list. Repeat this whole iteration n-1 times (or until the whole list is sorted by checking if no swaps were done in the current iteration (optimisation 1)). There is no need to check the elements that were already sorted in subsequent iterations so reduce the range by 1 in each iteration (optimisation 2).

1. What is the largest number of swaps performed by Bubble Sort per item in the list?

The maximum number of swaps performed by Bubble Sort per item in the list is n-1, where n is the number of elements in the list.

Complexity of Bubble Sort 1

The overall complexity of Bubble Sort 1 in both best and worst cases is O(n^2), where n is the number of elements in the list.

Complexity of Bubble Sort 2

The best-case complexity of Bubble Sort 2 is O(n) when the list is already sorted, and the worst-case complexity is O(n^2) when the list is in reverse order.

Best and Worst Case Explanation

Bubble Sort 1 has two loops leading to O(n^2) complexity, while Bubble Sort 2 can exit early if no swaps occur, leading to O(n) in the best case.

One Iteration Result

After one iteration of Bubble Sort on [5, 20, -5, 10, 3], the result is [5, -5, 10, 3, 20].

Stopping Condition

Bubble Sort stops after n-1 iterations for Bubble Sort 1 and when no swaps occur for Bubble Sort 2.

Incremental Sorting Algorithm

An algorithm is incremental if it can sort a list with minimal recomputation after a small change; Bubble Sort is incremental when adding an element to the front.

Stability of Sorting Algorithm

A sorting algorithm is stable if it maintains the relative order of equal elements; Bubble Sort is stable due to its strict comparison.

Selection Sort

A sorting algorithm that finds the minimum value in the unsorted portion and swaps it with the first unsorted element until the list is sorted.

Selection Sort Iteration

In one iteration of Selection Sort on [5, 20, -5, 10, 3], the result is [-5, 20, 5, 10, 3].

Complexity of Selection Sort

The best and worst-case complexity of Selection Sort is O(n^2), where n is the length of the list.

Stability of Selection Sort

Selection Sort is not stable as it may disrupt the relative order of equal elements during swaps.

Insertion Sort

A sorting algorithm that builds a sorted list by repeatedly taking the next unsorted element and inserting it into the correct position in the sorted portion.

Complexity of Insertion Sort

The best-case complexity is O(n) when the list is already sorted, and the worst-case complexity is O(n^2) when the list is in reverse order.

Incremental Nature of Insertion Sort

Insertion Sort is incremental as it can insert a new element into a sorted list with minimal operations.

Stability of Insertion Sort

Insertion Sort is stable as it maintains the relative order of equal elements during insertion.

Algorithm Expectations

An algorithm is expected to have a finite set of well-defined instructions and produce correct outputs for valid inputs.

Input Size in Algorithms

The input size can refer to the number of elements, the number of bits for integers, or the number of vertices/edges in graphs.

Time Complexity Measurement

Algorithmic time complexity should be measured with respect to the input size, focusing on the number of elementary operations performed.

Big O Notation

f(n) = O(g(n)) means that f(n) grows at a rate less than or equal to a constant multiple of g(n) for sufficiently large n.

Worst-case vs

Worst-case complexity describes the maximum time/resources required, while best-case complexity describes the minimum.

Abstract Data Type (ADT)

An ADT defines the values and operations without specifying implementation; examples include Stack ADT and Queue ADT.

Stack ADT

A Last In First Out (LIFO) data structure with key operations like push(), pop(), and peek().

Queue ADT

A First In First Out (FIFO) data structure with key operations like append(), serve(), and is_empty().

List ADT

A data structure that stores items in order, allowing operations like insert(), delete(), and access.

Sorted List ADT

A list that maintains elements in sorted order, allowing efficient searching and insertion.

Linked Nodes vs

Linked nodes allow for efficient insertion/deletion but have slower access times compared to arrays.

Bit-Vector

A compact representation of a set using bits, where each bit indicates the presence or absence of an element.

Complexity of Set Operations

The complexity of operations like add(), remove(), and union varies based on the underlying data structure (array vs. bit-vector).