Data Structures, Algorithms, & Applications in Java
Chapter 15, Exercise 23

Suppose we have the 12 elements [6, 7, 2, 5, 6, 2, 5, 7, 6, 2, 5, 5]. The distinct elements and their frequencies can be determined by first sorting the elements to get the array [2, 2, 2, 5, 5, 5, 5, 6, 6, 6, 7, 7]. The number of 2s can be determined by scanning the sorted elements from left to right looking for the first element that is not 2. This element, 5, is in position 3. So there are three 2s. To determine the number of 5s, we scan rightwards from the location c = 3 of the first 5 to the location j = 7 of the first element that is not a 5. The number of 5s is j - c = 4.

The code below uses this strategy to determine the distinct elements and their frequencies. Since we use a heap sort to sort the elements and since heap sort sorts elements in array positions [1:n], we input the elements into positions [1:n] of an array rather than into positions [0:n-1]. The code is given below. The test data and output appear in the files HistogrammingBySorting.*. 
public class HistogrammingBySorting
{
   public static void main(String [] args)
   {
      // define input stream
      MyInputStream keyboard = new MyInputStream();

      System.out.println("Enter number of elements");
      int n = keyboard.readInteger();
   
      // create array to hold the keys
      MyInteger [] key = new MyInteger [n + 1]; 

      // input the keys into the array key[1:n]
      for (int i = 1; i <= n; i++)
      {
         System.out.println("Enter element " + i);
         key[i] = MyInteger.input(keyboard);
      }
   
      // sort the keys
      HeapSort.heapSort(key);  
   
      // output distinct keys and their counts
      System.out.println("Distinct elements and frequencies are");
      int c = 1;                // cursor into keys
      while (c <= n)
      {// new key at key[c]
         // scan over keys equal to key[c]
         int j = c + 1;
         while (j <= n && key[j].equals(key[c]))
            j++;
   
         // number of elements equal to key[c] is j - c
         System.out.print(key[c] + " " + (j - c) + "    ");
   
         // set c to next new key
         c = j;
      }
      System.out.println();
   }
}