Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (574) Games in Android Showcase (154) games submitted by our members Games in WIP (620) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Stupid Sorting Question  (Read 3278 times) 0 Members and 1 Guest are viewing this topic.
DavidW

Junior Devvie

Medals: 3
Exp: 7 years

 « Posted 2012-03-10 18:49:58 »

Hi everyone!  I have been trying to decide how to do this for quite some time and I finally decided I just need some assistance.  I have an array of Comparable objects and I want to sort them, but I want to do it in a weird way.  I'd like to sort from highest to lowest, but also place repeated entries at the front of the array.  The more times the appear the more priority they get so something like

 1 `unsorted = {7, 2, 3, 2, 1, 5}`

will get sorted as
 1 `sorted = {2, 2, 7, 5, 3, 1}`

Where the 2s get put at the front because they appear twice.  Here is another example:
 1 `unsorted = {1, 2, 3, 2, 4, 2, 3, 5, 3, 5}`

will look like
 1 `sorted = {3, 3, 3, 2, 2, 2, 5, 5, 4, 1}`

where you can see that there are three 3s and three 2s, so the 3s appear first in the sorted array. 5 appears after this because there are only two of them.  Lastly we get 4 and 1.

Does this make sense?

Hello!
_Al3x

Senior Devvie

Medals: 7

Indie Games FTW!

 « Reply #1 - Posted 2012-03-10 19:24:57 »

I can only think of a not very good way to solve that:

use a new array to store some info:

 1 `sortArray[i][j]`

i gets the number to sort.
j gets the frequency.

So, for:
 1  2  3  4  5  6  7  8  9  10  11  12 `unsorted = {1, 2, 3, 2, 4, 2, 3, 5, 3, 5}sortArray[0][0] = 1 (number 1)sortArray[0][1] = 1 (there is 1 number 1)sortArray[1][0] = 2 (number 2)sortArray[1][1] = 3 (there are 3 number 2)sortArray[2][0] = 3 (number 3)sortArray[2][1] = 3 (there are 3 number 3)sortArray[3][0] = 4 (number 4)sortArray[3][1] = 1 (there is 1 number 4)sortArray[4][0] = 5 (number 5)sortArray[4][0] = 1 (there is 1 number 5)`

The way to make this array is to go through the unsorted array many times counting...
pseudo code made in 1 minute without testing:
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16 `sortArray[0][0] = unsorted[0] //here I store in [0][0] the first value. In this case, the number 1int h = HowManyDifferent(unsorted); // method to count how many different numbers there are in an arrayint k=0;int g=0;while (g

It's very ugly, but you get the idea.
Once you have sortArray filled, it's easy. Just order it by "j" (the frequency), then order it by "i" taking in consideration "j":

 1  2  3  4  5  6  7  8  9  10 `sortArray[0][0] = 1 (number 1)sortArray[0][1] = 1 (there is 1 number 1)sortArray[1][0] = 2 (number 2)sortArray[1][1] = 3 (there are 3 number 2)sortArray[2][0] = 3 (number 3)sortArray[2][1] = 3 (there are 3 number 3)sortArray[3][0] = 4 (number 4)sortArray[3][1] = 1 (there is 1 number 4)sortArray[4][0] = 5 (number 5)sortArray[4][0] = 1 (there is 1 number 5)`

after ordering by "j":

 1  2  3  4  5  6  7  8  9  10 `sortArray[0][0] = 2 (number 2)sortArray[0][1] = 3 (there are 3 number 2)sortArray[1][0] = 3 (number 3)sortArray[1][1] = 3 (there are 3 number 3)sortArray[2][0] = 1 (number 1)sortArray[2][1] = 1 (there is 1 number 1)sortArray[3][0] = 4 (number 4)sortArray[3][1] = 1 (there is 1 number 4)sortArray[4][0] = 5 (number 5)sortArray[4][0] = 1 (there is 1 number 5)`

In this example it ends here. Sorry that I can't write a better solution right now, I'm at work and can't code focused
Sure someone else will give a better answer

Danny02
 « Reply #2 - Posted 2012-03-10 19:33:31 »

I would use linked sorted sets, this should guarantee around constant adding and removing from the sorted list

Create a node class which holds a some sorted set class and has an empty next node.
when you want to add a new nummber take a look if the head node has this nummber already in its set,
if not insert it,
if add it to the heads next node(if none exist creat a new one)

removing works the excat opposit, try to remove it from the tail and work you towards he head node.

zyzz

Senior Newbie

 « Reply #3 - Posted 2012-03-10 21:55:42 »

find smallest value, store it into another array and reset original value and continue sorting
Roquen
 « Reply #4 - Posted 2012-03-11 07:42:24 »

Are the values integers and are the integers on some limited range and if so, what's the range?
DavidW

Junior Devvie

Medals: 3
Exp: 7 years

 « Reply #5 - Posted 2012-03-11 17:50:03 »

They are not integers, they are just objects which implement the Comparable interface.  However, each object does have a "rank" which I am using to do the comparison and that ranges from 1 to 14.

Hello!
ra4king

JGO Kernel

Medals: 374
Projects: 3
Exp: 5 years

I'm the King!

 « Reply #6 - Posted 2012-03-12 05:46:59 »

-sort list from smallest to largest
-remove and add repeated entries in an ArrayList of ArrayLists.
-push remaining items onto a stack
-sort ArrayList of ArrayLists into ascending order by comparing lengths or value
-push the Arraylists into the stack
-popping the stack will give you the desired sorted list

I might not have explained it well enough so if you need code, just ask

Oh what the hell I'm writing code for the fun of it anyway:
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62 `public > void weirdSort(ArrayList list) {   //sort from least to greatest   Collections.sort(list);      ArrayList> repeats = new ArrayList>();      for(int a = 0; a < list.size(); a++) {      T t = list.get(a);            int size = repeats.size();            //if 't' equals the one after it and either the repeats is empty or that value hasn't been added before      //then create a new list, and add it      if((size == 0 || !repeats.get(size-1).get(0).equals(t)) && (a < list.size()-1 && t.equals(list.get(a+1)))) {         repeats.add(new ArrayList());         repeats.get(size).add(list.remove(a));         a--;      }      //if 't' is a repeat, add it to the repeated list      else if(size != 0 && repeats.get(size-1).get(0).equals(t)) {         repeats.get(size-1).add(list.remove(a));         a--;      }   }      //push the remaining non-repeats onto the stack   Stack s = new Stack();   for(T t : list)      s.push(t);      //sort by lengths from least to greatest using Selection sort   for(int a = 0; a < repeats.size()-1; a++) {      int min = a;            for(int b = a+1; b < repeats.size(); b++) {         //test if ArrayList at 'b' is smaller than the ArrayList at 'min'         if(repeats.get(b).size() < repeats.get(min).size())            min = b;         //if ArrayLists 'b' and 'min' are the same lengths, test for lower value         else if(repeats.get(b).size() == repeats.get(min).size() && repeats.get(b).get(0).compareTo(repeats.get(min).get(0)) < 0)            min = b;      }            //swap      if(min != a) {         T t = repeats.get(min);         repeats.set(min,repeats.set(a,t));      }   }      //push the repeats onto the stack   for(ArrayList a : repeats)      for(T t : a)         s.push(t);   //clear the list to dump the stack into it   list.clear();      //Let me hear it pop!   while(!s.isEmpty())      list.add(s.pop());}`

This code compiles, is tested, and it works with:
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16 `ArrayList list = new ArrayList();list.add(1);list.add(2);list.add(3);list.add(2);list.add(4);list.add(2);list.add(3);list.add(5);list.add(3);list.add(5);weirdSort(list);for(int i : list)   System.out.print(i + " ");//Output: 3 3 3 2 2 2 5 5 4 1 `

EDIT: looking back at this.......daaamnnnnn I feel smart :S

DrZoidberg

Senior Devvie

Medals: 17

 « Reply #7 - Posted 2012-03-12 08:01:37 »

I'm going to use this opportunity to advertise Scala. There the code is so much shorter.
 1  2  3  4  5  6  7 `val unsorted = Array(1, 2, 3, 2, 4, 2, 3, 5, 3, 5)val map = new scala.collection.mutable.HashMap[Int, Int]() {  override def default(key: Int) = 0}unsorted.foreach(n => map += (n -> (map(n)+1)))val sorted = unsorted.sortBy(x => (-map(x), -x))sorted.foreach(println)`
DavidW

Junior Devvie

Medals: 3
Exp: 7 years

 « Reply #8 - Posted 2012-03-12 08:31:12 »

Thank you ra4king    That's great.

Hello!
DrZoidberg

Senior Devvie

Medals: 17

 « Reply #9 - Posted 2012-03-12 08:37:52 »

Here is how I would do it in Java.
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22 `import java.util.*;public class Sorting {    public static void main(String[] args) {        final HashMap map = new HashMap();        Comparator comp = new Comparator() {            @Override            public int compare(Integer i1, Integer i2) {                if(map.get(i1) == map.get(i2)) return i2-i1;                else return map.get(i2)-map.get(i1);            }        };        Integer[] unsorted = {1, 2, 3, 2, 4, 2, 3, 5, 3, 5};        for(int i: unsorted) {            Integer value = map.get(i);            if(value == null) value = 0;            map.put(i, value+1);        }        Arrays.sort(unsorted, comp);        for(int i: unsorted) System.out.println(i);    }}`
Roquen
 « Reply #10 - Posted 2012-03-12 10:18:53 »

The real question is, what things do you really want to do?  Do you really want to sort something and that's it or what?  There are tons of different ways this could be structured, but what make sense depends how what exactly is needed and what operations are going to happen the most if more than one is desired.  Your ordering can be achieved by thinking in terms of set.  So input {1,1,1} -> {{3,1}}  (i.e. 3 1's)  and {1,2,3} -> {{1,1},{1,2},{1,3}} (I'm showing reversed of your desired order, but that doesn't matter), etc.  Since your number of ranks is small, this set info can be packed into a single integer as follows:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100 `public class EncodedSortThing{  public static final int RANK_MAX = 14;    // calculate bit-packing constants  private static final int RANK_SHIFT = 32-Integer.numberOfLeadingZeros(RANK_MAX);  private static final int COUNT_INC  = 1<> RANK_SHIFT;      int rank = encode[i] & RANK_MASK;            if (num != 0) {        // do whatever real work here.        // * for example if you really want sorted, you        //   know how much space in the output each will        //   take and can directly fill an output structure        //   yielding an O(n) (linear time) sorting.                i--;        continue;      }            break;    }            // *** BELOW HERE HACKY DEMO CODE:        int[] o = new int[a.length];        // dump out input set in original order    System.out.printf("in:  {");    for(i=0;i> RANK_SHIFT;      int rank = encode[i] &  RANK_MASK;            if (num != 0) {        System.out.printf("{%d,%d},", num,rank);                while(0 != num--)          o[j++] = rank;                i--;      }       else        break;    }    System.out.printf("}\n");        // dump out output order    System.out.printf("out: {");    for(i=0;i
DavidW

Junior Devvie

Medals: 3
Exp: 7 years

 « Reply #11 - Posted 2012-03-14 08:18:55 »

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21 `ra4King,After trying out your code, I think there is a problem.[code]ArrayList list = new ArrayList(10);      list.add(1);list.add(2);list.add(1);list.add(2);list.add(4);list.add(0);list.add(1);list.add(4);list.add(3);list.add(5);      weirdSort(list);      for(int i : list)    System.out.print(i + " ");`

produces this output:
 1 `1 1 1 2 2 4 4 5 3 0 `

which is not what I want.  I am looking over the code now to see if I can find a problem, but thought I'd let you know that there is an issue.  If I find a solution I will post it below.

Quote
The real question is, what things do you really want to do?  Do you really want to sort something and that's it or what?

This is for a card game I am inventing.  The purpose of this sorting thing is to find out who has the best hand, and to also print the cards out in a logical looking order.  So the sort is happening on these cards.  Now each card has a rank and a picture, where we have that

 1  2  3 `public int compareTo(Card c) {  return this.rank - c.getRank();}`

so the ordering is not consistent with Object.equals().  I know it says here: (http://docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html) not to do this, but whatever!  Basically, for this sorting I don't care if the cards have different pictures or not.  But because of this I can't just store ordered pairs like (3, 1) for "three ones" because the ones may have different pictures and I don't want to lose that information.[/code]

Hello!
DavidW

Junior Devvie

Medals: 3
Exp: 7 years

 « Reply #12 - Posted 2012-03-14 08:38:11 »

Found the problem!!!

This line
 1  2 `         //if ArrayLists 'b' and 'a' are the same lengths, test for lower value         else if(repeats.get(b).size() == repeats.get(a).size() && repeats.get(b).get(0).compareTo(repeats.get(a).get(0)) < 0)`

should be this (change 'a' to 'min'):

 1 ` else if(repeats.get(b).size() == repeats.get(min).size() && repeats.get(b).get(0).compareTo(repeats.get(min).get(0)) < 0)`

In all honesty though your code is pretty slick and I hope you don't feel bad at all for this very small error

Hello!
65K
 « Reply #13 - Posted 2012-03-14 08:51:12 »

I would:
1. identify valid card combinations for each hand, define classes for two-of-a-kind, three-of-a-kind, full-house, etc.
2. put a list together of those for each hand
3. sort the combination lists of each player by implementing proper Comparators

-> easy to modify or extend rules
-> operates on a more abstract level instead of sorting cards directly

ra4king

JGO Kernel

Medals: 374
Projects: 3
Exp: 5 years

I'm the King!

 « Reply #14 - Posted 2012-03-14 10:13:34 »

Found the problem!!!

This line
 1  2 `         //if ArrayLists 'b' and 'a' are the same lengths, test for lower value         else if(repeats.get(b).size() == repeats.get(a).size() && repeats.get(b).get(0).compareTo(repeats.get(a).get(0)) < 0)`

should be this (change 'a' to 'min'):

 1 ` else if(repeats.get(b).size() == repeats.get(min).size() && repeats.get(b).get(0).compareTo(repeats.get(min).get(0)) < 0)`

In all honesty though your code is pretty slick and I hope you don't feel bad at all for this very small error

I wonder why it gave me the correct output though :/

DavidW

Junior Devvie

Medals: 3
Exp: 7 years

 « Reply #15 - Posted 2012-03-14 19:09:27 »

I would:
1. identify valid card combinations for each hand, define classes for two-of-a-kind, three-of-a-kind, full-house, etc.
2. put a list together of those for each hand
3. sort the combination lists of each player by implementing proper Comparators

-> easy to modify or extend rules
-> operates on a more abstract level instead of sorting cards directly

That's not a bad idea except that hands can be an arbitrary number of cards.  In Poker, where you only have 5 cards hands there are a small number of possible combinations, but they grow like e^(sqrt(n))/n which grows pretty fast (see http://en.wikipedia.org/wiki/Partition_(number_theory) for math about this  ) While there is an upper limit to the size of a hand, the number of possible hands is too large for me to individually make a class for each one.

Hello!
65K
 « Reply #16 - Posted 2012-03-14 19:24:29 »

I would have bet you are developing a Poker game
Anyway, I did not mean one class for each card combination but for each "value class" or however its called.
So, for Poker there would be one class for the Royal Flush, one for Full House, one for Straight, etc.
Objects of these value classes would get attributes for current cards of a hand.

Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 Riven (31 views) 2015-04-16 10:48:47 Duke0200 (43 views) 2015-04-16 01:59:01 Fairy Tailz (33 views) 2015-04-14 20:13:12 Riven (35 views) 2015-04-12 21:36:37 bus hotdog (50 views) 2015-04-10 02:39:32 CopyableCougar4 (52 views) 2015-04-10 00:51:04 BurntPizza (52 views) 2015-04-06 22:06:58 ags1 (54 views) 2015-04-02 10:58:48 Riven (53 views) 2015-04-01 18:27:05 ags1 (70 views) 2015-03-31 10:55:12
 theagentd 27x BurntPizza 17x wessles 15x 65K 11x kingroka123 11x Rayvolution 11x alwex 11x KevinWorkman 9x kevglass 8x phu004 8x Hanksha 7x SHC 7x Olo 7x ra4king 7x Ecumene 7x Roquen 7x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org