Optimize java code to sort array/arraylist with less time

Question

I was writing a program for a quiz which requires me to sort some numbers and print the corresponding string.

For this, I created a class Song, and took an array of the objects of this class. I have to sort on the basis of variable qi. The problem is that according to the judge, my solution takes too much time and is not efficient enough. I earlier tried with an ArrayList of objects and switched to array thinking that could optimize it to an extent but it was of no help.

How can I optimize it further?

My Code:

   class Song{
    long fi;
    long qi;
    String si;

    public Song(long fi,String si, long qi){
        this.fi = fi;
        this.si = si;
        this.qi = qi;
    }
}

      public class Zipf {
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        long fi;
        long qi;
        String si;
        int noOfSongs = scan.nextInt();
        int selection = scan.nextInt();
        List<Song> list=new ArrayList<Song>(); // all songs
        TreeSet<Song> set = new TreeSet<Song>(new treeComparator());
        for(int i=0; i< noOfSongs;i++)
        {
            fi=(scan.nextLong());
            si=(scan.next());
            qi=(fi*(i+1));
            list.add(new Song(fi,si,qi));//adding all songs to list
        }
        for(int i=0; i< selection;i++)
        {
            set.add(list.get(i));//adding no of songs to be selected into set

        }

        Song min = set.first();
        for (int i = selection; i < list.size(); i++) {
            Song song = list.get(i);
            if (song.qi > min.qi) {
                set.remove(min);
                set.add(song);
                min = set.first();
            }
        }
     Iterator<Song> iterator = set.descendingIterator();

                //Displaying the Tree set data
                for(int i=0;i<selection;i++){
                    System.out.println(iterator.next().si);
                }   

    }


}
class treeComparator implements Comparator<Song>{

    @Override
    public int compare(Song o1, Song o2) {
          if (o1.qi <= o2.qi) return -1;
            if (o1.qi > o2.qi) return 1;
            return 0;
    }
}   

Answer 1

In terms of Big-O complexity, your solution is optimal. It doesn't matter if you're using an array or an ArrayList, sorting takes O(nlogn) in both cases.

You could optimize in the small, such as avoiding creating new throw-away objects in your compare method. But in the big picture this will have a marginal effect on performance.

Thus, are you sure that your general approach to the task is correct? I mean, do you really need to sort the list? For instance, if the task is just to find the minimum qi, you could do without sorting the whole list. This can be generalized to the n smallest qi's like this:

List<Song> list; // all songs
int n; // provided by user

TreeSet<Song> set = new TreeSet<Song>(new Comparator() ...);
for (int i = 0; i < n; i++) {
    set.add(list.get(i));
}

Song max = set.last();
for (int i = n; i < list.size(); i++) {
    Song song = list.get(i);
    if (song.qi < max.qi) {
        set.remove(max);
        set.add(song);
        max = set.last();
    }
}

Here, we assume that the list of songs is very big and that n is smaller than the number of songs in the list. As you can see, you don't have to sort the whole list, it's sufficient to iterate over the list linearly once, and only keep the output set sorted.

The Comparator is the same that you used in your own code, but you can do without the new Long if you do the comparison "manually"

public int compare(Song s1, Song s2) {
    if (s1.qi < s2.qi) return -1;
    if (s1.qi > s2.qi) return 1;
    return 0;
} 

Answer 2

You can also use a TreeMap with key as qi and value as the object of Song class. So that it will be sorted at time of creation. If sorting is your main purpose then go for TreeSet and if it requires to fetch data often then ArrayList is the good choice.

EDIT

ArrayList with predetermined max size is more faster as it reduces the amount of incremental reallocation. So if you know max number of songs then this will be more faster.