 |
0.8
Sorting media using crowdsourcing.
|
Doxygen |
 |
|
0.8
Sorting media using crowdsourcing.
|
Doxygen |
|
Implements the splitsort, a quicksort in which comparisons are completely separated from the rest of the algorithm. More...
Public Member Functions | |
| SplitSort (List< Integer[]> init, Integer min) | |
| Creates an instance of SplitSort and sets all of its attribute. <../..> | |
| Boolean | notFinished () |
| Returns true if the sorting of the elements in this instance of SplitSort is not finished. <../..> | |
| void | iteration () |
Performs the first part of an iteration of the quicksort on all the arrays contained in sorted. <../..> | |
| void | endIteration (List< Boolean > comparisons) |
Performs the end of the quicksort iteration on all of the arrays contained in the attribute list SplitSort.sorted. <../..> | |
| Integer[] | getFinalResult () |
Returns the content of the sorted attribute transferred in a simple array. <../..> | |
| void | display () |
Prints the content of SplitSort.sorted on the screen, using brackets [] to separate each array. <../..> | |
| List< Integer > | getGreater () |
Get the value of greater. <../..> | |
| List< Integer > | getSmaller () |
Get the value of smaller. <../..> | |
| List< Integer[]> | getSorted () |
Get the content of sorted. <../..> | |
Private Member Functions | |
| void | addComparisons (Integer[] tab) |
Fills the greater and smaller arrays with the content of the tabparameter. <../..> | |
| 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. <../..> | |
Private Attributes | |
| List< Integer > | greater |
| Contains all the elements that are to be compared with their corresponding pivot. <../..> | |
| List< Integer > | smaller |
| Contains all the pivots used in the current iteration of the quicksort. <../..> | |
| List< Integer[]> | sorted |
| Contains the elements to be sorted in a list of arrays. <../..> | |
| List< 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. <../..> | |
| Integer | numberOfElements |
| The number of elements contained in the initial list of arrays to sort. <../..> | |
| Integer | minimalSize |
An array of a length smaller than minimalSize will not be sorted. <../..> | |
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.
Definition at line 20 of file SplitSort.java.
| sorter.SplitSort.SplitSort | ( | List< Integer[]> | init, |
| 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 :
| 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. |
Definition at line 81 of file SplitSort.java.
{
this.sorted = new ArrayList<Integer[]>();
this.greater = new ArrayList<Integer>();
this.smaller= new ArrayList<Integer>();
this.comparisons = new ArrayList<Boolean>();
this.minimalSize = min;
this.numberOfElements = 0;
for (Integer[] array : init)
{
this.sorted.add(array.clone());
this.numberOfElements += array.length ;
}
}
| void sorter.SplitSort.addComparisons | ( | Integer[] | tab | ) | [private] |
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.
| tab | The array that will go through an iteration of quicksort (using a pivot). |
Definition at line 154 of file SplitSort.java.
| void sorter.SplitSort.display | ( | ) |
Prints the content of SplitSort.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.
Definition at line 281 of file SplitSort.java.
{
for (Integer[] tab : this.sorted)
{
System.out.print(" [ ");
for (Integer i : tab)
{
System.out.print(i);
System.out.print(" ");
}
System.out.print("] ");
}
}
| void sorter.SplitSort.endIteration | ( | List< Boolean > | comparisons | ) |
Performs the end of the quicksort iteration on all of the arrays contained in the attribute list SplitSort.sorted.
The end of the quicksort iteration corresponds to the splitting of all arrays contained in sorted in at least two parts. See the SplitSort.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... |
Definition at line 176 of file SplitSort.java.
{
int i=0;
this.comparisons = comparisons;
while (i<this.sorted.size())
if ( this.sorted.get(i).length > this.minimalSize)
i+=insertion(i);
else
i+=1;
}
| Integer [] sorter.SplitSort.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.
Integer containing the identifiers of the media sorted. Definition at line 264 of file SplitSort.java.
| List<Integer> sorter.SplitSort.getGreater | ( | ) |
Get the value of greater.
greater Definition at line 306 of file SplitSort.java.
{ return this.greater; }
| List<Integer> sorter.SplitSort.getSmaller | ( | ) |
Get the value of smaller.
smaller Definition at line 314 of file SplitSort.java.
{ return this.smaller; }
| List<Integer[]> sorter.SplitSort.getSorted | ( | ) |
Get the content of sorted.
sorted Definition at line 322 of file SplitSort.java.
{ return this.sorted; }
| int sorter.SplitSort.insertion | ( | int | rank | ) | [private] |
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.
| rank | The array at the rank rank in the list sorted will be split in several parts. |
Definition at line 206 of file SplitSort.java.
{
// initialisations
Integer[] tab = this.sorted.get(rank);
int pivot = tab[0];
List<Integer> small = new ArrayList<Integer>() ;
List<Integer> great = new ArrayList<Integer>() ;
int pivotIndex = this.smaller.indexOf(pivot);
// creation of the arrays to add
for (int j=0; j<tab.length; j++)
{
int g = this.greater.get(pivotIndex+j);
int s = this.smaller.get(pivotIndex+j);
if (this.comparisons.get(pivotIndex+j))
{
if (s!=pivot) small.add(s);
if (g!=pivot) great.add(g);
}
else
{
if (g!=pivot) small.add(g);
if (s!=pivot) great.add(s);
}
}
Integer[] great_array = great.toArray(new Integer[0]);
Integer[] array_pivot = { pivot };
Integer[] small_array = small.toArray(new Integer[0]);
// removing and insertion of the right arrays
this.sorted.remove(rank);
int ins = 1; // number of arrays inserted (at least the pivot)
if (great_array.length>0)
{
this.sorted.add(rank,great_array);
ins++;
}
this.sorted.add(rank,array_pivot);
if (small_array.length>0)
{
this.sorted.add(rank,small_array);
ins++;
}
// the number of arrays inserted is returned
return ins;
}
| void sorter.SplitSort.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 :
comparisons, greater and smaller to avoid former results to interfere. SplitSort.addComparisons(Integer[]) on each array contained in sorted. Definition at line 134 of file SplitSort.java.
{
this.comparisons.clear();
this.greater.clear();
this.smaller.clear();
for ( Integer[] tab : this.sorted)
if (tab.length > this.minimalSize)
addComparisons(tab);
}
| Boolean sorter.SplitSort.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.
true if the sort is over, false otherwise. Definition at line 111 of file SplitSort.java.
{
int count = 0;
for (Integer[] tab : this.sorted)
if (tab.length > this.minimalSize)
break;
else
count+=tab.length;
return (count != this.numberOfElements);
}
List<Boolean> sorter.SplitSort.comparisons [private] |
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.
Definition at line 53 of file SplitSort.java.
List<Integer> sorter.SplitSort.greater [private] |
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.
Definition at line 34 of file SplitSort.java.
Integer sorter.SplitSort.minimalSize [private] |
An array of a length smaller than minimalSize will not be sorted.
Definition at line 61 of file SplitSort.java.
Integer sorter.SplitSort.numberOfElements [private] |
The number of elements contained in the initial list of arrays to sort.
Definition at line 57 of file SplitSort.java.
List<Integer> sorter.SplitSort.smaller [private] |
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).
Definition at line 40 of file SplitSort.java.
List<Integer[]> sorter.SplitSort.sorted [private] |
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.
Definition at line 46 of file SplitSort.java.