CIS 250 - Sorting

Objectives

• demonstrate sorting techniques
• utilize passing by reference

Sorting

• 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
• see DevX.com article on sorting with Visual Basic code and general commentary
• 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.

Example of several techniques covered up to this point (including sorting)

• parts.txt: file with sample data
• example program to be discussed in class