The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+6 votes
749 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
asked in Algorithms by Boss (14.3k points) | 749 views

3 Answers

+3 votes
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)$.
answered by Veteran (359k points)
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?
0 votes

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.

answered by Loyal (6.1k points)
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)?
0 votes
merge sort as its average or worst case complexity is better than that of quick sort
answered by (23 points)
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.

please clarify ?
+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).


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,147 questions
47,708 answers
147,675 comments
62,405 users