Sorting

• Demonstrate sorting techniques
• Utilize passing by reference

• We will discuss various sorting algorithms in class
• This is where I draw diagrams on the board and try to illustrate how abstract concepts can be turned into code
• This is also a great opportunity to demonstrate the order of algorithms
• You are not expected to be able to recreate the sorting algorithms out of thin air during the rest of this course, but hopefully some of the concepts will stick
• You are expected to be able to modify the given sort algorithms to fit new situations you run into - this generally involves changing the data type used and modifying the comparison code (where it is decided which item comes first)
• The sorts we will hopefully have time to look at:
  • bogosort (also called robsort, stupidsort, slowsort) (n * n!)
  • bubble sort (n²)
  • my sort (n²)
  • Wold sort (n²)
  • selection (n²)
  • insertion sort (n²)
  • shell sort (n (log n)²)
  • heap sort (n log n)
  • quick sort (n log n)
• See sort.cpp for sample sorts with timing information
• Example of sort runtimes: Sorting work array using bubble sort - elapsed time: 13722ms Sorting work array using my sort - elapsed time: 13426ms Sorting work array using Wold sort - elapsed time: 7754ms Sorting work array using selection sort - elapsed time: 4266ms Sorting work array using insertion sort - elapsed time: 3366ms Sorting work array using shell sort - elapsed time: 1365ms Sorting work array using merge sort - elapsed time: 15ms Sorting work array using heap sort - elapsed time: 14ms Sorting work array using quick sort - elapsed time: 9ms
• Since heapsort and quicksort appear to be tied for the best algorithm, many people wonder which algorithm is the "best" one to use. In general, heapsort is safer than a very simple quicksort implementation. Quicksort has a weakness in worst case situations that take its order to n². Heapsort doesn't degrade as much in worst-case scenarios. The weakness in Quicksort is due to the choice of a pivot. There are quicksort implementations that take this into account and can avoid most worst-case situations. The structure of quicksort also makes it easy to use other sort routines to sort subsections of its data, and parallelization shouldn't be too difficult either.

• See example program that covers classes, vector, heapsort, and file input
• See parts.txt: sample data for example03.cpp program