정렬 알고리즘 (5) - 빠른 정렬

0. 원리

빠른 정렬은 교환 정렬을 구분하는 것으로 분치법을 채택했다.분치법은 원문제를 약간의 규모가 더 작지만 구조와 원문제가 비슷한 자문제로 분해하여 점차적으로 자문제를 구하고 마지막으로 자문제의 해를 조합하는 것이 원문제의 해이다.

구분, 하나의 기준을 선택하고 이 기준은 현재의 무질서한 서열을 좌우 두 부분으로 나누며 왼쪽 서브구간 내의 숫자를 모두 기준보다 작게 하고 오른쪽 서브구간 내의 숫자를 모두 기준보다 크게 한다

해답을 구하고 귀속 호출은 좌우 서브 구간에 대해 분해 조작을 한다

하위 구간에 숫자가 하나만 있을 때 귀속이 끝나는데 이때의 서열은 바로 질서 서열이다

위의 설명에서 알 수 있듯이 관건은 바로 이 조작을 구분하는 것이다. 여기서 가장 간단하고 이해하기 쉬운 구분 방법을 사용한다

두 개의 번호를 설정합니다. 하나는 시작 번호start이고 하나는 끝 번호end입니다.무질서 시퀀스의 첫 번째 기록 데이터 [start]를 기준으로 선택합니다..

end를 오른쪽에서 왼쪽으로 스캔하여 첫 번째 숫자가 기준 숫자보다 작을 때까지 시작 시퀀스와 끝 시퀀스에 대응하는 숫자를 교환합니다. 시작 시퀀스에 1을 추가합니다

start를 왼쪽에서 오른쪽으로 스캔하여 첫 번째 숫자가 기준 숫자보다 클 때까지 시작 시퀀스와 끝 시퀀스에 대응하는 숫자를 교환하고 끝 시퀀스를 1

두 번째 세 번째 동작을 반복하여 시작 번호가 끝 번호와 같을 때까지 한다. 이때 기준 숫자는 정확한 위치에 있고 왼쪽의 숫자는 모두 기준 숫자보다 작으며 오른쪽의 숫자는 모두 기준 숫자보다 크다

여기에서도 시뮬레이션을 통해 시퀀스 [2, 8, 1, 5, 3]을 정렬합니다.

partition 0 and 4 start
2 8 1 5 3  (exchange data: 2  1)  1 8 2 5 3 
1 8 2 5 3  (exchange data: 2  8)  1 2 8 5 3 
partition 0 and 4 finish and partition is 1
partition 2 and 4 start
1 2 8 5 3  (exchange data: 8  3)  1 2 3 5 8 
partition 2 and 4 finish and partition is 4
partition 2 and 3 start
partition 2 and 3 finish and partition is 2

1차 이 귀속 호출은 0~4에서 파티션을 진행하고 숫자 2를 기준으로 상기 원리에 따라 두 번 교환한 후 2를 최종 위치 1에 두었다..

2차 귀속 이상 1차에서 얻은 1을 구분하여 2~4, 1~1 두 서열로 나눈다.start===end 왼쪽의 하위 구간과 종료 때문에 2~4 이 하위 서열을 파티션하고 숫자 8을 기준으로 교환한 후 8을 최종 위치 4에 넣었습니다..

제3차는 상기 라운드에서 얻은 4를 나누어 23, 44 두 서열로 나눈다.44 이 서브구간이 종료되고 34 이 서열에 대해partition을 계속 진행하며 숫자 3을 기준으로 하고 교환할 필요가 없으며 새로운 기준은 2이다

제4라운드는 22,33으로 나뉘기 때문에 전체 귀속이 중지되고 서열이 질서정연해진다

1. 실현

private void quickSort(int[] data, int start, int end) {
    if (start < end) {
        System.out.println("partition " + start + " and " + end + " start");
        int partition = partition(data, start, end);
        System.out.println("partition " + start + " and " + end + " finish and partition is " + partition);
        quickSort(data, start, partition - 1);
        quickSort(data, partition + 1, end);
    }
}

private int partition(int[] data, int start, int end) {
    int pivot = data[start];
    while (start < end) {
        // 
        while (start < end && data[end] > pivot) {
            end--;
        }
        if (start < end) {
            swap(data, start++, end);
        }
        // 
        while (start < end && data[start] < pivot) {
            start++;
        }
        if (start < end) {
            swap(data, end--, start);
        }
    }
    data[start] = pivot;
    return start;
}

구체적으로 GitHub/QuickSort 보기 가능

2. 복잡도

빠른 정렬은 불안정한 정렬 알고리즘이다.최악의 경우 시간 복잡도는 O(n²),평균 시간 복잡도는 O(nlogn)입니다.분석 시간의 복잡도는 두 부분으로 나뉘는데 하나는partition 함수이다. 이 함수는 왼쪽에서 오른쪽으로 스캐닝하고 오른쪽에서 왼쪽으로 스캐닝한다. 둘이 같고 분명히 O(n) 복잡도의 조작이고 이것은 고정불변한 것이다.두 번째는 외부의 귀속이다. 변화하는 것은 이 기준치를 얻는 것이다. 만약에 이미 질서수열이 있다면 O(n)를 해야 이 귀속을 끝낼 수 있다.따라서 최악의 경우 O(n²),일반적인 상황에서 기준치가 중간의 크기로 되어 있고 서열을 두 개의 크기 편차가 크지 않은 서열로 나눌 수 있다. 이런 시간 복잡도는 바로 O(logn)이다.
따라서 빠른 정렬을 최적화하려면 기준치의 선택이 좋은 최적화 방향이다.

3. 최적화

빠른 정렬의 최적화 방안이 매우 많은데 여기서 구체적인 실현을 하지 않는다. 왜냐하면 모든 방안은 단독으로 한 편으로 쓸 수 있고 간단한 소개만 할 수 있기 때문이다.

구역 크기에 따라 알고리즘을 조정한다.하위 서열이 어느 정도 작을 때 귀속 호출 빠른 정렬은 필요 없어 보이기 때문에 밸브 값을 설정할 수 있다. 하위 서열 규모가 작은 섬이 어느 정도 될 때 빠른 정렬을 멈출 수 있다. 이때 서열은 비교적 질서정연한 서열이어야 한다. 이때 삽입 정렬을 사용하면 선형에 가까운 복잡도를 얻을 수 있다

랜덤화.이미 정렬된 서열에 대해 최악의 시간 복잡도를 얻을 수 있기 때문에 첫 번째 숫자가 아닌 선택 기준을 임의화하면 최악의 상황을 얻을 확률이 매우 낮고 대부분의 서열이 기대하는 O(nlogn)에 도달할 수 있는 시간 복잡도를 얻을 수 있다

3평균분구법.대기 배열 그룹의 가장 왼쪽, 가장 오른쪽, 가장 중간에 있는 세 원소의 중간 값을 기준으로 빠른 배열을 한다.원리는 랜덤화와 유사하여 최악의 상황을 어느 정도 피할 수 있다..

병행 빠른 정렬.여러 대의 프로세서를 충분히 이용하여 대량의 데이터를 정렬할 수 있다.흥미가 있으면 연구할 수 있다