Sorting by frequency

Question

I'm having issue with this question in one of my assignments. I've tried figuring out a solution for hours but it seems I'm doing something wrong.

I need to sort an array by the frequency of its numbers, so for example;

[-1.1, -1.1, 2.4, -3.0, 4.0, 2.4, -1.1, -3.0] => [-1.1, -1.1, -1.1, 2.4, 2.4, -3.0, -3.0, 4.0]

[-0.5, 4.0, 6.5, 6.5, 4.0, -0.5] => [-0.5, -0.5, 4.0, 4.0, 6.5, 6.5]

What I have tried doing, that almost works, is create a function called count() this function checks how many time a double appears in the array, then returns that amount.

I have then made a function:

public static void sortByFreq(double[] arr)

    public static void sortByFreq(double[] arr)
{   
    double temp;
    for(int i = 0; i < arr.length; i++)
    {
        for(int j = 0; j < arr.length; j++)
        {

            if(count(arr, arr[i]) > count(arr, arr[j])) 
            {
// swap them if one of them appears more times(its count is bigger)
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;

            }

        }

    }

    for(int i = 0; i < arr.length; i++) // print the numbers
    {
        System.out.print(arr[i] + " ");
    }


}

Using this method, I've managed to get an incomplete answer, for example - the first example works out fine and prints correctly.

The second one prints [-0.5, 4.0, 6.5, 6.5, 4.0, -0.5] => [-0.5, 4.0, 6.5, 6.5, 4.0, -0.5 ]

As you can see the 4.0 and 6.5 are mixed. How do I solve this issue? Maybe I should try something completely different?

EDIT: I don't know how to use linked lists and I'm not sure we're allowed to use anything beyond what we've learned.

Answer 1

One strategy would be count the occurencies making a 2D array of the elements and sort this new array.

For the 2D array, I declared a class Element.java

public class Element{ 

    public int count;
    public int index;
    public double val;

    public Element(int index, int count , double val){
        this.count = count;
        this.index = index;
        this.val = val;
    }

}

The main algorithm for sorting an array by frequency looks like this

public static void sortByFrequency(double arr[]) {
    Element[] elements = new Element[arr.length];
    for (int i = 0; i < elements.length; i++)
        elements[i] = new Element(i,0,arr[i]);

    /* Count occurrences of remaining elements */
    for (int i = 0; i < arr.length; i++) {
        for(int j = 0; j < arr.length; j++){
            if(elements[i].val == elements[j].val)
                elements[i].count++;
        }
    }
    /* sort on the basis of count and in case of tie use index
    to sort.*/
    Arrays.sort(elements, new Comparator<Element>() {
        @Override
        public int compare(Element o1, Element o2) {
            if (o1.count > o2.count) return -1;
            else if (o1.count < o2.count) return 1;
            // tie breaker
            if(o1.count == o2.count ){
                if (o1.val > o2.val) return -1;
                else if (o1.val < o2.val) return 1;
            }
            return 0;
        }
    });

    for (int i = 0; i < arr.length; i++)
        arr[i] = elements[i].val;
}