Sorting

• 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?
• graphics
• 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
• algorithm
• 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
• algorithm
• 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 any good!
• 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?