10.3 정렬 교환 (2) 빠 른 정렬

기본 사상
빠 른 정렬 도 전형 적 인 분할 사상 (divide and conquer) 의 운용 이다.분 치 법 에 대해 다음 과 같은 절 차 를 알 아야 한다. 1. 현재 의 큰 문 제 를 몇 개의 키 문제 로 분해 하고 2. 모든 키 문 제 를 해결 해 야 한다. 3. 합 자 문 제 를 해결 하 는 것 은 배열 의 정렬 에 활용 하 는 데 있어 배열 을 둘 로 나 누 어 각각 좌우 로 정렬 한 후에 전체 배열 을 정렬 할 수 있다.위 에서 묘사 한 것 은 바로 정렬 을 병합 하 는 일반적인 사고 이다.한편, 빠 른 정렬 에 대해 약간 다르다. 먼저 하나의 추 축 량 pivot 을 선택 하고 배열 을 세 조각 으로 나 누 었 다. [L][pivot][R] 그 중에서 [L] 은 현재 배열 이 추 축 량 보다 작은 요 소 를 나타 내 고 [R] 은 추 축 량 보다 큰 요 소 를 나타 낸다.이것 은 첫 번 째 분해 과정 을 완성 했다.그 다음 에 이 L, R 두 개의 배열 에 대해 빠 른 순 서 를 매 기 는 것 이 바로 두 번 째 해결 과정 이다.원래 주소 정렬 이기 때문에 마지막 단계 에서 하위 문 제 를 해결 하 는 과정 은 생략 할 수 있 습 니 다.(원래 주소 의 문 제 는 다음 에 서술 한다.) 따라서 빠 른 정렬 과 관련 된 핵심 문 제 는 적절 한 추 축 량 을 어떻게 선택 하고 배열 을 어떻게 구분 하 느 냐 하 는 것 이다.교재 의 실현 에서 흔히 A [1], 즉 첫 번 째 요 소 를 중심 으로 한다.물론 개선 방법 은 매번 무 작위 로 배열 에서 하나의 요 소 를 추축 으로 선택 하 는 것 이다.추축 을 선택 한 후에 구분 을 해 야 한다. 즉, 추축 을 적당 한 위치 에 놓 아 추축 왼쪽 의 요 소 를 모두 추축 보다 작 게 하고 오른쪽 요 소 는 모두 그 보다 크다.구분 하 는 과정 은 2.2 절 순서 표 의 일부 알고리즘 디자인 에서 도 서술 되 었 는데 여기 서 생략 했다.
이루어지다
이곳 은 Hoare 의 구분 방법 을 사용 하여 빠 른 정렬 을 실현 했다.Hoare 방법의 사상 은 양쪽 을 가운데 로 끼 우 고 예 정 된 조건 을 만족 시 키 지 못 하면 위 치 를 교환 하 는 것 이다.양쪽 을 끼 우 는 과정 에서 양쪽 지침 i 와 j 가 어 긋 나 거나 경 계 를 넘 지 않도록 확보 해 야 한다.주의해 야 할 점 은 재 귀 출구 에 있 으 니 잘 고려 해 야 한다.

/**
*     
* @param std::vector<_ty> & a       a
* @param int begin                 
* @param int end                 
*/
template<typename _Ty>
void quick_sort(std::vector<_ty/> & a, int begin, int end){
    if (end - begin <= 1)
        return;
    //        ，     Hoare    ，   
    //              。
    _Ty pivot = a[begin];
    int i = begin , j = end;
    while (i < j){
        while (j > i && a[j] > pivot)    //      j>i
            j--;
        a[i] = a[j];
        while (i < j && a[i] < pivot)
            i++;
        a[j] = a[i];
    }
    a[i] = pivot;
    output_list(a);
    //         
    quick_sort(a, begin, i - 1);
    quick_sort(a, i + 1, end);
}

재 귀 알고리즘 은 매번 교체 되 는 상황 을 직접 출력 하기 어렵 기 때문에 매번 구분 이 완 료 된 후에 한 번 만 출력 하여 정렬 상황 을 관찰 합 니 다.테스트 데이터 5 4 11 18 1 70 35 90 100 2 에 대해 다음 과 같은 출력 을 얻 을 수 있 습 니 다.

2       4       1       5       18      70      35      90      100     11
1       2       4       5       18      70      35      90      100     11
1       2       4       5       11      18      35      90      100     70
1       2       4       5       11      18      35      90      100     70
1       2       4       5       11      18      35      70      90      100
1       2       4       5       11      18      35      70      90      100

시간 과 공간 복잡 도
일반적으로 빠 른 정렬 의 평균 시간 복잡 도 는 O (nlogn), 최 악의 시간 복잡 도 O (n2) 라 고 생각한다.재 귀 는 스 택 깊이 문 제 를 고려 해 야 하기 때문에 평균 적 인 공간 복잡 도 는 O (logn) 이 고 최 악의 공간 복잡 도 는 O (n) 이다.평균 적 인 상황 을 이해 하기 어렵 지 않다.매번 추 축 량 을 선택 할 때마다 배열 을 등분 하기 때문에 높이 가 logn 인 재 귀 나 무 를 얻 었 다.최 악의 경 우 는 매번 추 축 량 을 선택 한 후에 얻 은 구분 에서 발생 한다. 추 축 량 은 배열 의 가장자리 위치 (A [1] 또는 A [n]) 에 위치 하고 이 재 귀 나 무 는 한쪽 으로 넘 어 진 이 진 나무 로 퇴화 된다.매번 첫 번 째 요소 나 마지막 요 소 를 중심 축 으로 구분 하 는 상황 에서 데이터 가 거의 질서 가 있 는 상황 에서 빠 른 정렬 은 매우 비효 율 적 이다.그래서 추축 의 선택 은 일반적으로 더 좋 은 방법 을 취한 다.그리고 무 작위 로 선택 한 중심 축 에 있어 기대 시간 도 O (nlgn) 이 고 최 악의 경우 역시 O (n2) 이다.