Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (524)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (592)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Stupid Sorting Question  (Read 3036 times)
0 Members and 1 Guest are viewing this topic.
Offline 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!
Offline _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 1
int h = HowManyDifferent(unsorted); // method to count how many different numbers there are in an array
int k=0;
int g=0;
while (g<h){
   for (k=0; k<unsorted.size();k++){
       if (unsorted[k] == sortArray[i][0]){
            sortArray[i][1]++; //here I count how many 1's there are in unsorted
       }
   }
   k=0;
   i++;
   if (! repeated){
      sortArray[i][0] = unsorted[next]
   }
}


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 Sad
Sure someone else will give a better answer Smiley

Offline 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.

 
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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
Offline 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?
Offline 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!
Offline ra4king

JGO Kernel


Medals: 355
Projects: 3
Exp: 5 years


I'm the King!


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

Thinking logically about this:
-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 Smiley

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 <T extends Comparable<? super T>> void weirdSort(ArrayList<T> list) {
   //sort from least to greatest
   Collections.sort(list);
   
   ArrayList<ArrayList<T>> repeats = new ArrayList<ArrayList<T>>();
   
   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<T>());
         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<T> s = new Stack<T>();
   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<T> 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<Integer> list = new ArrayList<Integer>();
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 Grin

Offline 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)
Offline DavidW

Junior Devvie


Medals: 3
Exp: 7 years



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

Thank you ra4king  Grin  That's great.

Hello!
Offline 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<Integer, Integer> map = new HashMap<Integer, Integer>();
        Comparator<Integer> comp = new Comparator<Integer>() {
            @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);
    }
}
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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;
  private static final int RANK_MASK  = COUNT_INC-1;
 

  // change the array to whatever object
  public static void sort(int[] a)
  {
    int[] encode = new int[RANK_MAX+1];
    int   i;
   
    // initialize low order bits to all the
    // rank values (index zero is unused)
    // bit-packed {count,rank} count is zero
    for(i=1; i<=RANK_MAX; i++)
      encode[i] = i;
   
    // walk the objects and calculate the counts
    // ---whatever iterator here
    for(i=0; i<a.length; i++) {
      int r = a[i];             // get the rank of the object
      encode[r] += COUNT_INC;   // increment the bit-packed count
    }
   
    // sort the bit packed array
    java.util.Arrays.sort(encode);
   
    // since the bit packed encoding is reversed of the
    // desired we need to walk the array in reverse order
    i = RANK_MAX;
   
    while(true) {
      int num  = encode[i] >> 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<a.length-1;i++)
      System.out.printf("%d,", a[i]);
    System.out.printf("%d}\n",a[i]);
   
    System.out.printf("set: {");
   
    // dump out encoded (set) order and build output
    i = RANK_MAX;
    int j = 0;
    while(true) {
      int num  = encode[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<o.length-1;i++)
      System.out.printf("%d,", o[i]);
    System.out.printf("%d}\n",o[i]);
  }
 
  public static void main(String[] arg)
  {
    int[] a = {3,1,2,3,4,5,1,3};
    sort(a);
  }
}
Offline 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<Integer> list = new ArrayList<Integer>(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.  Clueless 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!
Offline 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 Smiley

Hello!
Offline 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

Offline ra4king

JGO Kernel


Medals: 355
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 Smiley
Nice find! My bad XD

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

Offline 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  Grin) 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!
Offline 65K
« Reply #16 - Posted 2012-03-14 19:24:29 »

I would have bet you are developing a Poker game Grin
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.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

toopeicgaming1999 (57 views)
2014-11-26 15:22:04

toopeicgaming1999 (50 views)
2014-11-26 15:20:36

toopeicgaming1999 (10 views)
2014-11-26 15:20:08

SHC (24 views)
2014-11-25 12:00:59

SHC (24 views)
2014-11-25 11:53:45

Norakomi (27 views)
2014-11-25 11:26:43

Gibbo3771 (24 views)
2014-11-24 19:59:16

trollwarrior1 (37 views)
2014-11-22 12:13:56

xFryIx (75 views)
2014-11-13 12:34:49

digdugdiggy (52 views)
2014-11-12 21:11:50
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!