search
Log In
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??

in Algorithms 721 views
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 Answer

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)

Related questions

0 votes
3 answers
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?
asked Apr 16, 2019 in Algorithms hitesh159 811 views
2 votes
3 answers
2
1.8k views
Consider an array with the following elements: 12, 18, 17, 11, 13, 15, 16 and 14. How many element will change their initial position after completion of partition algorithm by choosing 15 as pivot?
asked Jan 2, 2016 in Algorithms Sandeep Singh 1.8k views
1 vote
4 answers
3
781 views
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)
asked Jan 21, 2019 in Algorithms newdreamz a1-z0 781 views
1 vote
1 answer
4
571 views
Is there any standard way to sort in Quicksort or what all matters is PIVOT getting placed at its correct position thats it? I mean if only pivot condition then 3!*3! for both left and right elements but if any standard then each of the left and right parts ... fixed way that after 1st pass the array will remain as it is and only those elements compared with the minimum will be getting swapped.
asked Dec 26, 2018 in Algorithms Markzuck 571 views
...