정렬 메소드 관련 이야기

흔히 아는 정렬 메소드로는

 

Arrays.sort

 

Collections.sort 

 

이 두 개가 있다.

 

두개의 특징은 아래와 같다.

 

Arrays.sort

• dual-pivot QuickSort 알고리즘 사용
• 평균 시간 : O(NlogN)
• 최악 시간 : O(N^2)
• Stable 하지 않다

Collections.sort

• TimeSort ( merge sort + insertion sort)
• 시간복잡도 : O(N) ~ O(NlogN) 보장  -> insertion의 최선 O(N) + 합병정렬의 최악 O(NlogN)
• Stable 하다

 

간혹 알고리즘 문제 풀다가 보면 Arrays.sort로 풀면 안풀리는데 Collections.sort로 풀면 풀리는 경우가 있다.

그런 경우는 테스트 케이스에 O(N^2)가 걸리도록 하는 케이스가 존재하기 때문이다.

그렇기 때문에 만약 시간이 오버되면 Collections.sort를 써보는게 좋을 것 같다.

더불어 Stable 특성을 원하는 문제라면 더욱 더 그렇다

 

하지만 Counting Sort 로 풀 수 있는 것들이 있다면 메소드 쓰지말고 이걸로 푸는게 좋을 듯

진짜 빠르다..

 

추가적으로 다중 배열에서 Arrays.sort 메소드는

 

// arr 은 String[][] 배열이다.
// arr[][0] = 나이 ,  arr[][1] = 이름
Arrays.sort(arr, new Comparator<String[]>() {
    @Override
    public int compare(String[] o1, String[] o2) {
        return Integer.parseInt(o1[0]) - Integer.parseInt(o2[0]);
    }
});

이런 식으로 비교해주면 되는데 배열 첫번째 값을 비교한 후 또 비교할게 있다면 if문으로 두번째 값을 비교해주거나 하면된다. 저기 예시는 나이로 정렬을 하되 만약 같다면 기존 배열 순서대로 (Stable)처리하라고 해서 저렇게 적은거다. 

만약 나이가 같은 경우 이름으로 비교해라라고 하면 if(나이 비교 ) else (이름 비교) 이렇게 처리하면 정렬된다.