- Discuss the advantages and disadvantages of various sorting routines
- Implement an array sort in Java
- This is where the instructor draws diagrams on the board and tries to illustrate how abstract concepts can be turned into code.
- This is a great opportunity to discuss 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).
- You are expected to be able to implement a sort given the algorithm in pseudocode.
- As we look at sorting algorithms, it is important to note that you usually don't have to write your own algorithms.
It does help greatly if you are able to translate a sort algorithm from pseudocode into the language you are using,
or more commonly, from one programming language into another.
- Different sorting routines have different advantages and disadvantages.
Some are simple to write, but those are often quite inefficient. Examples
of these simpler sorts include shell sort, bubble sort, and
selection sort. Some are optimized for dealing with files
that don't fit into memory all at once, such as mergesort, which is often
used together with other sorts. Some sorts use complex data structure
concepts to gain efficiency, such as heapsort and quicksort.
- some of the sorts we may look at:
- bubble sort (n2)
- my sort (n2)
- Wold sort (n2)
- selection (n2)
- insertion sort (n2)
- shell sort (n (log n)2)
- heap sort (n log n)
- quick sort (n log n)
- rob sort (not usually run due to time constraints on the existence of the universe)
- see Sort.java for sample sorts with timing information
- The Arrays class has built-in sorting methods
- see DevX.com article on sorting with Visual Basic code and general commentary
- University of British Columbia Computer Science sorting animations page
- The skeptical sorter