Java Ordering a map or list

Question

if you have a map or list with a bunch of doubles between -1 and 1 you can order them from -1 to 1. how ever it is perfect e.g ( 0.4 is after 0.3 but before 0.5 )

is it possible to simulate putting the numbers generally in the correct place but not perfect? its hard to explain what I mean but I have drawn a diagram to help.

The x's are points on the number line The x's are points on the number line

I don't want it to be perfectly sorted, neither randomly sorted but in-between; roughly sorted. is this possible if so how?

• Keppil: Until you manage to define exactly what you mean by roughly sorted I would say that it is impossible.
• upog: do you want to retain the order in which input is given ?
• assylias: stackoverflow.com/questions/914129/…
• Theresa Forster: Sounds like you want to have them ordered but then mess them up a little afterwards, Think of it as 2 steps. order them then take random number of adjacent values and swap them.
• Greg: @Keppil thats the problem there is no definition for roughly sorted. Think of it like whats 5/12? you know that 5/10 is 5 so its go to be less than 5 you can approximate it to be about 0.4 ish. that's what i mean by roughly.

Answer 1

You can use a TreeMap (constructor with Comparator-arg) or Collections.sort(List, Comparator) with a Comparator based on Double.compare(double, double).

This is correct for perfect sorting. About "roughly sorted", you have to write your own Comparator-logic. And please define your term how you really want to sort.

• Greg: Ill explain what its for maybe that will help: The program is given a list of random words which are given a positive/negative rating to which one would be most suited. Then it is sorted and the top pos/neg word is selected, however I don't want it to return the perfect word every time, nor a random one but a better than average one.
• Greg: In the link @assylais gave it has the en.wikipedia.org/wiki/Shell_sort I might use that and stop it after X cycles with what you provided to accomplish it. It was a theoretical idea I just wanted to see if this part is possible and how.
• Meno Hochschild: @user2871826 Maybe you can apply some kind of randomized multiplication on the real ratings and then sort these fuzzy ratings. For example: Math.max(0.0, Math.min(1.0, x + Math.random() * 0.1 - 0.05))
• Greg: Fuzzy logic! why didn't I think of that before :\ I'm just going to play around and see what works better.

Answer 2

You haven't defined 'roughly sorted', but one option is "binning". Split the interval into n bins of width intervalsize/n. Store the bins in an array or list, and each bin is a list of values. Iterate once over the input set and distribute the values to their appropriate bins, which is O(n). You can improve the sorting by increasing the number of bins.

Answer 3

You can sort them first, and then run a set random swap of direct neighbours. For example, with a list size of n, you swap n times at random positions.