Suggest how any sorting algorithm can be augmented in a way to make the best-case count of its key comparisons equal to just n-1 (n is a list's size, of course). Do you think it would be a worthwhile addition to any sorting algorithm?

Question

Engineering

Jazlene Figueroa

5 June, 11:55

Suggest how any sorting algorithm can be augmented in a way to make the best-case count of its key comparisons equal to just n-1 (n is a list's size, of course). Do you think it would be a worthwhile addition to any sorting algorithm?

+2

Answers (1)

Know the Answer?

Yosef French · Answer 1

Before applying a sorting algorithm, There is a need to compare the adjacent elements of its input (if ai ≤ ai+1 for every i = 0, ..., n - 2, stop) before a sorting algorithm can be applied.

It slows down the algorithm, so for this reason it won't be a worthwhile addition.

This test is incorporated in the body of the algorithm by some sorting algorithms.