Answer:   Consider the first element as “sorted” (might not necessarily be true)   Create temp variable for first unsorted number   Check over each number in the sorted partition (decrementing right to left)   If the decremented element is greater than temp, shift it to the right by 1 spot.   Once the decremented element is less than or equal to temp, overwrite the number after the decremented element with temp, thus “inserting” it.

Answer:incremental   An algorithm is said to be incremental if it does not need to recompute everything after a small change/if the algorithm can return a sorted list with the new element within one or few iterations.

Answer:   A sorting algorithm is considered stable if it preserves the relative order of items with equal values. This means that if two elements in the list are equal, their order relative to each other remains the same after sorting.   For. e.g. in a list of tuples[(Earl,80), (Sebastian, 80),(David,90), (Charlie,70)]  is going to be sorted by the grades of students. Two people in the grades have the same grade 80 - Sebastian and Earl. Earl is at index 0 while Sebastian is at index v3 in the unsorted list - Earl has a lower Index than Sebastian. If the list is sorted by a stable sorting algorithm, to maintain the relative order of all items, Earl would have a lower index than Sebastian in the sorted list. The expected sorted list under a stable sorting algorithm would be:       [(Charlie,70), (Earl,80), (Sebastian, 80),(David,90)], (UPDATED EXAMPLE)   However, in selection sort, as non-adjacent elements are swapped, the relative order of all items in the output may be disrupted. As such, the expected output…

1.Example: [5, 20, -5, 10, 3] Answer: [-5, 20, 5, 10, 3] 2.Example: [6, 5, 4, 3, 2, 1] Answer: [1, 5, 4, 3,  2, 6]  

Answer: Regardless of whether or not a list is sorted, the amount of times we iterate through the list is the same as the selection sort algorithm does not know if all the elements have been sorted without checking. It will still go through itself to find the smallest element and swap it with itself. The algorithm hence takes O(N^2) comparisons, so it has an O(N) complexity.Feedback: Last sentence O(N^2) not O(N)

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. …