in Algorithms edited by
817 views
2 votes
2 votes
An array of size n is known to be sorted except for the 1st k elements and the last k elements, where k is a constant. which of the following algorithm is the best choice for sorting the array A?

Quick Sort or Insertion Sort?

given answer is the insertion sort, and i know it should be true too. but why not quick sort?

just apply quick sort two times--- one for the starting k elements and other for the end k elements(since we know the value of k), and it will take O(klogk) in average case and O(k^2) in the worst case. what’s wrong in that?
in Algorithms edited by
817 views

4 Comments

here out of N elements few elements are not sorted means array is almost sorted means insertion will give best case time complexity.
0
0

 quick sort best time is O (nlogn ) ...whereas insertion O (n) .

and as  said that it is almost sorted so we will go with insertion sort any day

0
0
What if the k elements which should actually be at the beginning are in the last k places and vice versa. Then your 2 quicksort approach will fail. It means that we need to apply the sorting algorithm over the complete array. And now the answer is obvious.
0
0

1 Answer

0 votes
0 votes
Insertion sort might be correct answer because :

As given in question as array of n elements with first and last k unsorted elements. so

let use Quick sort on it  T(n)=k.logk+(n-2k)^2 + k.logk = 2k.logk+n^2.

using insertion sort then  T(n)=2k^2+n.

 

so by this we can compare and say insertion sort is better as N>K.(and here we applied sorting on full array no matter which par is sorted or unsorted).

Although this is ambigious.

Related questions