a Estimate how many times faster quicksort will sort an arra

a. Estimate how many times faster quicksort will sort an array of one million random numbers than insertion sort.

b. True or false: For every n > 1, there are n-element arrays that are sorted faster by insertion sort than by quicksort?

Solution

a)

The running time of quicksort algorithm are

best case: nlogn

average case : nlogn

worst case : n2

The running time of insertion sort is

best case: n

average case: n2

worst case : n2.

In worst case quicksort and insertion sort run in same time.

In average case quicksort is 166666 faster than insertion sort. (n2/nlogn)

In best case insertion sort is faster.

b)

True.

For smaller elements insertion sort is quicker.

In Insertion sort 1 element is placed at at time, which makes it faster for small range numbers.

Quick sort is used for larger range numbers.