Figure 7.5 shows the best-case number of swaps for Selection Sort as (n). This is because the

Figure 7.5 shows the best-case number of swaps for Selection Sort as Θ(n).

This is because the algorithm does not check to see if the ith record is already in the ith position; that is, it might perform unnecessary swaps.

(a) Modify the algorithm so that it does not make unnecessary swaps.

(b) What is your prediction regarding whether this modification actually improves the running time?

(c) Write two programs to compare the actual running times of the original Selection Sort and the modified algorithm. Which one is actually faster?

Transcribed Image Text:

Comparisons: Best Case Average Case Worst Case Swaps: Best Case Average Case Worst Case Insertion Bubble Selection (n) (n) (n) (n) (n) (n) (n) 0 (n) (n) (n) (n) 0 (n) (n) (n) e(n) e(n) Figure 7.5 A comparison of the asymptotic complexities for three simple sorting algorithms.