previous |
start |
next
Analyzing the Performance of the Selection Sort Algorithm
- The formula for the number of visits in the
selection sort algorithm is
(1/2) n2 + (5/2) n - 3.
- For large values of n, the latter terms
in the formula have no significant contribution, so we just ignore
them.
|
n
|
(1/2)
n2
|
(5/2) n - 3
|
|
1000
|
500,000
|
2,497
|
|
2000
|
2,000,000
|
4,997
|
- When comparing the ratios of counts for
different values of n, the coefficient (1/2) cancels
out.
- We simply say "The number of visits is of order
n2" and use big-Oh notation: The number of
visits is O(n2).
- For selection sort, doubling the number of
elements increases the time needed for sorting
fourfold.
- If a 1000 element vector takes 11 seconds, a
100,000 element vector will require over 3 hours!
previous |
start |
next