0

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?

Greg
  • 754
  • 9
  • 18
  • Until you manage to define exactly what you mean by `roughly sorted` I would say that it is impossible. – Keppil Jan 02 '14 at 17:31
  • do you want to retain the order in which input is given ? – upog Jan 02 '14 at 17:32
  • 1
    http://stackoverflow.com/questions/914129/which-sorting-algorithms-give-near-approximate-sort-sooner – assylias Jan 02 '14 at 17:32
  • 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. – Theresa Forster Jan 02 '14 at 17:34
  • @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. – Greg Jan 02 '14 at 17:35
  • Or you could sort them by "bucket", say, [-1;0], ]0;0.3], ]0.3;1] for your example. Your algo then only places the numbers in the right bucket but does not sort within a given bucket. – assylias Jan 02 '14 at 17:36
  • @assylais all the items need to be included, but i guess you could put all the "unbucketed" items sort them correctly in a separate map and then combine the two? – Greg Jan 02 '14 at 17:40

3 Answers3

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.

Meno Hochschild
  • 42,708
  • 7
  • 104
  • 126
  • 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 Jan 02 '14 at 17:46
  • In the link @assylais gave it has the http://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. – Greg Jan 02 '14 at 17:50
  • @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))` – Meno Hochschild Jan 02 '14 at 17:52
  • Fuzzy logic! why didn't I think of that before :\ I'm just going to play around and see what works better. – Greg Jan 02 '14 at 17:54
1

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.

Jim Garrison
  • 85,615
  • 20
  • 155
  • 190
0

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.

Sibbo
  • 3,796
  • 2
  • 23
  • 41