코딩테스트 정렬에 관하여 정리 (Java)

1. primitive type(원시 자료형) 배열의 정렬과 Wrapper Class배열의 정렬은 다르다.

예시를 살펴봅시다.

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 0; i < N; i++)
            bw.write(arr[i] + " \n");
        bw.flush();

이거랑

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Integer[] arr = new Integer[N];

        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 0; i < N; i++)
            bw.write(arr[i] + " \n");
        bw.flush();

 

arr 배열이 int와 Integer의 차이 인데,

Arrays.sort의 구현체는 배열이 primitive type일 때

퀵소트로 정렬하며, 

Wrapper Class일때는

이와 같이 Timsort로 정렬함을 알 수 있다.

 

• Quick sort는
  • 평균 시간 복잡도 : O(NlogN)
  • 최악 시간 복잡도 : O(N2)
• Tim Sort는
  • 평균 시간 복잡도 : O(NlogN)
  • 최악 시간 복잡도 : O(NlogN)

이다. 따라서 같은 문제일 지라도 정렬 기법의 시간복잡도에 따라 시간초과가 날 수 있음에 유의해야한다.

 

2. 내림차순으로 정렬하기

마찬가지로, 기본타입과 레퍼클래스는 내림차순 방법이 다르다.

 

• 기본 타입은 오름차순 정렬 후 거꾸로 출력하는 방법밖에 없다.
• 래퍼 클래스는 Collections.reverseOrder()을 사용해 내림차순 정렬이 가능하다.

구현체를 뜯어보면,

메소드의 매개변수로 Comparator를 받을때, 배열은 T로 받기 때문에 원시타입으로 정렬 할 수 없는 것이다.

3. 커스터마이징

Comparator를 직접 구현체를 만들어서사용할 수도 있다.

 

정렬 알고리즘이 순서를 정할 때 사용할 Compartor를 커스터마이징 한다.

두 원소를 비교했을 때

return 음수 : a1이 a2보다 먼저

return 양수 : a2가 a1보다 먼저

return 0 : 그대로

이므로, 정렬하므로 a2가 a1보다 앞에 위치해야하므로 더 큰 숫자가 앞에 오도록 하여 내림차순이 된다.