1

I am trying to sort an array using the insertion sort algorithm. The array is filled with WordNode elements that include a word field (inputted from a text file) and a frequency field (to measure the number of times the particular word appears in the text file). I have implemented the sort so that words are sorted by frequency (from lowest to highest), but I also want to sort alphabetically if frequencies are equal. How can I sort using two different criteria at the same time? Below is my sort code.

public static void sort(ArrayUnorderedList<WordNode> array) {
    //create stacks for insertion sort
    LinkedStack<WordNode> sorted = new LinkedStack<WordNode>();
    LinkedStack<WordNode> temp = new LinkedStack<WordNode>();

    //while the array has elements to be sorted
    while(!array.isEmpty()) {
        //remove current element from array
        WordNode currentNode = array.removeFirst();

        //while the sorted stack meets sorting criteria
        while((!sorted.isEmpty()) && (sorted.peek().getFrequency() < currentNode.getFrequency())) {
            //push elements to temp stack
            temp.push(sorted.pop());
        }

        //push current element to sorted stack
        sorted.push(currentNode);

        //while the temp stack has elements to be replaced
        while(!temp.isEmpty()) {
            //push elements to sorted stack
            sorted.push(temp.pop());
        }
    }

    //replace sorted elements in array
    while(!sorted.isEmpty()) {
        array.addToRear(sorted.pop());
    }
}
Improve this question
1
  • You could also look at implementing Comparable, then you can compare each node directly, and control the comparison from one place Commented Apr 13, 2012 at 2:08

4 Answers 4

Reset to default
1

AppClay's answer is absolutely correct, but if you are interested in "tidying it up", create a helper that implements Comparator.

class WordNodeComparator implements Comparator<WordNode> {
    @Override
    public int compare(WordNode lhs, WordNode rhs) {
        int result = lhs.getFrequency() - rhs.getFrequency();
        if (result == 0) {
            return lhs.getWord().compareTo(rhs.getWord());
        }
        else {
            return result;
        }
    }
}

Then you simply create an instance of it, and use it in your loop:

while((!sorted.isEmpty()) && (nodeComparator.compare(sorted.peek(), currentNode) < 0)

Not only does this make the code easier to read and test, it's now trivial to swap out different Comparator implementations as needed.

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

1 Comment

This is a much nicer way of doing it, if I ever code in Java again (it's been a while) hopefully I'll remember this :)
0

Update this line:

while((!sorted.isEmpty()) && (sorted.peek().getFrequency() < currentNode.getFrequency())) {

to:

while((!sorted.isEmpty()) && (sorted.peek().getFrequency() < currentNode.getFrequency() || (sorted.peek().getFrequency() == currentNode.getFrequency() &&  sorted.peek().getWord().compareTo(currentNode.getWord()) < 0))) {
Improve this answer

3 Comments

I admit this is a little ugly. It might be nicer to create a function for the comparison and pass in sorted.peek() and currentNode as parameters
Though you may think it's ugly, it's still perfectly functional, so thank you for the assistance! I'll consider "tidying it up" a bit once I finish some of the other functionality in my program.
I guess the other option is to spread it over a couple of lines to make it more readable/maintainable.
0

Add this to your code:

int cmp = sorted.peek().getFrequency() - currentNode.getFrequency();
if (cmp == 0)
    cmp = sorted.peek().getWord().compareTo(currentNode.getWord());

while((!sorted.isEmpty()) && cmp < 0) {
    //push elements to temp stack
    temp.push(sorted.pop());
    cmp = sorted.peek().getFrequency() - currentNode.getFrequency();
    if (cmp == 0)
        cmp = sorted.peek().getWord().compareTo(currentNode.getWord());
}

I'm assuming that getFrequency() returns an integer and that the actual word in a WordNode is accessed by the getWord() method. Using the above we compare first by frequency, and if both frequencies are equal then we compare alphabetically

EDIT :

A nicer solution, define this helper method:

private static boolean compare(LinkedStack<WordNode> sorted, WordNode current) {
    int cmp = sorted.peek().getFrequency() - current.getFrequency();
    if (cmp == 0)
        cmp = sorted.peek().getWord().compareTo(current.getWord());
    return cmp;
}

And then change the first inner loop in your code to this:

while (!sorted.isEmpty() && compare(sorted, currentNode) < 0) {
    //push elements to temp stack
    temp.push(sorted.pop());
}
Improve this answer

4 Comments

getWord() returns a String value. Would this affect how your line cmp = sorted.peek().getWord() - currentNode.getWord(); works since you're subtracting String values? (Never mind... just noticed your edit.)
I don't think this will work, the value of cmp needs to be updated within the while loop, as you are popping off the top of the tmp stack. But then again, its's been a while since I've written a sort.
Wouldn't you need to update cmp in the for loop after the temp.push(sorted.pop()); line
You're right, cmp must be updated at each iteration. I updated my answer, it's starting to look too long. It'd be better to extract the code to a separate method, but you get the idea
0

Use Guava lib:

    public static List<WordNode> sort(List<WordNode> src){
       List<WordNode> result = Lists.newArrayList(src);
       Collections.sort(result, new Comparator<WordNode>(){
           @Override public int compare(WordNode w1, WordNode w2) {
             return ComparisonChain.start()  
                     .compare(w1.frequency, w2.frequency)  
                     .compare(w1.word     , w2.word) 
                     .result(); 
        }});
       return result;
     }
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.