|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectsorter.SplitSort
public class SplitSort
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.
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 |
---|
private java.util.List<java.lang.Integer> greater
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.
private java.util.List<java.lang.Integer> smaller
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).
private java.util.List<java.lang.Integer[]> sorted
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.
private java.util.List<java.lang.Boolean> comparisons
private java.lang.Integer numberOfElements
private java.lang.Integer minimalSize
Constructor Detail |
---|
public SplitSort(java.util.List<java.lang.Integer[]> init, java.lang.Integer min)
Creates an instance of SplitSort and sets the value of three of its attributes :
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 |
---|
public java.lang.Boolean notFinished()
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.
public void iteration()
This means choosing a pivot in each array contained in sorted and generating all of the comparisons necessary to go further. This methods :
addComparisons(Integer[])
on each array contained in sorted.
private void addComparisons(java.lang.Integer[] tab)
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.
tab
- The array that will go through an iteration of quicksort (using a pivot).public void endIteration(java.util.List<java.lang.Boolean> comparisons)
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.
comparisons
- A list of Boolean containing the results of the comparisons. Most of part this program's
only purpose is to create this list...insertion(int)
private int insertion(int rank)
This is done by splitting this array in three arrays :
rank
- The array at the rank rank in the list sorted will be split in several parts.
public java.lang.Integer[] getFinalResult()
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.
public void display()
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.
public java.util.List<java.lang.Integer> getGreater()
public java.util.List<java.lang.Integer> getSmaller()
public java.util.List<java.lang.Integer[]> getSorted()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |