sorter
Class SplitSort

java.lang.Object
  extended by sorter.SplitSort

public class SplitSort
extends java.lang.Object

Implements the splitsort, a quicksort in which comparisons are completely separated from the rest of the algorithm.

This class provides an implementation of the SplitSort : if given an array of integers, it will return, for each quicksort iteration, the comparisons that are necessary to continue. It allows the first and last step of a quicksort iteration (i.e generating comparison and splitting each array into three smaller ones) to be performed separately so as the comparisons to be gathered with those of other SplitSort instances (this is roughly the role of the Comparator class).

In order not to submit to many comparisons, it is possible to stop quicksort iterations for an array when its size is smaller than minimalSize. Since each comparison has a cost, it can be interesting to limit their number.

An array containing the sorted elements is generated in the end.

Author:
Leo Perrin (perrin.leo@gmail.com)

Field Summary
private  java.util.List<java.lang.Boolean> comparisons
          Contains true at the rank k if the k-th element of "greater" is actually greater than that of smaller: this.comparisons.get(k) = ( this.greater.get(k) > this.smaller.get(k) ), where '>' does not correspond to a comparison between integers but to the one given by a Comparator instance.
private  java.util.List<java.lang.Integer> greater
          Contains all the elements that are to be compared with their corresponding pivot.
private  java.lang.Integer minimalSize
          An array of a length smaller than minimalSize will not be sorted.
private  java.lang.Integer numberOfElements
          The number of elements contained in the initial list of arrays to sort.
private  java.util.List<java.lang.Integer> smaller
          Contains all the pivots used in the current iteration of the quicksort.
private  java.util.List<java.lang.Integer[]> sorted
          Contains the elements to be sorted in a list of arrays.
 
Constructor Summary
SplitSort(java.util.List<java.lang.Integer[]> init, java.lang.Integer min)
          Creates an instance of SplitSort and sets all of its attribute.
 
Method Summary
private  void addComparisons(java.lang.Integer[] tab)
          Fills the greater and smaller arrays with the content of the tabparameter.
 void display()
          Prints the content of sorted on the screen, using brackets [] to separate each array.
 void endIteration(java.util.List<java.lang.Boolean> comparisons)
          Performs the end of the quicksort iteration on all of the arrays contained in the attribute list sorted.
 java.lang.Integer[] getFinalResult()
          Returns the content of the sorted attribute transferred in a simple array.
 java.util.List<java.lang.Integer> getGreater()
          Get the value of greater.
 java.util.List<java.lang.Integer> getSmaller()
          Get the value of smaller.
 java.util.List<java.lang.Integer[]> getSorted()
          Get the content of sorted.
private  int insertion(int rank)
          Performs the end of a quicksort iteration on the array at the rank-th position in the sorter list and returns the number of arrays that have been inserted in it.
 void iteration()
          Performs the first part of an iteration of the quicksort on all the arrays contained in sorted.
 java.lang.Boolean notFinished()
          Returns true if the sorting of the elements in this instance of SplitSort is not finished.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

greater

private java.util.List<java.lang.Integer> greater
Contains all the elements that are to be compared with their corresponding pivot.

These inside this list are alleged to be greater than their counterpart in the smaller list. There is no mathematical basis whatsoever for this statement, it simply allows the result of a comparison to be easily understood : if comparisons.get(k) is true, then greater.get(k) IS greater than smaller.get(k). Otherwise, it is the contrary.


smaller

private java.util.List<java.lang.Integer> smaller
Contains all the pivots used in the current iteration of the quicksort.

The media whose ID are inside this list are alleged to be smaller than their counterpart in the greater list (this statement is explained in the description of greater).


sorted

private java.util.List<java.lang.Integer[]> sorted
Contains the elements to be sorted in a list of arrays.

Each array will go through an iteration of the quicksort. Using this list of arrays allows an iterative implementation of the quicksort rather than the "classical" recursive one.


comparisons

private java.util.List<java.lang.Boolean> comparisons
Contains true at the rank k if the k-th element of "greater" is actually greater than that of smaller: this.comparisons.get(k) = ( this.greater.get(k) > this.smaller.get(k) ), where '>' does not correspond to a comparison between integers but to the one given by a Comparator instance.


numberOfElements

private java.lang.Integer numberOfElements
The number of elements contained in the initial list of arrays to sort.


minimalSize

private java.lang.Integer minimalSize
An array of a length smaller than minimalSize will not be sorted.

Constructor Detail

SplitSort

public SplitSort(java.util.List<java.lang.Integer[]> init,
                 java.lang.Integer min)
Creates an instance of SplitSort and sets all of its attribute.

Creates an instance of SplitSort and sets the value of three of its attributes :

Parameters:
init - The list of array containing all the elements to be sorted as well as the current state of the sort.
min - The value to be assigned to minimalSize.
Method Detail

notFinished

public java.lang.Boolean notFinished()
Returns true if the sorting of the elements in this instance of SplitSort is not finished.

To determine whether the sort is over or not, it calculates the number (count) of elements contained in all arrays containing less than minimalSize elements. It stops when a bigger array is found, i.e (array.length > minimalSize). If count equals the number of elements to be sorted, then it means all elements have been sorted : it is finished ! Otherwise, well, it's not.

Returns:
true if the sort is over, false otherwise.

iteration

public void iteration()
Performs the first part of an iteration of the quicksort on all the arrays contained in sorted.

This means choosing a pivot in each array contained in sorted and generating all of the comparisons necessary to go further. This methods :

  1. Clears the content of its attributes comparisons, greater and smaller to avoid former results to interfere.
  2. Calls addComparisons(Integer[]) on each array contained in sorted.


addComparisons

private void addComparisons(java.lang.Integer[] tab)
Fills the greater and smaller arrays with the content of the tabparameter.

The comparisons necessary to perform a quicksort on the array "tab" are added to the attributes greater and smaller. greater contains all the element of tab while smaller is of the same size but contains only the pivot that will be used for the quicksort, i.e the first element of tab.

Parameters:
tab - The array that will go through an iteration of quicksort (using a pivot).

endIteration

public void endIteration(java.util.List<java.lang.Boolean> comparisons)
Performs the end of the quicksort iteration on all of the arrays contained in the attribute list sorted.

The end of the quicksort iteration corresponds to the splitting of all arrays contained in sorted in at least two parts. See the insertion(int) method's description for more details.

Parameters:
comparisons - A list of Boolean containing the results of the comparisons. Most of part this program's only purpose is to create this list...
See Also:
insertion(int)

insertion

private int insertion(int rank)
Performs the end of a quicksort iteration on the array at the rank-th position in the sorter list and returns the number of arrays that have been inserted in it.

This is done by splitting this array in three arrays :

If the pivot is actually the smallest or the greatest element of this array, only two arrays are created. The "old" array is removed from sorted.

Parameters:
rank - The array at the rank rank in the list sorted will be split in several parts.
Returns:
The number of arrays actually inserted.

getFinalResult

public java.lang.Integer[] getFinalResult()
Returns the content of the sorted attribute transferred in a simple array.

For each array in the sorted list, its elements are appended to a result list of Integer (initialized empty). Two loops are used : one iterates on the list and another iterates on the elements of each array.

Returns:
An array of Integer containing the identifiers of the media sorted.

display

public void display()
Prints the content of sorted on the screen, using brackets [] to separate each array.

This method is very useful when debugging to see how the sort evolves, but rather useless otherwise. The Comparator.display() method that uses this SplitSort.display() should be commented most of the time.


getGreater

public java.util.List<java.lang.Integer> getGreater()
Get the value of greater.

Returns:
the value of greater

getSmaller

public java.util.List<java.lang.Integer> getSmaller()
Get the value of smaller.

Returns:
the value of smaller

getSorted

public java.util.List<java.lang.Integer[]> getSorted()
Get the content of sorted.

Returns:
the value of sorted