BACK

Sorting Linked Lists

NEXT

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:
ThrowAway3.java  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:
ThrowAway3.java   [.txt version]
ThreeRun.exe

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

ListSortExample.java    Sedgewick's Program 3.10, list insertion sort. [.txt version]   [self-documenting variables    txt]

ListSort.java       Sorting example that uses Java iterators.  Note that it uses MyComparable.java to capture comparison information.

UtilMergeSort.java 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