Search code examples
javabubble-sort

Java Bubble Sort method for Object's fields


I want to sort Token objects first based on their usedNumber bigger to smaller.
Then for the tokens have same usedNumber i want to sort them smaller to bigger based their priority number for example:
name priority usedNumber
a 1 3
b 2 4
c 3 0
d 4 3
e 5 3
f 6 4
Sorted version should be first bigger usedNumbers then smaller priorty:
b 2 4
f 6 4
a 1 3
d 4 3
e 5 3
c 3 0
Code below doesnt sort them correctly

public class Token {
    int usedNumber;
    int priority;
    String name;
    public  Queue<Token> reversebubbleSort(Queue<Token> queue)
    {
        int n = queue.size();
        int i;
        int j;
        Token temp;
        boolean swapped;
        for (i = 0; i < n - 1; i++)
        {
            swapped = false;
            for (j = 0; j < n - i - 1; j++)
            {
                int namenumber1 = Integer.parseInt(queue.get(j).priority);
                int namenumber2 = Integer.parseInt(queue.get(j+1).priority);
                int number1 = queue.get(j).getUsedNumber();
                int number2 = queue.get(j+1).getUsedNumber();
                if (((number1^5)-namenumber1) < ((number2^5)-namenumber2))
                {
                    // swap arr[j] and arr[j+1]
                    temp = queue.get(j);
                    queue.set(j, queue.get(j+1));
                    queue.set(j+1, temp);
                    swapped = true;
                }
            }
            // IF no two elements were
            // swapped by inner loop, then break
            if (swapped == false)
                break;
        }
        return queue;
    }

Queue class in here is not from java.util. This is a class designed by me due the restrictions in my assigment. Queue class uses Arraylists to perform.

public class Queue<Token>  {
    private ArrayList<Token> queue;
    public Queue() {
        queue = new ArrayList<>();
    }

    public void add(Token addItem){
        //In queues, adding in the back, first in first out.
        queue.add(addItem);
    }
    public void removeFromFront(){
        queue.remove(0);
    }
    public int size(){
        return queue.size();
    }


    public Token get(int location){
        return queue.get(location);
    }
    public void remove(int index){
        queue.remove(index);
    }

    public void set(int location, Token setItem) {
        queue.set(location, setItem);
    }
}
}

Solution

    • Rather than wrapping ArrayList in your Queue, extend it: makes for simpler code
    • Don't use "Token" as a generic class name: it's confusing. Rather use the standard T Which gives you code for Queue.java:
    import java.util.ArrayList;
    
    /*
     * If it's only ever used for Token, it could also be
     * public class Queue extends ArrayList<Token>
     *   and then you could override the sort method of ArrayList
     *   with the implementation shown in Token.sortSpecial below
     */
    public class Queue<T> extends ArrayList<T> {
    
      private static final long serialVersionUID = 1L;
    
      public void removeFromFront() {
        super.remove(0);
      }
    
    }
    
    • Method for sorting queues in class Token should be static: it's not linked to the state of an instance. I've renamed it sortSpecial. It also doesn't have to return, as the sorting is done in place on the Queue
    • Use List.sort with a custom Comparator to do the sorting
    • Fields should be private with getters and setters (which are not shown here)

    Which gives you Token.java:

    public class Token {
    
      private String name;
      private int priority;
      private int usedNumber;
    
      public Token(String name, int priority, int usedNumber) {
        super();
        this.usedNumber = usedNumber;
        this.priority = priority;
        this.name = name;
      }
    
      /* Getters and Setters go here */
    
      /** Sort by usedNumber DESC / priority ASC */
      public static void sortSpecial(Queue<Token> queue) {
        queue.sort((x, y) -> {
          int comp = -Integer.compare(x.usedNumber, y.usedNumber);
          if (comp == 0)
            comp = Integer.compare(x.priority, y.priority);
          return comp;
        });
      }
      
      @Override
      public String toString() {
        return getClass().getSimpleName() + "[" + name + " (p=" + priority + ", un=" + usedNumber + ")]";
      }
      
    }
    

    Or if you want to play smart-ass, you could write the comparator as a one-liner (after defining your getters):

    Comparator.comparingInt(Token::getUsedNumber).reversed().thenComparingInt(Token::getPriority)
    

    Entry point for your program (Main.java):

    public class Main {
      
      public static void main(String[] args) {
        Queue<Token> toks = new Queue<>();
        toks.add(new Token("a", 1, 3));
        toks.add(new Token("b", 2, 4));
        toks.add(new Token("c", 3, 0));
        toks.add(new Token("d", 4, 3));
        toks.add(new Token("e", 5, 3));
        toks.add(new Token("f", 6, 4));
        
        System.out.println("Input:");
        toks.stream().forEach(t -> System.out.println('\t' + t.toString()));
        System.out.println();
        
        Token.sortSpecial(toks);
        System.out.println("Output:");
        toks.stream().forEach(t -> System.out.println('\t' + t.toString()));
      }
    
    }
    

    Console output:

    Input:
        Token[a (p=1, un=3)]
        Token[b (p=2, un=4)]
        Token[c (p=3, un=0)]
        Token[d (p=4, un=3)]
        Token[e (p=5, un=3)]
        Token[f (p=6, un=4)]
    
    Output:
        Token[b (p=2, un=4)]
        Token[f (p=6, un=4)]
        Token[a (p=1, un=3)]
        Token[d (p=4, un=3)]
        Token[e (p=5, un=3)]
        Token[c (p=3, un=0)]