Made Easy Test Series: Algorithm-Sorting

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)$Insertion Sort

$b)$Bubble sort

$c)$Quicksort

$d)$Selection sort

---

Why not quick sort will be answer? Quick Sort sorts part by part using pivot. So, why not will it be answer?? How do we know it is asking for almost sorted array??

Comments

1. Start  loop from 1 to k
2. pick an element and compare with the elements in the sorted list and place them in the sorted list.
3. now loop for the last k elements.
4. pick an element and compare with the elements in the sorted list and place them in the sorted list.

Well it looks like we are doing insertion sort algo. and its T.C. will be O(n*k) and since k is constant it will be O(n).

---

In insertion sort , first k element is always sorted

right??

---

yes k can range from 1 to n where n is the size of array.

---

See, here some middle elements are sorted and first k elements not sorted.

But in insertion sort, first some elements will always be sorted. Isnot it??

---

In insertion sort the main thing is ...we place an element in a sorted list and by doing this the sorted list grows till all the elements of array are sorted.

You can swap the first k elements with the sorted list such that in the array sorted elements are first and after that there are 2k elements which are unsorted.

Then apply insertion sort.
T.C = O(k)  for swap + O(n*2k)   = O(n)

Answer 1

Insertion sorting sort all the elements of the array by traversing to each elements in the given array.

But question is given that first k elemenets and last k elements are not sorted so,

it will quick sort who select last elements as pivot and place pivot elements to its correct position

and at left of pivot and right of pivot, elements r still unsorted ........

time compexity is O(n-1)=O(n)

so answer is option (c)