java 정렬하기

1. comparable과 comparator

Java 에서 object를 정렬 하기 위해서는 comparable interface 가 기본적으로 필요하다. 

@Test
public void sortObjects() {
    final String[] strings = {"z", "yy", "abc"};
    final String[] expected = {"abc", "yy", "z"};
	
    Arrays.sort(strings);
    assertArrayEquals(expected, strings);
}

String class는 comparable 인터페이스가 implements된 class 이므로 순서대로 정렬된다. 

comparable이 implements되지 않은 object를 sorting 하려고 하면 컴파일러가 comparable interface가 구현되어 있을거라고 예상하기 때문에 exception이 발생한다.

class Obj {
    private int orderNo;
	
    public Obj(int i) {
        this.orderNo = i;
    }

    public int getOrderNo() {
        return this.orderNo;
    }
}

@Test
public void sortNotComparable() {
    final List<Obj> objects = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        objects.add(new obj(i));	
    }
    // java.lang.ClassCastException: Sorting$Obj cannot be cast to java.lang.Comparable
    Arrays.sort(objects.toArray());
}

Comparable interface를 implements해서 compareTo 메소드를 override하면 sorting을 할 수 있다.

class Obj implements Comparable<Obj>{
    private int orderNo;
    ...
    @Override
    public int compareTo(Obj o) {
        return this.orderNo - o.orderNo;
    }
}

하지만 클래스 외부에서 compare 방법을 변경할 수 없기 때문에 보통 comparable을 설명 할때 natural order sorting(예를 들어 id순서나 날짜 순서 같은 자연스러운 sorting)을 구현할때 사용하라고 하는 경우를 볼 수 있다. 우리가 알고 있는 디자인 패턴에 맞는 방법은, 다양한 sorting방법을 변경하면서 사용하는 것인데, 그래서 comparator 가 필요하다.

class CustumOrder implements Comparator {
    @Override
    public int compare(Obj o1, Obj o2) {
        return o2.getOrderNo() - o1.getOrderNo();
    }	
}

완성된 코드는 아래와 같다.

class Obj {
    private int orderNo;
	
    public Obj(int i) {
        this.orderNo = i;
    }

    public int getOrderNo() {
        return this.orderNo;
    }

    @Override
    public boolean equals(Object other) {
        Obj self = (Obj) other;
        return this.orderNo == self.getOrderNo();
    }
}

class CustumOrder implements Comparator {
    @Override
    public int compare(Obj o1, Obj o2) {
        return o2.getOrderNo() - o1.getOrderNo();
    }	
}

@Test
public void sortNotComparable() {
    final List<Obj> objects = new ArrayList<>();
    for (int i = 0; i < 5; i++) {
        objects.add(new Obj(i));
    }

    final List<Obj> reversedExpectedObjects = Arrays.asList(new Obj(4), new Obj(3), new Obj(2), new Obj(1), new Obj(0));
    final List<Obj> expectedObjects = Arrays.asList(new Obj(0), new Obj(1), new Obj(2), new Obj(3), new Obj(4));
	
    // 내림차순
    Collections.sort(objects, new CustumOrder());
    assertEquals(reversedExpectedObjects, objects);
	
    // 오름차순
    // Comparator가 functional interface이기 때문에 lambda expression을 사용할 수 있다.
    Collections.sort(objects, new Comparator<Obj>() {
        @Override
        public int compare(Obj o1, Obj o2) {
            return o1.getOrderNo() - o2.getOrderNo();
        }
    });
    assertEquals(expectedObjects, objects);
}

2. TreeMap

자바에서 기본 자료구조로 TreeMap을 제공한다. HashMap과 달리 이진트리 자료구조이기 때문에 key를 가지고 comparable과 comparator interface를 사용해서 sorting한다. (그렇기 때문에 hashCode 메소드는 사용하지 않는다.)

@Test
public void treeMapTraversal() {
    final Map<Integer, String> counts = new TreeMap<>();
    counts.put(4, "four");
    counts.put(1, "one");
    counts.put(3, "three");
    counts.put(2, "two");
	
    final Iterator<Integer> keys = counts.keySet().iterator();
    assertEquals("one", counts.get(keys.next()));
    assertEquals("two", counts.get(keys.next()));
    assertEquals("three", counts.get(keys.next()));
    assertEquals("four", counts.get(keys.next()));
}

@Test
public void treeMapTraversalWithComparator() {
    final Map<Integer, String> counts = new TreeMap<>(new Comparator() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
    counts.put(4, "four");
    counts.put(1, "one");
    counts.put(3, "three");
    counts.put(2, "two");
	
    final Iterator<Integer> keys = counts.keySet().iterator();
    assertEquals("four", counts.get(keys.next()));
    assertEquals("three", counts.get(keys.next()));
    assertEquals("two", counts.get(keys.next()));
    assertEquals("one", counts.get(keys.next()));
}