Sorting

• The items might be in an array or in some other kind of collection
• The order can be ascending or descending

Importance of sorting

• Sorting is a fundamental part of many tasks
• Sorting is often required for the efficient performance of other tasks (e.g. searching a phonebook)

What kind of order ?

• It depends on what items you happen to be sorting
• The two most common orders are numerical order (for numbers)
  and lexicographical order (for strings)

Lots of algorithms

• We'll look at Selection Sort -- simple but relatively inefficient
• There are several dozen commonly used sorting algorithms, each with its own advantages and disadvantages

Analysis of Algorithms

• How fast is it?
• An important conceptual tool for thinking about algorithms in the abstract
• useful for choosing a good algorithm for a particular task