Suppose the data consisted of nothing more than the values 0 and 1 alternating:

Question

Suppose the data consisted of nothing more than the values 0 and 1 alternating:

0 1 0 1 0 1 0 1 0 1 ......

We have the following sorts to consider: Insertion, Selection, Bubble, Merge, Quick, Heap

What time would you expect from these sorts, given that particular data? (Do any of them work significantly better, as opposed to totally random data?)

NOTE: Consider how the sorts themselves behave -- do not consider special code being written to handle this particular input. Also NOTE: The Quick sort must not only partition its data, but recursively sort each partition (here unaware of duplicated values)

Explanation / Answer

This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be 'insert'ed in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort.

The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst case complexity are of (n2), where n is the number of items.

At best time O(n), worst time O(n2) and average time O(n2) expect from insertion sort, given that particular data.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.