# Made Easy Test Series: Algorithm-Sorting

1 vote
721 views

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??

1
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).

0
In insertion sort , first k element is always sorted

right??
0
yes k can range from 1 to n where n is the size of array.
0
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??
0
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)

1 vote
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)

## Related questions

1
811 views
why not merge sort?we don’t swap in merge sort,we just create auxillary arrays and merge them by changing elements in the original array.should we consider that as a swap?
Consider a scenario of modified quick sort, where we have given an input sorted array A[1 .. . n], all elements of array are distinct and n >=3. Pivot is the median of set of 3 elements [First element, middle element, and last element]. What will be worst case time complexity of modified quick sort? a.O($n^{2}$) b.O(nlogn) c.O($n^{2}$logn) d.O(nloglogn)