Sorting
Sorting involves arranging a collection of items in order
- based on some property of the item (e.g. key)
- using an ordering relation on that property
Sorting occurs in many data contexts, e.g.
- arrays, linked-lists (internal, in-memory)
- files (external, on-disk)
Different contexts generally require different approaches
- sorting has been well-studied over the last 40 years
Why is sorting useful?
- speeds up subsequent searching
- arranges data in a human-useful way
(e.g. list of students in a tute class, ordered by family-name or id)
- provides intermediate step for advanced algorithms
(e.g. duplicate detection/removal, many DBMS operations)
We initially focus on sorting arrays of Item s in ascending order.
|