A1 Theory W0 Flashcards
Briefly describe Bubble sort giving details about.
The main idea of Bubble Sort.
What is the largest number of swaps performed by Bubble Sort per item in the list?
What is the best case and worst case complexity?
Explain why the best and worst case are as stated. No explanation no marks.
Bubble sort is a s simple comparison based sorting algorithm that steps through the list to be sorted and compares adjacent elements and swaps them if in the wrong order. This gradually bubbles the larger elements towards the end and floats the smaller elements towards the front.
Largest number of swaps performed by bubble sort is n-1 (DEGREES OF FREEDOM).
Best case complexity of bubble sort is O(n), this is when the list is already sorted and no swaps are needed passing through.
Worst-case complexity of bubble sort is O(n^2), this occurs when the input list is in reverse order, leading to the maximum amount of swaps.
What is the result of applying one iteration (list traversal) of Bubble Sort if one wants to sort the list in increasing order and starts from the left?
Example: [5, 20, -5, 10, 3]
Example: [-5, -20, -5, -10, 3]
After one iteration the of example one: the largest element 20 will have moved to the back of the list but all the other elements will be out order. The resulting list will be [5,-5,10,3,20].
After one iteration of example two: the smallest element -20 will have moved right position and all other elements except 3 will be out of position. Resulting [-20, -5, -10, -5, 3]
When does Bubble Sort stop? Describe at least one way to improve Bubble Sort.
Bubble sort will stop when there are no swaps being made when passing through the list.
One way to improve bubble sort is to add a mark that will say where a swap has not been made so that part is known to already be sorted. You can also set the mark to n-1 so the last element is not checked against None.
What does it mean for a sorting algorithm to be incremental? Is BubbleSort incremental? Why and when?
An algorithm is incremental when it does not need to recompute everything after a small change. It can reuse most the work already done to handle the change.
A sorting algortihm is incremental when it can: be given a sorted list and add one new element. use one or a few iterations of the algorithm to return a sorted list that has the new element.
Bubble sort is not inherently incremental as it requires multiple passes through the elements to sort. When comparing two elements, even though a swap is made the previous element may not be in it’s final position.
What does it mean for a sorting algorithm to be stable? Why? Is Bubble Sort stable?
A sorting algorithm is considered stable if it preserves the relative order among elements. Changing the relative order is not stable. Stability helps values stay together, especially in something like a spreadsheet.
For example, if I have a list [A1,A2,B3,B5], A1 and A2 will always stay in that order no matter what happens around them in the list. The same thing goes for B3 and B5, if the algorithm is stable they will never be in the order [B5, B3].
Yes, Bubble sort is a stable algorithm. It will only ever swap adjacent values if they are out of order and it does not move elements around unnecessarily.
Briefly describe Insertion sort giving details about.
The main idea of Insertion Sort.
Explain what one iteration does.
What is the best case and worst case complexity?
Explain why the best and worst case are as stated. No explanation no marks.
Insertion sort is a comparison based sorting algorithm that builds the final sort one element at a time. Like sorting a hand of cards by repeatedly inserting one card into its correct position.
Insertion sort divides the the input into two portions, the sorted and unsorted portions, the algorithm repeatedly takes an element form the unsorted portion and inserts it into the sorted portion in the correct position.
In one iteration, an element from the unsorted portion will be added to the sorted portion in the correct position and shifting larger elements one position to the right.
Best-case of insertion sort is O(n), when the input list is alredy sorted and each new element inserted is compared to the previous element.
Worst case of insertion sort is O(n^2), this is when the input list is in reverse order and each new element needs to be compared and inserted at the beginning of the sorted portion.
What is the result of applying one iteration of Insertion Sort if one wants to sort the list in increasing order and starts from the left?
Example: [5, 20, -5, 10, 3]
Example: [-7,-1,-4,4,5,6]
In both examples the order will actually stay the same after one iteration.
This is because the first two elements will be compared to each other and no swapping is required.
The resulting lists will be the same as what they started after one iteration.
It takes one iteration to build a sublist of length 1 and two iterations to build a sublist of length 2. To sort the whole list it takes n-1 iterations.
What does it mean for a sorting algorithm to be incremental? Why? Is Insertion Sort incremental? Why and when?
An algorithm is incremental when it does not need to recompute everything after small changes. Able to re-use most of the work that is already done.
Yes, insertion sort is incremental as it builds the sorted sequence one element at a time.
What does it mean for a sorting algorithm to be stable? Why? Is InsertionSort stable?
A sorting algorithm is stable when the relative order of elements stays the same. If the relative order is changed then the algorithm is not stable.
For example, if you had an input list of [A1,A2,B5,B6], A1 and A2 will always stay in that order if the algorithm is stable. If they become [A2,A1] then the sorting algorithm has failed to maintain the relative order.
Yes, insertion sort is a stable algorithm if implemented correctly. Insertion sorts always puts an element in its correct position which maintains the relative order.
Selection sort is a comparison based algorithm that sorts an array by repeatedly selecting the smallest element from the unsorted portion of the array and places it in its correct position in the sorted portion.
