ME_test_series

Question

An array A of size n is known to be sorted except for the first k elements and the last k elements, where K is a constant. Which of the following algorithms will be the best choice for sorting the array A?

A.) quick sort

B.) insertion sort

C.) selection sort

D.) bubble sort

I can’t understand how can insertion sort be better in this case?

Comments

Kunal Kadian

k may be very small and n may be very large.

what's the problem ??

---

yes, insertion

see this https://gateoverflow.in/55340/if-list-is-almost-sorted-and-largest-element-wrongly-placed

---

@kumar.dilip I am asking what if k very small than n, say n= 1e5 and k = 10 Then the array is. Not almost sorted.. a huge chunk of array is unsorted.. So for any k, hoe can we say that insertion sort is best? Shouldn't some more information between k and n be mentioned so that we can be sure that n,k are very close and therefore array is almost sorted.