Question

4. Suppose you need to sort input data that is almost-sorted, meaning large stretches of the data are already in increasing order with occasional out-of-order elements. Argue that INSERTION-SORT would tend to be more time efficient than QUICKSORT in this situation.

Describe a scenario (other than sorting checks by check number or processing date) in which one might need to sort almost-sorted data.

Answer 1

When the data is almost sorted no doubt Insertion Sort is the best algorithm to sort the data.

We know that in the Insertion Sort we keep on moving from left to right ( from smallest toward largest ) and if we found that the element is less than its previous element, we place it in the correct position and move forward.

Now, when we know the array is almost sorted, we require to place very few elements to its correct location, as very few elements are in the wrong position.

Time Complexity of using Insertion Sort = O(n) where n is the no. of elements in the array

Now, in Quicksort, we know the minimum time complexity of the quicksort is O(nlogn). In the case when the array is almost sorted, the condition may arise that the pivot element we are choosing is bad selection.

Suppose we select the first element as pivot, it will return almost (n-1) as almost all elements are greater than pivot element. And in the next case, it will return (n-2), then (n-3) and so on.

So, in the case of an almost sorted array, the time complexity of the Quicksort will be O(n²).

Hence, Insertion Sort is preferable in the case of an almost sorted array.

Example:

1. Arranging students in the queue according to their height. The student can be guessed simply by watching that is he/she is too tall to be stand at last or at the beginning or in between.

2. Arranging books by their length on the shelf. We can easily determine the correct position of the book if one is inserted incorrectly.

3. Arranging notes (money) when a lot of money you are holding. We can place the incorrectly placed note to the correct place easily.

Leave a comment if face any problem.