in Algorithms
1,868 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??

in Algorithms
by
1.9k views

4 Comments

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

3 Answers

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

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) 

1 comment

konstant faktor

plesea remvoa Bikram Sir profile picture from yoru proflei
0
0
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