Sorting algorithms - Questions and answers

Here are some good examples of the questions that we might be asked during the coding interview.

Sorting algorithms - Q&A

Q1: Why does Bubble sort have O(n) as best case time complexity, while the average and worst case is O(n^2)?

A1: Because, in the Bubble sort implementation here, we have a boolean flag called 'swapped' that will end the iteration after the first traverse if the list is already sorted. 

In the case the list is already sorted, there will be only one iteration, after which the 'swapped' boolean flag will remain false, and the sorting process will end.

Q2: Why the Insertion sort has all three (best, average, and worst) cases of O(n^2)?

A2: When we have a look at the implementation here, we see that no matter if it is an already sorted list or unsorted, the same steps will occur. We would still need to traverse and compare all the elements with each other, but no swap will occur.

Q3: Why is Insertion sort good for a sorted or partially sorted sequence of elements? (Can you explain the best case time complexity of O(n) of the Insertion sort?)

A3: Based on the approach that we are using for the Insertion sort here, if the list is already sorted, we will just traverse through the input list once and no shifting of elements will occur.
We will check if the current element is smaller than the first element inside the unsorted array, and we will determine that it is not smaller, and we will do nothing.
We'll pick the next element inside the unsorted part of the array, and do the same.
So just a comparison of the current element with the first element of the sorted part will occur, nothing more.

In case there are only a few elements that need to be put at the correct position (partially sorted input list), the time complexity will still be considered as O(n).

Q4: Why does Merge sort have all three cases (best, average, and worst) as O(n log n)?

A4: It's because it always divides the array into two halves and takes linear time to merge the two halves. No matter if the input array is sorted or unsorted, the same steps and operations will be executed.

Q5: Why does Quick sort have the worst time complexity of O(n^2), while the best and average cases are O(n log n)?

A5: The efficiency of the Quicksort algorithm very much depends on the selection of the pivot element.

Let’s assume the input of the Quicksort is a sorted array and we choose the leftmost element as a pivot element. In this case, we’ll have two extremely unbalanced arrays. One array will have one element and the other one will have (N - 1) elements.

Similarly, when the given input array is sorted reversely and we choose the rightmost element as the pivot element, the worst case occurs. Again, in this case, the pivot elements will split the input array into two unbalanced arrays.

Except for the above two cases, there is a special case when all the elements in the given input array are the same. In such a scenario, the pivot element can’t divide the input array into two and the time complexity of Quicksort increases significantly.

We can avoid the worst-case in Quicksort by choosing an appropriate pivot element. In this section, we’ll discuss different ways to choose a pivot element.

The first approach for the selection of a pivot element would be to pick it from the middle of the array. In this way, we can divide the input array into two subarrays of an almost equal number of elements in it.

In some cases selection of random pivot elements is a good choice. This variant of Quicksort is known as the randomized Quicksort algorithm.

Another approach to selecting a pivot element is to take the median of three pivot candidates. In this case, we’ll first select the leftmost, middle, and rightmost elements from the input array. Then we’ll arrange them to the left partition, pivot element, and right partition.