코테연습 - 정렬

이번주는 코딩테스트 정렬 알고리즘에 대해 정리해볼것이다.

우선 정렬의 종류에는 선택 정렬, 버블 정렬, 삽입 정렬, 병합 정렬 ,퀵 정렬, 힙 정렬, 계수 정렬 등 여러가지 종류가 존재한다.

모든 정렬을 설명하는게 좋을 수 있지만 코딩테스트에서 사용되는건 퀵, 삽입, 병합 정렬 3종류가 주로 사용되기 때문에 3가지 정렬만 간단하게 정리하고 갈것이다.

 

- 퀵 정렬 (Quick Sort)

우선 퀵 정렬이다. 보통 퀵정렬은 기본타입들을 정렬할때 사용된다. ex) int[], double[], char[] 등등

이제 퀵정렬의 메커니즘을 알아보자 

 

 

step1 : 우선 pivot 선정한다.

 

step2 : low 포인터를 pivot 이상의수가 나올때까지 이동시킨다(왼 -> 오). high 포인터는 pivot 이하의수가 나올때까지 이동(오 -> 왼) 포인터가 멈추면 해당 인덱스의 해당하는 원소들을 교환한다.

 

step3 : step2 와 같은 조건으로 다시 포인터를 이동시켜준다.

 

step4 : low와 high가 엇갈릴때 까지 같은 조건으로 포인터를 이동시키고 교환한다.

 

step5 : 엇갈린 지점에서 pivot과 엇갈린 지점의 원소를 교환한다.

 

step6 : pivot이 교환된 지점은 원소가 고정되고 pivot을 기준으로 왼쪽 오른쪽을 분할시켜 step1 ~ step5의 과정을 반복한다.

 

이러한 퀵정렬이 사용되는 아주 간단한 예시를 보자

int[] arr = {5, 2, 8, 3, 1};
Arrays.sort(arr);

내부적으로 퀵정렬을 사용해서 오름차순 정렬을 해주는 간단한 예시이다. 중요한것은 기본타입일 경우에만 퀵정렬이 사용된다는것이다.

이제 퀵정렬의 시간복잡도를 알아보자

평균적인 시간복잡도는 O(N log N)이다. 하지만 pivot 선택이 나쁘면 최악의 경우 O(N^2)의 시간복잡도가 나올 수 있다. 이러한 최악을 대비하기 위해서 Arrays.sort의 경우 Dual-Pivot QuickSort라는 변형 알고리즘을 사용해 이 문제를 회피한다고 한다.

 

 

그 다음은 TimSort 다 맨처음에 퀵, 병합, 삽입 3가지만 쓴다면서 갑자기 웬 TimSort라고 할수 있지만

사실은 객체를 정렬할때 사용하는 Comparator, Comparable, 람다 등등은 이 TimSort를 이용한다. 이 TimSort가 무엇이냐면 그냥 단순히 더 좋은 정렬 성능을 위해 병합 + 삽입을 합친 하이브리드 정렬이라 생각하면된다. 코딩테스트때문에 이 정렬을 자세히는 알 필요 없기 때문에 지금은 이런게 있다만 설명하고 바로 삽입정렬을 설명해보겠다.

 

- 삽입 정렬 (Insertion Sort)

 

 

삽입 정렬은 1번째 인덱스부터 시작해서 해당 자리의 적절한원소를 찾아서 삽입해주는것처럼 보여서 삽입 정렬이라 한다.

메커니즘은 크게 어렵지 않다. 오히려 너무 간단하다.

먼저 1번째 인덱스 자리에서 시작한다. 그 후 1 ~ n 번째 인덱스 까지 돌것이다.

n번째 인덱스의 원소를 n - 1, n - 2 .... 0 까지 비교해줘서 자리를 교환해주는 것이다.

 

작은 데이터나 부분적으로 정렬된 배열에 효과적이고

시간 복잡도는 최선의 경우 O(N), 평균의 경우O(N^2),  최악의 경우 O(N^2) 이다.

다음은 병합 정렬이다.

 

- 병합 정렬 (Merge Sort)

 

너무 간단하지만 병합정렬의 메커니즘을 알아보자

1. 모든 원소가 하나가 될때까지 반으로 쪼갠다.

2. 이제 정렬하면서 병합을 시작한다. 위의 그림대로다.

시간 복잡도는 최선, 평균, 최악 모두 O(N log N) 이다. 그 이유는 입력 데이터의 정렬 상태에 크게 영향받지 않기 때문이다.

 

이제 정렬들의 알고리즘을 알아봤으니 실전에서 어떤 방식으로 문제를 풀어야 할지 알아보자

https://www.acmicpc.net/problem/10825

이 문제가 적절한 예시인거 같아 가져와 봤다.

 

먼저 Comparator를 사용한 방식이다.

 

public class S_4_10825 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Score[] scores = new Score[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String name = st.nextToken();
            int language = Integer.parseInt(st.nextToken());
            int english = Integer.parseInt(st.nextToken());
            int math = Integer.parseInt(st.nextToken());
            scores[i] = new Score(name, language, english, math);
        }

        Arrays.sort(scores, (a, b) -> {
            if (a.language != b.language) {
                return b.language - a.language;
            }
            if (a.english != b.english) {
                return a.english - b.english;
            }
            if (a.math != b.math) {
                return b.math - a.math;
            }
            return a.name.compareTo(b.name);
        });

        for (Score score : scores) {
            System.out.println(score.name);
        }
    }


    public static class Score {
        String name;
        int language;
        int english;
        int math;

        public Score(String name, int language, int english, int math) {
            this.name = name;
            this.language = language;
            this.english = english;
            this.math = math;
        }
    }
}

 

그리고 Comparable을 사용한 방식이다.

public class S_4_10825_V2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Score[] scores = new Score[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String name = st.nextToken();
            int language = Integer.parseInt(st.nextToken());
            int english = Integer.parseInt(st.nextToken());
            int math = Integer.parseInt(st.nextToken());
            scores[i] = new Score(name, language, english, math);
        }

        Arrays.sort(scores);

        for (Score score : scores) {
            System.out.println(score.name);
        }
    }


    public static class Score implements Comparable<Score>{
        String name;
        int language;
        int english;
        int math;

        public Score(String name, int language, int english, int math) {
            this.name = name;
            this.language = language;
            this.english = english;
            this.math = math;
        }

        @Override
        public int compareTo(Score other) {
            if (this.language != other.language) {
                return other.language - this.language;
            }

            if (this.english != other.english) {
                return this.english - other.english;
            }

            if (this.math != other.math) {
                return other.math - this.math;
            }

            return this.name.compareTo(other.name);
        }
    }
}

 

자 이제 두가지 방법이 존재하는것은 알고 둘 모두 풀 수 있다는건 알겠는데 Comparator가 뭐고 Comparable은 뭔데? 이제부터 알아보자

우선 두 방법 모두 객체를 비교하는 방식이기에 TimSort를 사용했을 것이다.

 

이제 Comparable 과 Comparator의 차이를 간단히 알아보자 

 

Comparable은 Comparable<T>를 클래스 내부에 compareTo 메서드를 오버라이드해서 구현해야한다. 하지만 Comparator와의 차이점을 말하자면 Comparator는 여러 정렬기준을 만들어놓고 골라서 쓰는게 가능하지만 Comparable은 하나의 정렬 기준만 설정이 가능하다. Comparator는 객체 외부에서 정렬기준을 정의하고 정렬을 하는것이지만 위에서 말한것처럼 여러 정렬기준들을 만들어두고 골라 쓰는게 가능하다. 또한 Comparator는 위의 코드처럼 람다식을 이용 할 수 도있고 compare(T a, T b)를 사용해서 비교 할 수 도 있다.

Comparator가 람다식을 사용 할 수 있는 이유는 Comparator가 함수형 인터페이스이기 때문이다. 함수형 인터페이스는 단 하나의 추상메서드만 가지고 Comparator의 경우 compare(T a, T b)의 추상메서드를 하나 가지고 있는것이다. 위의 코드처럼 람다식을 사용하지 않는다면 아래와 같이 표현해야 할것이다. 

Comparator<Score> comparator = new Comparator<Score>() {
    @Override
    public int compare(Score a, Score b) {
        if (a.language != b.language) {
            return b.language - a.language;
        }
        if (a.english != b.english) {
            return a.english - b.english;
        }
        if (a.math != b.math) {
            return b.math - a.math;
        }
        return a.name.compareTo(b.name);
    }
};
Arrays.sort(scores, comparator);

물론 람다식을 이용하는게 훨씬 코드가 깔끔해진다. 람다식을 이용한 저 코드를 더 간결하게 표현할 수 있는데 그 코드는 아래와 같다.

Arrays.sort(scores, Comparator
        .comparingInt((Score s) -> -s.language)
        .thenComparingInt(s -> s.english)
        .thenComparingInt(s -> -s.math)
        .thenComparing(s -> s.name));

 

글로만 보면 복잡하니 Comparable, Comparator의 차이를 표로 정리해보자

	Comparable	Comparator
정의 위치	클래스 내부에서 직접 구현	클래스 외부에서 별도로 구현 가능
인터페이스	Comparable<T> -> compareTo(T o) 구현	Comparator<T> -> compare(T o1, T o2)
정렬 기준	1개만 가능	여러 기준 정의 가능
사용법	Arrays.sort(arr)	Arrays.sort(arr, comparator)
활용	기본 정렬 기준 필요할 때	상황에 따라 정렬 기준 바꿀 때 (기준이 여러개니까)

 

지금 글은 배열을 기준으로 설명했지만 배열대신 List같은 자료구조가 들어온다면 Arrays.sort 대신 Collections.sort를 이용하면 될것이다.

 

참고자료

 

[알고리즘/정렬] 2. 퀵 정렬(Quick Sort)

 

 

[알고리즘] 삽입정렬(insertion Sort) - JAVA(자바)

 

 

[Algorithm] Sort #4 - 병합 정렬 Merge Sort