Test: Sorting - 1 - CUET Humanities MCQ

Best case time complexity of bubble sort is O(n).

f(n) = (n - 1) + (n + 2) ...
Hence, option 2 is the correct answer.

Best case is that in which the algorithm stops itself, once a pass makes no changes.
The only need is to do n comparisons. So, the best case complexity is O(n).

First Pass:
(5 1 4 2 8) (1 5 4 2 8), Here, algorithm compares the first two elements and swaps them.
(1 5 4 2 8) (1 4 5 2 8), Swap since 5 > 4
(1 4 5 2 8) (1 4 2 5 8), Swap since 5 > 2
(1 4 2 5 8) (1 4 2 5 8), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Bubble sort (seeking sort) is a simple sorting algorithm. In this, we compare each pair of adjacent items and swap them if they are in wrong order.
Number of comparisons in bubble sort = (n - 1) + (n - 2) + ... + (3) + (2) + (1) = n(n-1)/2
So, the complexity of bubble sort will be o(n²). Average comparisons will be o(n²).
Therefore, option 2 is the correct answer.

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has space complexity of O(n) in the worst case.

The worst case time complexity of selection sort is O(N²).

Selection sort's average case space complexity is O.

The worst case is when the elements are in reverse order. In this case, the maximum number of key comparisons is possible.
Hence, the total number of comparisons is

Insertion sort is a sort algorithm that keeps the left side of the array sorted until the whole array is sorted.