Consider the list below. What happens to the number of comparisons for each of the sort algorithms if the list is already sorted.

3 8 12 34 54 84 91 110


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.

Computer Science & Information Technology

You might also like to view...

100BaseX represents several Fast Ethernet variations.

Answer the following statement true (T) or false (F)

Computer Science & Information Technology

In 1995, the government stopped paying for backbone transmission lines requiring the Internet to be self-supporting

Indicate whether the statement is true or false

Computer Science & Information Technology

An entity stores data about people, places, or things

Indicate whether the statement is true or false

Computer Science & Information Technology

The art of bringing an object to life by giving it the appearance of motion or activity is ____.?

A. ?simulation B. ?animation C. ?transition D. ?HTML5

Computer Science & Information Technology