jdsl.core.algo.sorts
Class ListInsertionSort

java.lang.Object
  |
  +--jdsl.core.algo.sorts.ListInsertionSort

public class ListInsertionSort
extends java.lang.Object
implements SortObject


Constructor Summary
ListInsertionSort()
           
 
Method Summary
 void sort(Sequence S, Comparator c)
          Perform insertion-sort, assuming the Sequence is based on a doubly-linked list. The sort proceeds by looking at each element in S, removing it, and inserting it in its place in a sorted sequence on the side.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

ListInsertionSort

public ListInsertionSort()
Method Detail

sort

public void sort(Sequence S,
                 Comparator c)
Perform insertion-sort, assuming the Sequence is based on a doubly-linked list.

The sort proceeds by looking at each element in S, removing it, and inserting it in its place in a sorted sequence on the side. Once S has been emptied, the temporary sequence is sorted; move all its elements back to S. This sort also demonstrates the use of a sentinel: to avoid unnecessary checks for the end of the temporary sequence, we insert an element as big as the biggest element, guaranteeing that no element will be inserted after it. This element is removed before copying back into S, to avoid changing S's contents.

Specified by:
sort in interface SortObject
Parameters:
S -  
c -