2
\$\begingroup\$

Given a linked list of 0s, 1s and 2s, sort it. Looking for code review, optimizations and best practices

public final class SortZeroesOnesTwos {

    private Node first;
    private Node last;
    private int size;

    public SortZeroesOnesTwos(List<Integer> items) {
        for (Integer item : items) {
            add(item);
        }
    }
    public void add(Integer item) {
        Node node = new Node(item);
        Node l = last;
        last = node;
        if (first == null) {
            first = node;
        } else {
            l.next = node;
        }
        size++;
    }

    private static class Node {
        private int item;
        private Node next;

        public Node(int item) {
            this.item = item;
        }
    }

    public void sortZeroesOnesAndTwos() {
        int[] a = new int[3];

        Node node = first;
        while (node != null) {
            a[node.item] = a[node.item] + 1; 
            node = node.next;
        }

        node = first;
        int i = 0;
        while (node != null) {
            if (a[i] == 0) { 
                i++; 
            } else { 
                node.item = i;
                node = node.next;
                a[i] = a[i] - 1;
            }
        }
    }

    public int[] toArray() {
        int[] result = new int[size];
        int i = 0;
        for (Node x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }
 }


public class SortZerosOnesTwosTest {

    @Test
    public void test1() {
        SortZeroesOnesTwos sortList = new SortZeroesOnesTwos(Arrays.asList(0, 1, 2, 1, 2, 0));
        sortList.sortZeroesOnesAndTwos();
        int[] expected = {0, 0, 1, 1, 2, 2};
        assertTrue(Arrays.equals(expected, sortList.toArray()));
    }


    @Test
    public void test2() {
        SortZeroesOnesTwos sortList2 = new SortZeroesOnesTwos(Arrays.asList(1, 2, 1, 2));
        sortList2.sortZeroesOnesAndTwos();
        int[] expected2 = {1, 1, 2, 2};
        assertTrue(Arrays.equals(expected2, sortList2.toArray()));
    }


    @Test
    public void test3() {
        SortZeroesOnesTwos sortList3 = new SortZeroesOnesTwos(Arrays.asList(0, 2, 0, 2));
        sortList3.sortZeroesOnesAndTwos();
        int[] expected3 = {0, 0, 2, 2};
        assertTrue(Arrays.equals(expected3, sortList3.toArray()));
    }

    @Test
    public void test4() {
        SortZeroesOnesTwos sortList4 = new SortZeroesOnesTwos(Arrays.asList(0, 1, 0, 1));
        sortList4.sortZeroesOnesAndTwos();
        int[] expected4 = {0, 0, 1, 1};
        assertTrue(Arrays.equals(expected4, sortList4.toArray()));
    }
}
\$\endgroup\$
5
\$\begingroup\$

The mash-up you continue to have with Objects and primitives is something that is easy to resolve, yet you don't. Is there some reason I am missing why it is important to convert your data to an Integer Object before converting it back to an int?

public void add(Integer item) {

Why can't that be:

public void add(int value) {

???? Your Node class stores it as an int, so there is no reason to do the multiple conversions.

The algorithm you have used for the 'sorting' is similar to what I would do. There are a few nitpicks though (one of them is not so small....):

  1. Use Post-increment and Post-Decrement operators:

    a[node.item] = a[node.item] + 1;
    

    and

    a[i] = a[i] - 1;
    

    should be:

    a[node.item]++;
    

    and

    a[i]--;
    
  2. Why use a linked list at all? Seriously, what does the Node concept buy you? This problem could easily be solved with a primitive array (... or an ArrayList, or LinkedList if you were not using primitives .....). If your data was stored as an array, it would be as simple as:

    public void sortZeroesOnesAndTwos() {
        int[] itemcount = new int[3];
    
        for (int item : data) {
            itemcount[item]++; 
        }
    
        int pos = 0;
        for (int item = 0; item < a.length; item++) {
            while (itemcount[item]-- > 0) {
                data[pos++] = item;
            }
        }
    }
    
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ About point 1., I think it is more readable to leave a[i] = a[i] - 1. \$\endgroup\$ – toto2 Jul 3 '14 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.