Sorting Collections

As we have seen, there are some classes in the collections framework that force the items within them to be sorted. Examples of that are TreeSet and TreeMap. The aspect to explore in this section is how to use existing sorting mechanisms for lists, but also for cases that have datasets with more than one value per data point.

The exercise we are doing throughout this chapter is a good example of a case where there are data points with more than one value. For each data point, we need to store the word for which we are calculating the frequency and the frequency itself. You might think that a good technique to sort that out is by storing the information in the form of maps. The unique words could be the keys, while the frequencies could be the values. This could be achieved by modifying the final part of the previous program to look like this:

Map map = new HashMap();

while (iterator.hasNext()) {

    //  point to next element

    String s = (String) iterator.next();

    // get the amount of times this word shows up in the text

    int freq = Collections.frequency(text, s);

    // print out the result

    System.out.println(s + " appears " + freq + " times");

    // add items to the map

    map.put(s, freq);

}

TreeMap mapTree = new TreeMap();

mapTree.putAll(map);

System.out.println(mapTree);

While this is an interesting and simple approach to sorting (copying the data into a structure that is sorted by nature), it presents the problem that data is sorted by key and not by value, as the following result of the previous code highlights:

Word count: 11

a appears 2 times

test appears 3 times

this appears 2 times

is appears 3 times

* appears 1 times

{*=1, a=2, is=3, test=3, this=2}

So, if we want to sort these results by value, we need to figure out a different strategy.

But let's step back for a second and analyze what tools are offered in the collections framework for sorting. There is a method called sort() that can be used to sort lists. An example of this is as follows:

import java.util.*;

public class Example19 {

    public static void main(String[] args) {

        List <Double> array = new ArrayList();

        array.add(5.0);

        array.add(2.2);

        array.add(37.5);

        array.add(3.1);

        array.add(1.3);

        System.out.println("Original list: " + array);

        Collections.sort(array);

        System.out.println("Modified list: " + array);

    }

}

The result of this program is:

Original list: [5.0, 2.2, 37.5, 3.1, 1.3]

Modified list: [1.3, 2.2, 3.1, 5.0, 37.5]

Process finished with exit code 0

Given a list, we could sort it this way just fine; it would even be possible to navigate through it backward using listIterator to sort a list in descending order. However, these methods do not solve the issue of sorting data points with multiple values. In such a case, we would need to create a class to store our own key-value pair. Let's see how to implement this by continuing with the exercise we have been dealing with throughout the chapter.

Exercise 3: Sort the Results from the AnalyzeInput Application

We now have a program that, given some input text, identifies some basic characteristics of the text, such as the number of words in the text or the frequency of each of the words. Our goal is to be able to sort the results in descending order to make them easier to read. The solution will require the implementation of a class that will store our key-value pairs and make a list of objects from that class:

1. Create a class containing the two data points: the word and its frequency. Implement a constructor that will take values and pass them to class variables. This will simplify the code later:

   class DataPoint {

       String key = "";

       Integer value = 0;

       // constructor

       DataPoint(String s, Integer i) {

           key = s;

           value = i;

       }

   }

2. When calculating the frequency for each word, store the results in a newly created list of objects of the new class:

           List <DataPoint> frequencies = new ArrayList <DataPoint> ();

           while (iterator.hasNext()) {

           //point to next element

           String s = (String) iterator.next();

           // get the amount of times this word shows up in the text

           int freq = Collections.frequency(text, s);

           // print out the result

           System.out.println(s + " appears " + freq + " times");

           // create the object to be stored

           DataPoint datapoint = new DataPoint (s, freq);

           // add datapoints to the list

           frequencies.add(datapoint);

       }

3. Sorting is going to require the creation of a new class using the Comparator interface, which we are just introducing now. This interface should implement a method that will be used to run comparisons within the objects in the array. This new class must implement Comparator <DataPoint> and include a single method called compare(). It should have two objects of the class being sorted as parameters:

   class SortByValue implements Comparator<DataPoint>

   {

       // Used for sorting in ascending order

       public int compare(DataPoint a, DataPoint b)

       {

           return a.value - b.value;

       }

   }

4. The way we call the Collections.sort() algorithm using this new comparator is by adding an object of that class as a parameter to the sort method. We instantiate it directly in the call:

   Collections.sort(frequencies,new SortByValue());

5. This will sort the frequencies list in ascending order. To print the results, it is no longer valid to make a direct call to System.out.println(frequencies) because it is now an array of objects and it will not print the contents of the data points to the terminal. Iterate through the list in the following way instead:

   System.out.println("Results sorted");

   for (int i = 0; i < frequencies.size(); i++)

       System.out.println(frequencies.get(i).value

                       + " times for word "

                       + frequencies.get(i).key);

6. If you run the program using the same input that we have been using for the last couple of examples, the outcome will be:

   Results sorted

   1 times for word *

   2 times for word a

   2 times for word this

   3 times for word test

   3 times for word is

7. Our goal is to sort the results in descending order and, to do that, we will need to add one more thing to the call to the sort algorithm. When instantiating the SortByValue() class, we need to tell the compiler that we want the list to be sorted in reverse order. The collections framework already has a method for this:

   Collections.sort(frequencies, Collections.reverseOrder(new SortByValue()));

   Note

   For the sake of clarity, the final code can be referred at: https://packt.live/2W5qhzP.

8. A full interaction path with this program, from the moment we call it to include the data entry, would be as follows:

   user@localhost:~/IdeaProjects/ch04/out/production/ch04$ java AnalyzeInput

   this is a test

   is a test

   test is this

   *

   You typed: [this, is, a, test, is, a, test, test, is, this, *]

   Word count: 11

   a appears 2 times

   test appears 3 times

   this appears 2 times

   is appears 3 times

   * appears 1 times

   Results sorted

   3 times for word test

   3 times for word is

   2 times for word a

   2 times for word this

   1 times for word *