Question

10. If the given input array is sorted or nearly sorted, which of the following 1 point
algorithm gives the best performance?​

Answer 1

Answer:

Insertion sort takes linear time when input array is sorted or almost sorted (maximum 1 or 2 elements are misplaced). All other sorting algorithms mentioned above will take more than lienear time in their typical implementation.

Explanation:

Many sorting algorithms are available, but the one which is best suited for the almost sorted array is the insertion sort.

Which of the following stable sorting algorithm takes the least time when applied to an almost sorted array? Explanation: Insertion sort takes linear time to sort a partially sorted array. Though merge and quick sort takes O(n*logn) complexity to sort, merge sort is stable.

Insertion sort is the clear winner on this initial condition. Bubble sort is fast, but insertion sort has lower overhead. Shell sort is fast because it is based on insertion sort. Merge sort, heap sort, and quick sort do not adapt to nearly sorted data