정렬 방법을 검토하고 테스트합니다. 1부

얼마 전 VKontakte에 대한 댓글에서 저는 프로젝트의 다른 학생 중 한 명과 논쟁을 벌였습니다. 논쟁의 본질은 "누가 이길 것인가"였습니다. 즉, sort()클래스의 메소드 java.util.Arrays또는 자체 작성 간단한 알고리즘인 버블 , 삽입 , 선택 , 쉘 (쉘 알고리즘)의 구현이었습니다. 어떤 사람들에게는 이 질문에 대한 답이 분명할 수 있지만 분쟁이 발생한 이후 양측이 자신의 관점에 찬성하여 "존경받는 출처"를 가지고 있다는 사실에도 불구하고 회색 물질을 확장하는 연구를 수행하기로 결정했습니다. 다양한 알고리즘을 구현하는 과정입니다. 요약: java.util.Arrays.sort() 100,000개 이상의 요소 배열에서는 무조건 선두입니다. 크기가 작을수록 Shell 방법이 때때로 경쟁할 수 있습니다. 고려된 나머지 알고리즘은 완전히 비어 있으며 일부 이국적인 조건에서만 유용할 수 있습니다. 이제 실리콘 uber-device에서 배열이 어떻게 정렬되는지 살펴보겠습니다.

선택 정렬. 선택 항목별 정렬

가장 간단하고 분명한 방법부터 시작해 보겠습니다. 그것의 본질은 Coursera에 대한 그의 비디오 강의에서 Robert Sedgwick이 우리에게 완벽하게 보여줍니다 . (여기서 제가 GIF로 잘못 압축한 애니메이션을 인용하겠습니다): 보기 첫 번째 요소에서 배열을 통해 실행하고, 각 단계에서 우리는 오른쪽에서 현재 요소를 바꾸는 최소 요소를 찾으십시오. 결과적으로 우리는 배열의 최종 버전을 정렬된 형식으로 예약합니다. 다음은 Java에서 이 알고리즘을 구현하는 코드입니다.

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

알고리즘 분석에 따르면 각 패스에서 배열의 나머지 부분을 빗질해야 합니다. 즉, 정확히 N + (N-1) + (N-2) + ... + 1 = N^이 필요합니다. 2/2 비교. 따라서 알고리즘의 복잡도는 O(N^2)입니다. 이것은 무엇을 의미 하는가? 즉, 배열(N)의 요소 수를 2배 늘리면 알고리즘의 실행 시간이 2배가 아니라 2^2 = 4배 늘어납니다. N을 10배 늘리면 작동 시간도 100배 늘어나는 식입니다. Ubuntu 14.4를 실행하는 Core i3 프로세서가 장착된 2012년 노트북에서 다음과 같은 가동 시간을 얻었습니다.

삽입 정렬. 삽입 정렬

여기서는 아이디어가 약간 다릅니다. 다시 한 번 Sedgwick 박사의 애니메이션을 살펴보겠습니다. 앞에 있는 것을 보기 아직 우리가 본 적도 없으며 우리가 남겨둔 모든 것은 항상 순서대로 남아 있습니다. 요점은 원래 배열의 각 새 요소가 더 작은 요소에 "안착"될 때까지 처음으로 "반환"한다는 것입니다. 따라서 우리는 다시 N개의 패스(원본 배열의 각 요소에 대해)를 가지지만 각 패스에서 대부분의 경우 전체 나머지를 보지 않고 일부만 봅니다. 즉, 다음 각 요소를 맨 처음으로 반환해야 하는 경우에만 옵션 1 + (N-1) + (N-2) + … + N = N^2/2를 얻습니다. 입력 정렬된 "역방향" 배열(불운, 불운). 이미 정렬된 배열의 경우(행운이 있습니다) 완전한 공짜가 있을 것입니다. 각 패스마다 단 하나의 비교만 있고 요소는 제자리에 남겨 둡니다. 즉, 알고리즘은 N에 비례하는 시간에 작동합니다. 알고리즘의 결정은 이론상 최악의 경우, 즉 O(N^2)에 의해 결정됩니다. 평균적으로 작동 시간은 N^2/4에 비례합니다. 즉, 이전 알고리즘보다 두 배 빠릅니다. 내 구현에서는 최적이 아닌 순열 사용으로 인해 실행 시간이 Selection의 실행 시간보다 길었습니다. 조만간 글을 수정해서 업데이트할 예정입니다. 다음은 동일한 시스템에서의 코드와 작업 결과입니다.

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

쉘 정렬. 쉘 정렬

똑똑한 사람인 Donald Schell은 1959년에 삽입 알고리즘에서 가장 비용이 많이 드는 경우는 요소가 배열의 시작 부분으로 아주 멀리 돌아올 때라는 것을 알아냈습니다. 일부 패스에서는 요소를 몇 위치만큼 처음으로 되돌립니다. , 또 다른 패스에서는 전체 배열을 거의 통과하여 시작 부분까지 멀고 길다. 여러 요소를 거치면서 동시에 이 작업을 수행할 수 있습니까? 그리고 그는 그런 방법을 찾았습니다. 이는 일반적으로 d-sort 또는 Sedgwick에 따르면 h-sort(h는 hop을 의미한다고 생각함)라고 하는 특수 부분 정렬을 순차적으로 수행하는 것으로 구성됩니다. 예를 들어 3-정렬은 문제의 요소를 이전 요소와 비교하지 않고 두 개를 건너뛰고 3개 위치 뒤의 요소와 비교합니다. 변경된 경우 요소 3 위치와 다시 비교하는 식으로 진행됩니다. 결론은 결과 배열이 "3-정렬"된다는 것입니다. 즉, 요소의 잘못된 위치가 3개 미만의 위치가 됩니다. 이 삽입 알고리즘을 사용하는 것은 쉽고 즐겁습니다. 그런데 "1-sort"는 단순한 삽입 알고리즘에 지나지 않습니다 =) 배열에 h 값을 감소시키면서 h-sort를 순차적으로 적용하면 큰 배열을 더 빠르게 정렬할 수 있습니다. 그 모습은 다음과 같습니다. 보기 여기서의 과제는 부분 정렬의 올바른 순서를 선택하는 방법입니다. 궁극적으로 알고리즘의 성능은 이에 달려 있습니다. 가장 일반적인 것은 Donald Knuth가 제안한 수열입니다. h = h*3 + 1, 즉 1, 4, 13, 40, ... 등 배열 크기의 최대 1/3까지입니다. 이 시퀀스는 적절한 성능을 제공하며 구현하기도 쉽습니다. 알고리즘을 분석하려면 수많은 언어가 필요하며 내 능력을 넘어서는 일입니다. 분석의 폭은 h 시퀀스의 다양한 변형에 의해서도 결정됩니다. 경험적으로, 우리는 알고리즘의 속도가 매우 좋다고 말할 수 있습니다. 직접 확인해보세요: 1초도 안 되는 시간에 백만 개의 요소가! 그리고 여기에 Knut 시퀀스가 ​​포함된 Java 코드가 있습니다.

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

버블 정렬. 버블방식

이것은 고전입니다! 거의 모든 초보 프로그래머가 이 알고리즘을 구현합니다. 너무나 고전적인 작품이라 Sedgwick 박사가 애니메이션을 제작하지도 않았기 때문에 제가 직접 작업을 해야 했습니다. 여기 에서는 각 패스에서 배열을 처음부터 끝까지 순회하면서 순서가 잘못된 이웃 요소를 교체합니다. 결과적으로, 가장 큰 요소는 배열의 끝까지 "부동"(따라서 이름)됩니다. 우리는 배열이 이미 정렬되어 있기를 희망하면서 각각의 새로운 패스를 시작합니다( sorted = true). 구절이 끝날 때 실수를 했다는 것을 알게 되면 새로운 구절을 시작합니다. 여기서 어려운 점은 각 패스에서 (거의) 전체 배열을 탐색한다는 것입니다. 비교는 모든 단계에서 발생하고 교환은 거의 모든 단계에서 발생하므로 이 알고리즘은 가장 느린 알고리즘 중 하나가 됩니다("흔들리는 정렬" 등이 아닌 합리적으로 구현된 알고리즘을 고려한다면). 여기서 공식적으로 복잡도는 O(N^2)와 동일하지만 계수는 삽입 및 선택의 복잡도보다 훨씬 높다는 점이 흥미롭습니다. 알고리즘 코드:

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

작동 시간: 차이를 느껴보세요. 백만 개의 요소에 대해 30분 이상 소요됩니다! 결론: 이 알고리즘을 절대 사용하지 마세요!!!

첫 번째 부분 요약

결과적으로 이러한 알고리즘에 대한 일반 표를 살펴보는 것이 좋습니다. 내장 메소드의 결과와 비교할 수도 있습니다 java.util.Arrays.sort(). 일종의 마법처럼 보입니다. Shell보다 빠른 것이 무엇일까요? 이에 대해서는 다음 부분에서 쓰겠습니다. 여기서는 널리 사용되는 빠른 정렬 알고리즘과 병합 정렬을 살펴보고 기본 유형과 참조 유형에서 배열을 정렬하는 방법의 차이점에 대해 알아보고 이 문제에 대한 매우 중요한 인터페이스에 대해 알아봅니다. Comparable) 아래에서 공부할 수 있습니다. 데이터 테이블을 사용하여 로그 눈금으로 작성된 그래프입니다. 선이 평평할수록 알고리즘이 더 좋습니다 =) 전체 프로젝트를 다운로드하고 스스로 테스트를 실행하려는 사람들을 위해 링크를 유지하십시오: Java 다음 부분에서 만나요! =)