Sorting list with smallest size smallest in Java
I'm trying to sort a dataset so that it looks like a histogram of a probability distribution function (I'm assuming it's normally distributed at the moment).
I have a list of entries:
private static final class SortableDatasetEntry{
Number value;
Comparable key;
public SortableDatasetEntry(Number value, Comparable key){
this.value = value;
this.key = key;
}
}
Example: I have elements: {1,2,3,4,5,6,7,8,9}
EDIT: The sorted list I would like: {1,3,5,7,9,8,6,4,2}
(or something similar) The numbers won't always be that neat (i.e. just sorting by odd / doesn't even work). I have a partial solution that involves sorting in regular order (lowest to highest) and then copying that list to another, pasting them in the middle each time, so the last element inserted (in the middle) is the most great. I would still like to find a way to do this with a comparator.
This is quite tricky because it is not sorted by absolute value value
, but by the distance from the mean ( value
) within the set, and then somehow moved so that the values closest to the value are centered. I know the compareTo function must be "reversible" (I forgot the correct term).
Bonus points: How to determine the correct distribution of the data (i.e. if it is not normal as expected).
source to share
It will be easier for you to plot your histogram like Map
.
public static Map<Integer, List<Number>> histogram(List<Number> values, int nBuckets) {
// Get stats on the values.
DoubleSummaryStatistics stats = values.stream().mapToDouble((x) -> x.doubleValue()).summaryStatistics();
// How big must each bucket be?
int bucketSize = (int) (stats.getMax() - stats.getMin()) / nBuckets;
// Roll them all into buckets.
return values.stream().collect(Collectors.groupingBy((n) -> (int) ((n.doubleValue() - stats.getMin()) / bucketSize)));
}
Notice the intent of Histogram
To plot a histogram, the first step is to "bin" a range of values, i.e. Divide the entire range of values into a series of small bins, and then count how many values fall within each bin.
source to share
There will be something like:
public List<Integer> customSort(List<Integer> list) {
Collections.sort(list);
List<Integer> newList = new ArrayList<Integer>();
for (int i = 0; i < list.size(); i += 2) {
newList.add(list.get(i));
}
if (list.size() % 2 == 0) {
for (int i = 1; i < list.size(); i += 2) {
newList.add(list.get(list.size() - i));
}
} else {
for (int i = 1; i < list.size(); i += 2) {
newList.add(list.get(list.size() - i - 1));
}
}
return newList;
}
work? I insert {1,2,3,4,5,6,7,8,9}
and receive {1,3,5,7,9,8,6,4,2}
, and {1,2,3,4,5,6,7,8}
gives {1,3,5,7,8,6,4,2}
.
source to share
You cannot accomplish this in one view with just a custom one Comparator
.
However, it is still possible to do this locally without an additional set of links.
Your current approach is out of place, but is probably the easiest to implement and understand. If the size of the collection in memory is not a concern, consider staying with your current approach.
Custom Comparator in One View
Your desired order depends on the ascending order. With no unsaved data, yours Comparator
has no ascending order on first sort.
On-site approaches
You can create your desired order on site.
What follows assumes 0-based indexes.
One approach would use two kinds. Sort in ascending order first. Label each object with its own index. In a second-class comparator, all objects with even indices will be smaller than all objects with odd indices. Objects with even indices will be ordered in ascending order. Objects with odd indices will be ordered in descending order.
Another approach would be a custom sorting algorithm that supports matching from virtual to physical indexes. The sorting algorithm would create ascending order in the virtual index space. Your index collation will be allocated in physical memory in the order you want. Here's an untested sketch of the index mapping:
private int mapVirtualToPhysical( int virtualIndex, int countElements ) {
boolean isEvenIndex = ( 0 == (index % 2));
int physicalIndex = isEvenIndex ? (index / 2) : (countElements - (index/2) - 1);
return physicalIndex;
}
The preferable one for any of them would be the initial view, followed by a series of O (n) swaps. However, I have not yet defined the swap sequence. The best I have come up with so far has a left tail in order, but a right tail either requires subsequent sorting or a stack.
source to share
For large datasets, you can use an approach where the constructor SortableEntry
determines which side of the graph (left or right to the height) this particular record will occupy, using a random number generator:
static final class SortableEntry<T>{
Number value;
Comparable<T> key;
int hr;
static Random rnd = new Random();
public SortableEntry(Number value, Comparable<T> key){
this.value = value;
this.key = key;
this.hr = rnd.nextInt(2) == 0 ? -1 : 1; // here
}
}
The point of the additional variable hr
is that any "correct" entry will be greater than any "left" one and vice versa. If the hr
two records being compared are the same, compare the actual key
, taking the sign into account hr
:
static final class SortableEntryComparator<T> implements Comparator<SortableEntry<T>> {
@Override
public int compare(SortableEntry<T> e1, SortableEntry<T> e2) {
if (e1.hr == e2.hr)
return e1.hr < 0 ? e1.key.compareTo((T) e2.key) : e2.key.compareTo((T) e1.key);
else
return e1.hr - e2.hr;
}
}
Now a little test:
@Test
public void testSort() {
List<Integer> keys = Arrays.asList(10, 20, 30, 40, 50, 60, 70, 80, 90, 100,
12, 25, 31, 33, 34, 36, 39, 41, 26, 49,
52, 52, 58, 61, 63, 69, 74, 83, 92, 98);
List<SortableEntry<Integer>> entries = new ArrayList<>();
for (Integer k : keys) {
entries.add(new SortableEntry<Integer>(0, k));
}
entries.sort(new SortableEntryComparator<Integer>());
System.out.println(entries);
}
// output:
// [12, 26, 33, 36, 39, 40, 49, 50, 52, 60, 61, 63, 80, 90, 98, 100, 92, 83, 74, 70, 69, 58, 52, 41, 34, 31, 30, 25, 20, 10]
// the highest key (100) is not precisely in the center,
// but it will tend to occur in the center when dataset is large.
source to share