What does it mean for a sorting algorithm to be stable? Why? Is InsertionSort stable?
|
23
|
0
|
A1

175 Words
|
2 minutes
Answer: For a sorting algorithm to be stable, it is expected that the relative order of items will remain the same, i.e. when 2 or more items have the same value in an unsorted list, the one which had a lower index in the unsorted list is first.   During the insertion process, when an element (pivot) is being compared to the sorted elements of the list, it will only move past elements which are greater than it, not elements which are less than or equal to it. Hence, insertion sort is stable because when 2 or more items have the same value, the relative order of items remains unchanged.    Alternative Answer: For a sorting algorithm to be stable, it is expected that the relative order of items will remain the same. Insertion sort is stable because of the strict < (Should be >) 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 <=…
A1Insertion SortingSolvedSorting
What does it mean for a sorting algorithm to be incremental? Why? Is Insertion Sort incremental? Why and when? (isn’t the answer for this meant to be incremental)
|
22
|
0
|
A1

124 Words
|
A minute
Answer: An algorithm is incremental if it does not need to recompute everything after a small change (like a new element is added).  Insertion sort traverses through unchanged element, stores the new element into a temporary variable and loop from right to left to find the correct position. The new element is then inserted to the list. Insertion sort is incremental when the new element is added at the back of the list.   To add on:   Because all original sorted elements would not move as they stop on the first comparison, only when it reaches the new element (last element) does a sequence of swapping and comparing occur, and since it is the last element, the sorting algorithm knows the list is already sorted.  
A1Insertion SortingSolvedSorting
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?
|
20
|
0
|
A1

63 Words
|
A minute
1. Example: [5, 20, -5, 10, 3] [5, 20, -5, 10, 3] because in the first iteration, it compares 5 and 20, and since 20 is greater than 5 it stays in the same position.   2. Example: [-7,-1,-4,4,5,6] Answer:   [-7,-1,-4,4,5,6] -> List remains unchanged as -7 at index 0 is smaller than index 1.
A1Insertion SortingSolvedSorting