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?
  • not just business!
  • 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?