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

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

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

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

0. 원리

1. 실현

2. 복잡도

3. 최적화

좋은 웹페이지 즐겨찾기