Skip to main content

Section 8.13 Sorting Efficiency

To figure out how efficient the Selection Sort algorithm is, we will analyze the worst case. For units of work, we will consider comparisons and swaps - the two key operations in a sort. This video works through how much work there is for a Selection Sort on a list of 4 items:
Animation used by permission of Virginia Tech
If we did the same work for a selection sort on a list of 100 things (\(n = 100\)), it would look like:
Table 8.13.1.
Step Comparisons Swaps
1 99 1
2 98 1
3 97 1
97 3 1
98 2 1
99 1 1
The total swaps would be 99 steps times 1 swap each = 99. Expressed in terms of \(n\) we could say it is \(n - 1\) swaps.
The total comparisons would be 99 + 98 + 97 + … + 3 + 2 + 1 or \((n - 1) + (n - 2) + (n - 3) + + 3 + 2 + 1\text{.}\) So what does that equal? There is a trick to find out - pair up the first item and the last, then the second item and next to last and so on. Each pair of items sums to \(n\text{:}\)
Since there were \(n - 1\) numbers to start with, there will be \(\frac{n - 1}{2}\) pairs, each of which adds to \(n\text{.}\) Multiplying the number of pairs by the sum of each pair gives us the total: \(\frac{n - 1}{2} \cdot n = \frac{n^2 - n}{2} = \frac{n^2}{2} - \frac{n}{2}\text{.}\)
Overall, our work will be given by:
\(\text{Total work} = \text{Comparisons} + \text{Swaps}\)
Or:
\(\textrm{Total work} = (\frac{n^2}{2} - \frac{n}{2}) + (n-1) = \frac{n^2}{2} + \frac{n}{2} - 1\)
Since for Big-O purposes, all we care about is the class of the dominant term, in this case \(\frac{n^2}{2}\text{,}\) we will say that Selection Sort is \(O(n^2)\) (Quadratic). A similar process can be used to show that so is Insertion Sort.
Selection and Insertion Sort are Quadratic - \(O(n^2)\text{.}\)
You have attempted of activities on this page.