Question

out of the following four:

1.Bubble sort
2. Insertion sort
3. Quicksort
4. Mergesort

a. Which sorting methods perform best and worst for data sizes ≥ 25,000 when
the input data is random?
b. Which sorting methods perform best and worst for data sizes ≥ 25,000 when
the input data is 90% sorted?
c. Which sorting methods perform best and worst for data sizes ≥ 25,000 when
the input data is reverse sorted?
d. Which sorting methods perform best and worst for data sizes < 25,000 when
the input data is random?
e. Which sorting methods perform best and worst for data sizes < 25,000 when
the input data is 90% sorted?
f. Which sorting methods perform best and worst for data sizes <25,000 when the
input data is reverse-sorted?
g. What is the relationship between the running time and the data size for each
of the sorting methods when the input data is random? (Try to come up with a function –
need not be ‘exact’, but close)
 Bubble sort
 Insertion sort
 Mergesort
 Quicksort
h. Conclude which sorting method is better suited for data size >25,000 and under
what input data pattern (random, almost sorted and reversely sorted)

Answer 1

A) when data size>=25000 or we can say for large data set with random values Merge sort is best among all it's worst case complexity is nlogn which is better than any of the algorithm.

bubble and inserion will perform worst in this case with complexity o(n²).

B)

if data is nealry sorted as in that case Insertion sort performs best in nearly O(n) complexity

Quick sort will perform worst because in each turn it's pivot will be at left most or right most position so overall complexity will be O(n²)

C)

Merge sort will perform best with complexity O(nlogn)

If data is reverse sorted then it will be worst case of Quick,bubble, insertion O(n²)

D)

if input data is random merge sort with worst case time O(nlogn) will perform best

and insertion , bubble will perform worse

but as data is very small so all the algos will work in nealry same .

E)

same as B data size doesn't affect it.

if data is nealry sorted as in that case Insertion sort performs bes in nearly O(n) complexity

Quick sort will perform worst because in each turn it's pivot will be at left most or right most position so overall complexity will be O(n²)

F)

Merge sort will perform best with complexity O(nlogn)

If data is reverse sorted then it will be worst case of Quick,bubble, insertion O(n²)

G) When input is random

Let n be data size

BUBBLE n²

Insertion n²

Mergesort nlogn

Quicksort nlogn on average but in worst case in can be n²

H)

Best algo with data>25000

Random	MERGE SORT
almost sorted	INSERTION SORT
Reverse Sorted	MERGE SORT