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.) Best sorting method Mergesort And worst is Insertion sort.

b.) When a data is sorted then Insertion is best method and worst is Quicksort.

c.) mergesort is best in this case and worst is bubble sort.

d.) When ever a data is given rendom then merge sort is best with O(nlogn) and Insertion/ bubble both are worst.

e.) Data is sorted then Insertion is best and quicksort is worst .

f.) Almost same as part c merge sort is best and worst is bubble.

h.) At the conclusion merge sort O(n logn) is best in all the case .

Bubble and Insertion sort O(n^2) are worst except in case when data is almost sorted then quick sort is worst .