The Gateway to Computer Science Excellence
0 votes
40 views
If the number of records to be sorted is small, then ...... sorting can be efficient.
A. Merge B. Heap
C. Insertion D. Bubble

And why?
in Algorithms by (427 points) | 40 views
+1
Insertion because of high probability they number of inversion pairs well be less so majority of times it will take O(n)
0
but if given array is totally reverse then complexity will be o(n2) of insertion sort

Array to be sort : 9 8 7 6 5 4 3 2 1

Sorted Array: 1 2 3 4 5 6 7 8 9
0
Exactly, this is where my confusion lies..
+1
So you have considered 9 elements what is probability that that will be in reverse position 1/9!

How many cases are there when no element is in its right position and compare it with 1 elements in its right position , 2 elements in right position , 3 in right and so on

Probability is very low

 

Consider this 123

123

132

213

231

312

321

No element in its right position 2/6 atleast one in right position 4/6

So number of elements in its correct position will affect inversion pair

In short worst case is O(n$^{2}$) but probability that worst case will happen is less
0
Okay..got it, thanks.

Please log in or register to answer this question.

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
50,737 questions
57,384 answers
198,542 comments
105,341 users