Sorting Linked Lists


JavaListSort.html Code from java.util.Collections showing explicit code for java.util.Collections.sort()

Sorting option 1:   Destroy the incoming linked list to generate the sorted linked list
selectionSort         Helper method:  remove the largest object from the linked list
insertionSort          Helper method:  addOrdered, already developed

Sorting option 2:   leave the linked list structure alone and move the data among those node objects
selectionSort         For each node, starting from first, traverse to find the smallest value, swap with start, and move forward
insertionSort          For each node, traverse from front to find where it belongs, then move data value downstream

MergeSort             Merging lists as a technique for sorting (full web page)
MyComparable     Wrapper class to allow counting comparisons when java.util.Collections.sort uses x.compareTo(obj)
driverMain             Driving main to test the algorithms

Sorting option 1:  Final prototype:  add sorting methods to the linked list.  [.txt version]
ThreeRun.exe          Above program in a JSmooth .exe wrapper for Windows

Sorting option 2:   [.txt version]

ThreeSort.rtf           Option 1 code formatted as a two-page two-column document
ThreeRun.txt           Specimen execution of the program.

Enrichment material — not subject to examination    Sedgewick's Program 3.10, list insertion sort. [.txt version]   [self-documenting variables    txt]       Sorting example that uses Java iterators.  Note that it uses to capture comparison information. Implementing merge sort on top of the behaviors of the java.util.List interface.  [txt]   [rtf]
UtilMergeSort.exe  Directly executable version under Windows thanks to JSmooth

Iterating in Java  Article submitted to Dr. Dobb's Journal — compares sorting implementations based on iterators with direct implementations

MultiSort   [txt]  LinkedList implementation and driver exercising and comparing many sorting algorithms  Sample output, with commentary

Page last updated 2010-Jan-08 at 09:22