What happens to the number of comparisons for each of the sort algorithms if the list is already sorted.
What will be an ideal response?
The processing of selection and bubble sort, as written, is independent of the original configuration of the items in the list, and therefore remain O(n2). But given that the data is originally sorted, the inner loop of the insertion sort will only make one comparison for each iteration, giving this situation the best case efficiency of O(n).
Because the quick sort algorithm, as written, chooses the first element in the partition as the partition element, each recursive step will only handle one element for an initially sorted list, and the efficiency degrades to the worst case scenario of O(n2). The merge sort guarantees equal partitions, and is O(n log n) in all cases, including this situation in which the elements are initially sorted.
You might also like to view...
Conditional formatting is a way to apply formatting to specific ________ based on a comparison to a rule set in the New Rule dialog box
A) controls B) properties C) fields D) data
____ is a way to allow Photoshop to create new frames automatically between two existing frames.
a. Filtering b. Editing c. Tweening d. Auto-filling
The modified insertion sort introduced in 1959 by D. E. Shell is known as the diminishing return sort.
Answer the following statement true (T) or false (F)
Joining a table to itself, is called a(n) ____________________.
Fill in the blank(s) with the appropriate word(s).