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.