Stupid Sorting Question

Newbie & Debugging Questions
#1

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

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

will get sorted as

sorted = {2, 2, 7, 5, 3, 1}

Where the 2s get put at the front because they appear twice. Here is another example:

unsorted = {1, 2, 3, 2, 4, 2, 3, 5, 3, 5}

will look like

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?

#2

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

use a new array to store some info:

sortArray[i][j]

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

So, for:

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:


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”:

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”:

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 :frowning:
Sure someone else will give a better answer :slight_smile:

#3

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.

#4

find smallest value, store it into another array and reset original value and continue sorting

#5

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

#6

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.

#7

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 :slight_smile:

Oh what the hell I’m writing code for the fun of it anyway:


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:


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 ;D

#8

I’m going to use this opportunity to advertise Scala. There the code is so much shorter.

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)
#9

Thank you ra4king ;D That’s great.

#10

Here is how I would do it in Java.

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);
    }
}
#11

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:


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);
  }
}
#12 
ra4King,

After trying out your code, I think there is a problem.

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 2 2 4 4 5 3 0


which is not what I want.  :clue: 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?
[/quote]
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

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.
#13

Found the problem!!!

This line

         //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’):

 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 :slight_smile:

#14

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

#15

Nice find! My bad XD

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

#16

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 ;D) 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.

#17

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