windend
62
2021-04-07 09:03:52
2
133

java.util.Array에서 sort메소드가 어떻게 구현되어있는지 확인하는 방법문의


java.util.Array에서 sort메소드가 어떻게 구현되어있는지 확인하는 방법 알 수 있을까요?

0
  • 답변 2

  • 연습용더미1
    591
    2021-04-07 09:20:51 작성 2021-04-07 09:22:17 수정됨

    모든 클래스나 메서드가 그렇지만, Ctrl 누르고 사용중인 클래스나 메서드를 클릭하면 됩니다.

    확인해보니 DualPrivotQuicksort라는 클래스의 sort 메서드를 그대로 사용하네요. 매개변수만 받은 값에 따라 적절히 변경해주네요.

    아래가 DualPivotQuicksort의 sort 메서드입니다.


    /**
         * Sorts the specified range of the array using the given
         * workspace array slice if possible for merging
         *
         * @param a the array to be sorted
         * @param left the index of the first element, inclusive, to be sorted
         * @param right the index of the last element, inclusive, to be sorted
         * @param work a workspace array (slice)
         * @param workBase origin of usable space in work array
         * @param workLen usable size of work array
         */
        static void sort(int[] a, int left, int right,
                         int[] work, int workBase, int workLen) {
            // Use Quicksort on small arrays
            if (right - left < QUICKSORT_THRESHOLD) {
                sort(a, left, right, true);
                return;
            }
    
            /*
             * Index run[i] is the start of i-th run
             * (ascending or descending sequence).
             */
            int[] run = new int[MAX_RUN_COUNT + 1];
            int count = 0; run[0] = left;
    
            // Check if the array is nearly sorted
            for (int k = left; k < right; run[count] = k) {
                // Equal items in the beginning of the sequence
                while (k < right && a[k] == a[k + 1])
                    k++;
                if (k == right) break;  // Sequence finishes with equal items
                if (a[k] < a[k + 1]) { // ascending
                    while (++k <= right && a[k - 1] <= a[k]);
                } else if (a[k] > a[k + 1]) { // descending
                    while (++k <= right && a[k - 1] >= a[k]);
                    // Transform into an ascending sequence
                    for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                        int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
                    }
                }
    
                // Merge a transformed descending sequence followed by an
                // ascending sequence
                if (run[count] > left && a[run[count]] >= a[run[count] - 1]) {
                    count--;
                }
    
                /*
                 * The array is not highly structured,
                 * use Quicksort instead of merge sort.
                 */
                if (++count == MAX_RUN_COUNT) {
                    sort(a, left, right, true);
                    return;
                }
            }
    
            // These invariants should hold true:
            //    run[0] = 0
            //    run[<last>] = right + 1; (terminator)
    
            if (count == 0) {
                // A single equal run
                return;
            } else if (count == 1 && run[count] > right) {
                // Either a single ascending or a transformed descending run.
                // Always check that a final run is a proper terminator, otherwise
                // we have an unterminated trailing run, to handle downstream.
                return;
            }
            right++;
            if (run[count] < right) {
                // Corner case: the final run is not a terminator. This may happen
                // if a final run is an equals run, or there is a single-element run
                // at the end. Fix up by adding a proper terminator at the end.
                // Note that we terminate with (right + 1), incremented earlier.
                run[++count] = right;
            }
    
            // Determine alternation base for merge
            byte odd = 0;
            for (int n = 1; (n <<= 1) < count; odd ^= 1);
    
            // Use or create temporary array b for merging
            int[] b;                 // temp array; alternates with a
            int ao, bo;              // array offsets from 'left'
            int blen = right - left; // space needed for b
            if (work == null || workLen < blen || workBase + blen > work.length) {
                work = new int[blen];
                workBase = 0;
            }
            if (odd == 0) {
                System.arraycopy(a, left, work, workBase, blen);
                b = a;
                bo = 0;
                a = work;
                ao = workBase - left;
            } else {
                b = work;
                ao = 0;
                bo = workBase - left;
            }
    
            // Merging
            for (int last; count > 1; count = last) {
                for (int k = (last = 0) + 2; k <= count; k += 2) {
                    int hi = run[k], mi = run[k - 1];
                    for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                        if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
                            b[i + bo] = a[p++ + ao];
                        } else {
                            b[i + bo] = a[q++ + ao];
                        }
                    }
                    run[++last] = hi;
                }
                if ((count & 1) != 0) {
                    for (int i = right, lo = run[count - 1]; --i >= lo;
                        b[i + bo] = a[i + ao]
                    );
                    run[++last] = right;
                }
                int[] t = a; a = b; b = t;
                int o = ao; ao = bo; bo = o;
            }
        }


  • 마사키군
    1k
    2021-04-07 09:21:32

    자바는 오픈소스니까 소스코드를 보면 되겠지요.

    구글에다가 java util array sort source 검색하시면 소스코드 자체는 잔뜩 나오는데, 개인적으로는 URL에 http://hg.openjdk.java.net 들어가는 것으로 살펴보시면 되지 않을까 싶습니다.

    http://hg.openjdk.java.net 는 JDK 공식 저장소라고 알고 있어요.

  • 로그인을 하시면 답변을 등록할 수 있습니다.