Answer: O(n^2) for both, where n is the length of the list

Answer: For each iteration of Selection Sort we find the minimum value starting at the 0th index and traverse the list. We store the minimum value in a variable and note the index it was found. We then place the current value of the array at the current index in a temp variable. We replace the current value with the minimum and the value at which minimum value was found with the temp variables value.

Answer: Selection Sort finds the minimum value for each index of the array and successively does this until the end of the array is reached.    To add on: Once it “selects” the minimum value in the unsorted portion of the list it then swaps it into the end of the sorted portion of the list, which will be its final position.  

Answer: A sorting algorithm is said to  be stable if the relative order is maintained after the list has been sorted. For example: [1,3a,3b,2]->[1,2,3a,3b] this is stable.  Bubble sort is stable because of the strict < comparison in the code (elements are only swapped if they are less than the other element, so equal elements are not swapped and the relative order is maintained). Using <= would make it unstable.      Feedback:  The ‘>’ comparison is being done, elements are swapped if the element on the left is greater than the one on the right.

Answer: An algorithm is said to be incremental if it does not need to recompute everything after a small change. For example: adding an element to a sorted list and sorting it again. If it only takes a few iterations, it would be called incremental.  Bubble sort is incremental when the element is added to the front of the list because it will reach its correct position in the list in the first iteration. But if you add it to the end of the list, the number of iterations required would depend on the position of the element. (Include an example) Adding onto this ^^:  This is because of the invariant that mentions that in each traversal, the largest unsorted element will get to its final position.     Eg:  Original sorted list: [3, 6, 10, 14, 18, 20]  After appending 13 at the end: [3, 6, 10, 14, 18, 20, 13] Note that 14, 18 and 20 are not in their final positions and require 3 traversals of the list in order to sort the list. …

Answer: Bubble sort 1 stops after n-1 iterations of the outer loop. Bubble sort 2 stops when none of the elements have been swapped in the last. Bubble sort 2 is the optimised version of bubble sort 1 where there is a conditional break if the list becomes sorted before n-1 traversals are over.   Feedback: Missing word have been swapped in the previous iteration.   …where n is the number of elements in the list

1. Example: [5, 20, -5, 10, 3] Answer: [5,-5,10,3,20]   Alternative Answer:  After every traversal, the largest unsorted element gets to its final place 2. Example: [-5, -20, -5, -10, 3] Answer: [-20,-5,-10,-5,3]

Answer: Bubble sort 1 has two loops. The outer loop runs n-1 times and so does the inner loop (n is the length of the list). So the overall complexity in all cases comes out to be (n-1)^2 which is O(n^2).   Bubble sort 2 also has two loops but there is a conditional break. If none of the numbers are swapped during a traversal, then the loop is stopped. The best case of O(n) occurs when the list is already sorted and it takes one traversal to make sure that the list is sorted.    The worst case is when the list is sorted in the reverse order (both inner and outer loop will run n-1 times). So the worst case complexity is O(n^2).   Alternative Answer #1 (more in depth)(Feedback: Correct) For the best case, this will occur when the list is already sorted Bubble Sort II will check every element in the list once, resulting in n operations, where  n  is the number of elements in the list. It will check only…

Answer: 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). Feedback: Alt answer #1: Add the statement   Bubble sort is a sorting algorithm whose main idea is to place the largest unsorted element into its final position after each traversal.

Answer: The overall complexity of Bubble sort 1 in both best and worst cases is O(n^2) The overall best-case complexity of Bubble sort 2 is O(n) and its worst case complexity is O(n^2) where n is the length of the list.   Feedback: Would be good to define what n actually is for 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