826 views
Array of n elements with first 10 and last 50 elements unsorted..find an algo which runs faster a)merge sort b)quick sort c)insertion sort d)bubble sort Explain

Insertion Sort.

To sort the first 10 elements- maximum $O(10^2) = O(1)$ time complexity.

Next, $n-60$ elements take $\Theta(n-60)$ time as these would involve no shifting among themselves)

Final 50 elements take $\Theta(50n) = \Theta(n)$ time in worst case to place each of the 50 elements in position.

So, totally $\Theta(n)$.
edited by
0

Insertion Sort

the elements are

 10 elements unsorted n-60 elements sorted 50 elements unsorted

so we can perform shift of these 10 elements to the end which will take Θ(n) time  and now we can perform insertion sort on complete array and here array is almost sorted so it will take overall Θ(n) time.

@ Arjun sir ...pls check this concept

0
Nopes. That is wrong. Because we don't know the fact that only the first 10 and last 50 elements are unsorted. We blindly apply a sorting mechanism. In this sorting mechanism, we have to find the complexity for the given input.
0
Proof that O(N) time is needed !

We can have array like

10 Elements||| Sorted N-60 Element ||| 50 Elements

It is not said that First 10 elements are smallest 10 elements or last 50 elements are largest 50 elements ! They can be arbitary.

Using merge sort we can get 3 sorted list in O(1) time (50log50 & 5.

Then merging takes O(N) time using merge routing !

Use

1. Merge sort for sorting those 10 & 50.

2. Merge sort for merging sorting list. Is my approach right @Arjun ?
0
But you need to modify merge sort algorithm to handle this special input. Actually question here means that, we give a particular sorting algorithm (without knowing what will be the input) and then this particular input is given.
0

@arjun sir how did you take the last step to sort 50 element,

"Final 50 element take Θ(50n)=Θ(n)​ Θ(50n)=Θ(nΘ(50n)=Θ(n)​

0
@Arjun Sir, Can't we do like that

Through Merge Sort:-

1> sort first 10 elements which take 10log10 = O(1) then

2> Sort last 50 elements which take 50log50 = O(1) then

At this stage, we have three sorted lists now apply merge procedure which takes

O(n+10) first and middle list which is O(n) and then O(n+50) which is O(n) time

Through Insertion Sort:-

Since the constant amount of elements are unsorted and the rest of the array is sorted so we can consider the array as almost sorted, and since the almost sorted array is the best case time complexity of the insertion sort which is O(n).

So from above two procedure can we say that both insertion sort and merge sort both can be the answer to the above question?

Whether first i elements or last k are unsorted, it is ultimately an unsorted array only. So it is not the best case. It may be average case or worst case, since we don't know thw inputs. Comparing all the sort given in the option it is either Merge sort or quick sort. Correct me, if I missed something.

0
Keith kr Sir I too dont know the answer lets see what arjun sir say about it
+1
First 10 and last 50 elements are unsorted. We just have a constant number of unsorted elements. So, you can see which algorithm would be the best here. The best algorithm would be able to run in O(n) time.
0
as the first 10 and last 50 are unsorted and remaining sorted:

we can have ex: n= 10, first 3 ,last 4 unsorted and remaing 3 sorted;

( 3 1 6)  4 7 9 ( 5 2 8 0)

it will anyhow require us to sort all of them at some point in time: and faster will definately be merge sort in that case for worst case.

correct me
0
sir how O(n)?
merge sort as its average or worst case complexity is better than that of quick sort
0
Try insertion sort.
0
sir, in que. first 10 elements & last 50 elements was already sorted......but how can you say it is an finite array....we have no info. about unsorted elements in between sorted elements. Is it 1,2,3, or don't know how many.

& insertion sort is better to choose for already or partially sorted array.....but it is not useful for array with large no. of elements.

+1
first 10 and last 50 are unsorted- so rest are sorted. (the number of elements is still finite but not constant).
0
sorry i read it wrongly, yes sir u r right. first 10 and last 50 are unsorted.

But what about 2nd point.............if there is only 1 or 2 elements in sorted array....then insertion sort is not useful in this case.........because list is not almost sorted.& in this case insertion will take O(n^2).

+1 vote
1
2