1,873 views
3 votes
3 votes

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

3 Answers

1 votes
1 votes
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)
0 votes
0 votes

Its mentioned that first and last “k” elements are unsorted. So insertion sort compares first k and leaves the middle and then again compares the last k elements. Total time taken 0( kn+kn)= 0(2kn)= 0(n) 

0 votes
0 votes

Here the catch. Both Insertion and bubble sort would have been the best algorithm IF AND iF the whole element was sorted in ascending order. Hence it can’t be the answer;

Selection sort has time complexity of O(n^2), which is independent of whether the array is sorted or not.

But Since the first k and last k elements are not sorted and if choose the first element as pivot element then quick sort works just like merge sort hence it’s time complexity will be O(nlogn) which is the best among all the given algorithm, 

Hence opt C is correct!

Related questions

1 votes
1 votes
5 answers
1
hitesh159 asked Apr 16, 2019
2,026 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 sw...
1 votes
1 votes
1 answer
2
0 votes
0 votes
0 answers
4
Abhishek Kumar 38 asked Dec 19, 2018
612 views
Which of the following sorting algorithm represented by above code?