edited by
820 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?
edited by

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

0 votes
0 votes
0 answers
2
Abhishek Kumar 38 asked Dec 19, 2018
612 views
Which of the following sorting algorithm represented by above code?
0 votes
0 votes
2 answers
3
Somoshree Datta 5 asked Oct 20, 2018
1,587 views
Consider the following scenario during insertion sort when the array looks like the following:{25,75,95,125,80,5,10}The number of comparisons that it will further take fo...