投稿した質問数 30

1

와.. 저는 간단하게라도 답해주셔도 감사한데
이렇게 자세하게 알려주시니 몸 둘 바를 모르겠습니다;;

덕분에 자바뿐만 아니라 정렬 알고리즘에 대해 더 좀 더 꼼꼼히 생각해보고 다시 공부해봐야겠다는 생각을 해봅니다.

답변 너무 감사합니다!

1

안녕하세요? 좋은 질문 감사하게 잘 들었습니다.

먼저 Collections.sort()의 내부 동작 원리를 일일이 다 설명 드리기에는 시간이 너무 모자릅니다. 질문자님께서 이해되게 충분한 설명을 하려면 Collections 내부 코드를 일일이 다 설명을 드려야 되는데, 내부 코드를 제가 100 퍼센트 다 완벽하게 이해하고 있는것도 아니기때문에 제가 설명해서 완벽하게 이해시켜드리는건 힘들것 같아요.

다만 "List 객체 cars의 각 원소는 어떻게 선택(?)되어 2개의 파라미터로 각각 들어오게 되는건가요?" 이 질문에 대해서는 대략적으로는 설명을 드릴게요.

이걸 설명 드리려면 내부 코드를 볼 수 밖에 없는데 아무튼 간단하게 살펴보겠습니다.

먼저 Collections.sort( )를 타고 들어가보면 아래 코드를 만날 수 있는데요.

==== List.java ====

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

Object[ ] a는 cars 리스트를 배열로 바꾼게 되겠죠? 저희가 다시 살펴 보아야 할 부분은 Arrays.sort(a, (Comparator) c); 인데요. 여기를 다시 들어가보겠습니다.

==== Arrays.java ====

public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        sort(a);
    } else {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            TimSort.sort(a, 0, a.length, c, null, 0, 0);
    }
}

 여기에서 정렬 방식이 두가지로 나뉘는데요. 하나는 legacyMergeSort( )이고, 또 하나는 TimSort.sort( )인데, legacyMergeSort( )는 정렬 알고리즘 중에서 병합 정렬을 의미합니다. 그리고 TimSort.sort( ) 는 Tim Peters 라는 분이 만든 정렬 알고리즘인데 Insertion sort(삽입 정렬)와 Merge sort(병합 정렬)를 결합해서 만든 정렬 알고리즘입니다. System Property를 따로 설정하지 않는 이상 Java 에서는 기본적으로 legacyMergeSort( ) 대신에 TimSort.sort( ) 를 사용하는데요. Tim sort가 Merge sort보다 조금 더 나은 성능을 낸다고 하는군요. TimSort 에 대해서는 설명이 잘 되어 있는 별도 링크를 맨 하단에 링크로 남겨 둘게요.

그러면 TimSort.sort( ) 안을 한번 살펴보겠습니다.

==== TimSort.java ==== 

static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
                     T[] work, int workBase, int workLen) {
    assert c != null && a != null && lo >= 0 
                         && lo <= hi && hi <= a.length;

    int nRemaining  = hi - lo;
    if (nRemaining < 2)
        return;  // Arrays of size 0 and 1 are always sorted

    // If array is small, do a "mini-TimSort" with no merges
    if (nRemaining < MIN_MERGE) {
        int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
        binarySort(a, lo, hi, lo + initRunLen, c);
        return;
    }

   
    TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
    int minRun = minRunLength(nRemaining);
    do {
        // Identify next run
        int runLen = countRunAndMakeAscending(a, lo, hi, c);

        // If run is short, extend to min(minRun, nRemaining)
        if (runLen < minRun) {
            int force = nRemaining <= minRun ? nRemaining : minRun;
            binarySort(a, lo, lo + force, lo + runLen, c);
            runLen = force;
        }

        // Push run onto pending-run stack, and maybe merge
        ts.pushRun(lo, runLen);
        ts.mergeCollapse();

        // Advance to find next run
        lo += runLen;
        nRemaining -= runLen;
    } while (nRemaining != 0);

    // Merge all remaining runs to complete sort
    assert lo == hi;
    ts.mergeForceCollapse();
    assert ts.stackSize == 1;
}

소스 코드가 꽤 복잡해 보이는데요. 결론만 얘기하자면 Tim sort 방식에서는 정렬할 원소의 개수가 일정 기준보다 작을 경우에는 binarySort( )라는 메서드를 호출해서 먼저 정렬을 하는데요. 위 코드에서 첫번째 빨간색으로 된 binarySort( )의 경우 정렬할 배열의 개수가 기준 이하일 경우, merge sort도 필요 없이 binarySort( ) 만으로 정렬을 끝내버리는걸 볼 수 가 있죠.

저희 예제는 정렬할 car 객체의 개수가 5개 밖에 안되기 때문에 binarySort만 진행하고 끝내겠죠?

그럼 binarySort( ) 의 내부 코드를 잠깐 살펴보겠습니다.

==== Timsort.binarySort( ) ===

private static <T> void binarySort(T[] a, int lo, int hi, int start,
                                   Comparator<? super T> c) {
    assert lo <= start && start <= hi;
    if (start == lo)
        start++;
    for ( ; start < hi; start++) {
        T pivot = a[start];

        int left = lo;
        int right = start;
        assert left <= right;
        /*
         * Invariants:
         *   pivot >= all in [lo, left).
         *   pivot <  all in [right, start).
         */
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (c.compare(pivot, a[mid]) < 0)
                right = mid;
            else
                left = mid + 1;
        }
        assert left == right;

        
        int n = start - left;  // The number of elements to move
        
        switch (n) {
            case 2:  a[left + 2] = a[left + 1];
            case 1:  a[left + 1] = a[left];
                     break;
            default: System.arraycopy(a, left, a, left + 1, n);
        }
        a[left] = pivot;
    }
}

binarySort란 정확하게 얘기하자면 Binary Insertion Sort(이진 삽입 정렬)인데요. 삽입 정렬의 성능을 개선한 정렬 알고리즘이라고 보시면 되겠습니다. Binary Insertion Sort에 대해서도 관련 링크를 남겨 두도록 할게요.

위 소스 코드에서 저희가 궁금한것은 Comparator의 compare( ) 메서드에 2개의 파라미터가 어떻게 선택되어 입력되느냐 하는 것인데요.

중간 정도에 보면 빨간색으로 된 if(c.compare(pivot, a[mid]) < 0) 이라는 코드가 보이시죠?

질문자님께서 궁금해하시는 부분이 저 코드에 있습니다. ^^;;

Binary Insertion sort 정렬에서는 삽입(Insertion)되어야 할 지점을 찾기 위해 Binary Search(이진 탐색)를 사용하는데요. Binary Search에서는 탐색을 하기 위해 left, right 그리고 mid(기준값)가 필요하다는건 잘 아실거라고 생각을 합니다. 위 코드에서는 Comparator.compare( )를 사용해서 right 값을 찾고 있는걸 보실 수가 있죠? 즉, while문에서 Binary Search가 끝날때까지 계속 루프를 돌면서 Comparator.compare( )로 right 값을 찾고 있는 것입니다. 

이 말을 다시 해보자면 Comparator.compare( ) 에 입력되는 car 객체들이 직접적으로 정렬이 된다기 보다는 특정 정렬 알고리즘에서 정렬을 정상적으로 수행하기 위한 어떤 기준을 찾아주는 역할을 한다고 생각하는게 이해하기 쉬울것 같아요. 이건 제 개인적인 생각이기때문에 다른분들의 의견은 다를수도 있겠지만요.

질문에 대한 답변이 충분한지 솔직히 자신은 없지만 아무튼 학습하시는데 조금이라도 도움이 되셨으면 좋겠네요.

아래는 Tim Sort와 Binary Insertion Sort의 관련 링크이니 한번 읽어보시는것도 괜찮을듯 싶어요.

그럼 좋은 밤 되시고, 또 뵐게요.

- Tim Sort 관련 링크: https://d2.naver.com/helloworld/0315536

- Binary Insertion Search 관련 링크: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=rhaosoversan&logNo=221377149974