What is the most efficient way to simultaneously sort three ArrayLists in Java

Question

I have three ArrayLists. One of Strings - names, and two of Integers - score and picture numbers. I want to sort them simultaneously by the players scores (from highest to lowest). Now i use a simple bubble sort, but i think it will not be efficient when the Lists will be bigger.

This is my code:

public class MyBubbleSort {

    public static void bubble_srt(List<Integer> score, List<String> name, List<Integer> pic) {
        int n = score.size();
        int k;
        for (int m = n; m >= 0; m--) {
            for (int i = 0; i < n - 1; i++) {
                k = i + 1;
                if (score.get(i) < score.get(k)) {
                    swapNumbers(i, k, score, name, pic);
                }
            }
            printNumbers(score);
        }
    }

    private static void swapNumbers(int i, int j, List<Integer> score, List<String> name, List<Integer> pic) {

        int temp;
        temp = score.get(i);
        score.set(i, score.get(j));
        score.set(j, temp);

        String s;
        s = name.get(i);
        name.set(i, name.get(j));
        name.set(j, s);

        int p;
        p = pic.get(i);
        pic.set(i, pic.get(j));
        pic.set(j, p);

    }

    private static void printNumbers(List<Integer> input) {

        for (int i = 0; i < input.size(); i++) {
            System.out.print(input.get(i) + ", ");
        }
        System.out.print("\n");
    }

}

Thanks!

Eran · Accepted Answer · 2015-12-15 07:42:24Z

8

Best way would be to create a class containing score, name and pic properties and have a single List of that class, which you sort using Collections.sort and a Comparator that compares two instances of your class according to the score property.

Bubble sort is in-efficient compared to other sorting algorithms (merge sort, quick sort), and there's no need to implement a sort algorithm yourself, since the standard Java packages already do that for you.

answered Dec 15, 2015 at 7:42

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Kraal · Accepted Answer · 2015-12-15 08:02:06Z

First create a PlayerInfo class as follows:

package test;

public class PlayerInfo {

    private String name;
    private Integer score;
    private Integer pictureId;

    public PlayerInfo(final String name, final Integer score, final Integer pictureId) {
        this.name = name;
        this.score = score;
        this.pictureId = pictureId;
    }

    public String getName() {
        return this.name;
    }

    public void setName(final String name) {
        this.name = name;
    }

    public Integer getScore() {
        return this.score;
    }

    public void setScore(final Integer score) {
        this.score = score;
    }

    public Integer getPictureId() {
        return this.pictureId;
    }

    public void setPictureId(final Integer pictureId) {
        this.pictureId = pictureId;
    }

    @Override
    public String toString() {
        return this.name + ":" + this.score + ":" + this.pictureId;
    }
}

Second create a PlayerInfo Comparator. Here we create a ScoreBasedComparator (as per your request, but you can create other comparators as well to fit your specific needs):

package test;

import java.util.Comparator;

public class ScoreBasedComparator implements Comparator<PlayerInfo> {

    @Override
    public int compare(final PlayerInfo playerInfo1, final PlayerInfo playerInfo2) {
        return playerInfo1.getScore().compareTo(playerInfo2.getScore());
    }

}

Finally, you can sort your List of PlayerInfo instances, using Collections.sort(<your collection>, <your comparator>) as follows:

package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Runner {

    public static void main(final String[] args) {
        List<PlayerInfo> playerInfos = new ArrayList<PlayerInfo>();
        playerInfos.add(new PlayerInfo("A", 123, 1));
        playerInfos.add(new PlayerInfo("B", 1, 2));
        playerInfos.add(new PlayerInfo("C", 23, 3));
        playerInfos.add(new PlayerInfo("D", 300, 4));
        Collections.sort(playerInfos, new ScoreBasedComparator());
        System.out.println(Arrays.toString(playerInfos.toArray()));
    }

}

Running this small program will output the following line:

[B:1:2, C:23:3, A:123:1, D:300:4]

As you can see your collection was unsorted at creation time but is printed sorted by score.

Hope this helps.

rcgldr · Accepted Answer · 2015-12-15 17:06:26Z

If the goal here is to sort three arrays according to one of the arrays, without resorting to combining the arrays into a common class, then a fourth array of indices, 0 to size-1 can be created, then the array of indices is sorted according to one of the arrays (using a built in sort and custom compare). Then all three arrays are reordered according to the array of sorted indices. I don't know if Java has a built in reorder function. C example to reorder 3 arrays, A,B,C according to sorted array of indices I, with time complexity of O(n) (linear, every store places a value in it's ordered position). I is reverted back to 0 to n-1.

    // reorder A,B,C in place according to I
    // tA,tB,tC are temps
    for(i = 0; i < n; i++){
        if(i != I[i]){
            tA = A[i];
            tB = B[i];
            tC = C[i];
            k = i;
            while(i != (j = I[k])){
                A[k] = A[j];
                B[k] = B[j];
                C[k] = C[j];
                I[k] = k;
                k = j;
            }
            A[k] = tA;
            B[k] = tB;
            C[k] = tC;
            I[k] = k;
        }
    }

Collectives™ on Stack Overflow

What is the most efficient way to simultaneously sort three ArrayLists in Java

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related