Sorting and Efficiency
This section is based on parts 13, 14 and 15 of the notes,
Sorting Arrays, part 1,
Sorting Arrays, part 2,
and
Efficiency.
Practical exercises supporting this section are in
Exercise sheet 6.
When you have completed this section you should be able to:
- Understand how various sorting algorithms work on indexable data
structures
- Know what is meant by "sorting in place"
- Use the built-in sorting methods provided as part of Java's library
- Understand what is meant by the "natural order" of a class of objects
- Appreciate that the algorithm used to solve a problem will be the
main factor in how fast it is solved
- Understand the phrases "best case", "worst case" and "average case"
when applied to algorithms
- Understand how an algorithm which works by repeatedly halving the
problem size results in an execution time proportional to the
logarithm of the problem size
- Appreciate the "big-O" notation as a way of categorising algorithm
efficiency
Matthew Huntbach
Last modified: 30 June 2006