The Gateway to Computer Science Excellence
0 votes
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
Insertion because of high probability they number of inversion pairs well be less so majority of times it will take O(n)
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
Exactly, this is where my confusion lies..
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







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 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
105,341 users