self doubt

Question

Best and Worst case input for:

1. Selection Sort

2. Insertion Sort

3. Merge Sort

4. Quick Sort

5. Bucket Sort

6. Counting Sort

7. Bubble Sort

Answer 1

Sorting algo	Worst case Occurs	Best case occurs
Selection sort,  insertion sort, Bubble sort	When given elements are already sorted in reverse order of your desired sorting, eg: you want to sort in ascending But given elements are in already descending	When given elements are already sorted in your desired sorting order.
Quick sort	When elements are sorted in either ascending or descending or all elements are equal	all other then given worst case is best case
merge sort	The worst case of merge sort will be the one where merge sort will have to do maximum number of comparisons. https://stackoverflow.com/questions/24594112/when-will-the-worst-case-of-merge-sort-occur	other then worst is best case
Counting Sort	not in GATE syllabus	not in GATE syllabus
Bucket Sort	not in GATE syllabus	not in GATE syllabus

 

Answer 2

SS and IS :: $ 54321 $

MS ::: it takes same time for best and worst (whatever input it is) $ O(n logn) $

QS :: Inputs are in ascending order or descending order or All elements are same.

BS ::  It performs at  $O(n^2)$ when all elements at allocated to the same bucket.

CS :: When range is too high. EX - $[1,1000,2,6]$

BS :: Sorted in reverse order. $[5,4,3,2,1]$