- sorting - putting things in order
- ascending A-Z, descending Z-A
- to a computer, alphabetic order or numeric order is really the same thing
(characters treated as ASCII codes)
- why do it?
- not just business!
- game playing
- Python has a sort method for lists already!
- list.sort() sorts ascending and returns None !
- why would you need to worry about it?
- you may be using a language which isn't Python
- You may need to sort a 2-dimensional list, which sort does not work on
- it's good exercise with lists!
- Selection sort
- repeat for n-1 passes (n is number of elements)
- find the largest in the unsorted list
- swap it with the item at the right end of the unsorted list
- unsorted list gets smaller every pass
- lots and lots of comparisons n*(n-1)/2
- not too many swaps n-1
- quick sort
- chooses a pivot number from the items in the list - which one? does not matter
- uses the pivot to partition the list into two smaller lists, one less than the pivot
one greater than the pivot
- put the pivot between the two lists - it is sorted
- use quicksort algorithm on the two partitions, independent of each other
- when get down to empty list or 1-element list, stop
- hope to pick good pivot, partitions evenly balanced, but will work even if it's not
- does not work quickly on list already sorted, partitions are always unbalanced
- number of comparisons less, about n*log(n)
- number of passes about log(n)
- considerable data movement making partitions
- often implemented recursively
- philosophy of algorithms
- computers do not solve problems with a "poof!" and a magic formula
- algorithms "nibble away" at problems, making them smaller a small step at a time
- computers are patient, they don't mind repeating the same algorithm a million times if needed
- in any algorithm, look for how it reduces the "problem space" - if it doesn't, it isn't
- sorts are better or worse based on context
- is the data already almost sorted? is the data totally random? unique or duplicated?
- are the items small or large? (hard to move or easy?)
- is there enough room to keep all the data in RAM?
- compare sorting algorithms by number of comparisons made, number of data moves made
and amount of extra RAM needed
- also by complexity - is it hard to implement?