빠 른 정렬 의 분석 과 최적화

1. 빠 른 정렬 에 대한 소개
빠 른 정렬 은 정렬 알고리즘 입 니 다. n 개 수 를 포함 하 는 입력 배열 입 니 다. 최 악의 경우 운행 시간 은?Θ(n2)[Θ 더 타 로 읽다.이 최 악의 경우 운행 시간 이 비교적 나 쁘 지만 빠 른 정렬 은 정렬 에 가장 좋 은 실 용적 인 선택 이다.이것 은 평균 상황 에서 의 성능 이 상당히 좋 기 때문이다. 기대 하 는 운행 시간 은?Θ(nlgn), 그리고Θ(nlgn) 기호 에 포 함 된 상수 인 자 는 매우 작다.또한 현지에서 정렬 할 수 있 고 가상 메모리 환경 에서 도 잘 작 동 할 수 있다.
병합 정렬 과 마찬가지 로 빠 른 정렬 도 분 치 법 (Divide and conquer) 을 기반 으로 합 니 다.

분해: 배열 A [p. r] 는 두 개의 (비어 있 을 수 있 음) 하위 배열 A [p. q - 1] 와 A [q + 1. r] 로 나 뉘 어 A [p. q - 1] 중의 모든 요 소 는 A [q] 보다 작 고 A [q + 1. r] 중의 모든 요 소 는 A [q] 보다 크다.이렇게 원소 A [q] 는 그 최종 위치 에 있다.

해결: 재 귀적 호출 을 통 해 빠 른 정렬 을 하고 하위 배열 A [p. q - 1] 와 A [q + 1. r] 를 정렬 합 니 다.

합병: 두 개의 키 배열 은 현지에서 정렬 되 기 때문에 합병 할 필요 가 없고 전체 배열 은 순서 가 있 습 니 다.

의사 코드:

PARTITION(A, p, r)
    x = A[p]
    i = p
    for j=p+1 to r
        do if A[j] <= x
            then i = i+1
                 exchange(A[i],A[j])
    exchange(A[p], A[i])
    return i

QUICKSORT(A, p, r)
    if p < r
        then q = PARTITION(A, p, r)
             QUICKSORT(A, p, q-1)
             QUICKSORT(A, q+1, r)

성능 분석
1. 최 악의 경우
빠 른 정렬 의 최 악의 경 우 는 배열 이 질서 가 있 거나 역순 으로 배 열 된 상황 에서 발생 한다.이렇게 되면 구분 과정 에서 발생 하 는 두 구역 중 하 나 는 요소 가 없고 다른 하 나 는 n - 1 요 소 를 포함한다.이때 알고리즘 의 운행 시간 은 T(n) = T(n-1)+T(0)+Θ(n), 재 귀 식 의 해 T(n)=Θ(n^2) 로 재 귀 적 으로 표시 할 수 있다.빠 른 정렬 알고리즘 의 최 악의 경우 정렬 을 삽입 하 는 것 보다 운행 시간 이 더 좋 지 않다 는 것 을 알 수 있다.
2. 가장 좋 은 상황
만약 에 우리 가 운 이 좋다 면 매번 구분 작업 에서 가장 균형 적 인 구분 을 하면 배열 은 n / 2: n / 2 로 나 눌 것 이다.이때 얻 은 재 귀 식 은 T(n) = 2T(n/2)+Θ(n) 이 고 주 정리 상황 에 따라 얻 을 수 있다 T(n)=Θ(nlgn).
3. 평균 상황
가설 1: 빠 른 배열 의 구분 점 은 매우 비뚤어진다. 예 를 들 어 매번 배열 을 1 / 10: 9 / 10 의 두 개의 서브 구역 으로 나 누 는데 이런 상황 에서 운행 시간 은 얼마 입 니까?운행 시간 재 귀 식 은 T(n) = T(n/10)+T(9n/10)+Θ(n) 이 고 재 귀 트 리 분해 T(n)=Θ(nlgn) 를 사용 합 니 다.구분 점 이 매우 비 뚤 어 졌 을 때 운행 시간 은 여전히Θ(nlgn)。
가설 2: Partition 이 발생 하 는 구분 은 '좋 은 것' 도 있 고 '나 쁜 것' 도 있 으 며 이들 은 교체 되 어 나타난다.이런 평균 상황 에서 운행 시간 은 또 얼마 입 니까?이때 의 재 귀 식 은 (G 는 Good, B 는 Bad) 이다.
G(n) = 2B(n/2) + Θ(n)
B(n) = G(n-1) + Θ(n)
해: G (n) = 2 (G (n / 2 - 1) +Θ(n/2)) + Θ(n) = 2G(n/2-1) + Θ(n) = Θ(nlgn)
이 를 통 해 알 수 있 듯 이 좋 고 차이 점 이 교체 되 어 나타 날 때 빠 른 운행 시간 은 모두 좋 은 구분 과 같이 여전히Θ(nlgn) 。
3. 빠 른 배열 의 최적화
위의 분석 을 통 해 알 수 있 듯 이 질서정연 하거나 역순 을 입력 할 때 빠 른 정렬 이 느 리 고 나머지 상황 에 서 는 양호 하 다.입력 자체 가 정렬 되 었 다 면 큰일 입 니 다.그렇다면 우 리 는 어떻게 모든 입력 에 대해 비교적 좋 은 평균 상황 성능 을 얻 을 수 있 도록 확보 합 니까?앞의 빠 른 정렬 은 기본적으로 배열 의 첫 번 째 요 소 를 주 원 으로 사용 합 니 다.배열 의 요 소 를 주 원 으로 무 작위 로 선택 하면 빠 른 줄 의 운행 시간 은 입력 시퀀스 의 순서 에 의존 하지 않 습 니 다.우 리 는 주 원 을 무 작위 로 선택 한 빠 른 순 서 를 Randomized Quicksort 라 고 합 니 다.
에 세이 화 된 빠 른 정렬 에서 우 리 는 항상 첫 번 째 요 소 를 주 원 으로 선택 하 는 것 이 아니 라 배열 A [p... r] 에서 무 작위 로 요 소 를 선택 한 다음 에 첫 번 째 요소 와 교환 합 니 다.주 원 요 소 는 무 작위 로 선택 되 었 기 때문에 우 리 는 평균 상황 에서 입력 배열 에 대한 구분 이 비교적 대칭 적 이 기 를 기대한다.
의사 코드:

RANDOMIZED-PARTITION(A, p, r)
    i = RANDOM(p, r)
    exchange(A[p], A[i])
    return PARTITION(A, p, r)

RANDOMIZED-QUICKSORT(A, p, r)
    if p < r
        then q = RANDOMIZED-PARTITION(A, p, r)
            RANDOMIZED-QUICKSORT(A, p, q-1)
            RANDOMIZED-QUICKSORT(A, q+1, r)

우 리 는 3 만 개의 요소 의 질서 있 는 서열 에 대해 전통 적 인 빠 른 정렬 과 랜 덤 화 된 빠 른 정렬 을 하고 그들의 운행 시간 을 비교 합 니 다.

/*************************************************************************
    > File Name: QuickSort.cpp
    > Author: SongLee
    > E-mail: [email protected]
    > Created Time: 2014 06 21      10 11 30 
    > Personal Blog: http://songlee24.github.com
 ************************************************************************/
#include<iostream>
#include<cstdlib>  // srand rand
#include<ctime>  // clock_t clock
using namespace std;

void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

//       
int Partition(int A[], int low, int high)
{
    int pivot = A[low];
    int i = low;
    for(int j=low+1; j<=high; ++j)
    {
        if(A[j] <= pivot)
        {
            ++i;
            swap(A[i], A[j]);
        }
    }
    swap(A[i], A[low]);
    return i;
}

//        ，    pivot
int Partition_Random(int A[], int low, int high)
{
    srand(time(NULL));
    int i = rand() % (high+1);
    swap(A[low], A[i]);
    return Partition(A, low, high);
}

//     
void QuickSort(int A[], int low, int high)
{
    if(low < high)
    {
        int pos = Partition(A, low, high);
        QuickSort(A, low, pos-1);
        QuickSort(A, pos+1, high);
    }
}

//        
void QuickSort_Random(int A[], int low, int high)
{
    if(low < high)
    {
        int pos = Partition_Random(A, low, high);
        QuickSort_Random(A, low, pos-1);
        QuickSort_Random(A, pos+1, high);
    }
}

int main()
{
    clock_t t1, t2;
    //      
    int A[30000];
    for(int i=0; i<30000; ++i)
        A[i] = i+1;
        
    t1 = clock();
    QuickSort(A, 0, 30000-1);
    t1 = clock() - t1;
    cout << "Traditional quicksort took "<< t1 << " clicks(about " << ((float)t1)/CLOCKS_PER_SEC << " seconds)." << endl;

    t2 = clock();
    QuickSort_Random(A, 0, 30000-1);
    t2 = clock() - t2;
    cout << "Randomized quicksort took "<< t2 << " clicks(about " << ((float)t2)/CLOCKS_PER_SEC << " seconds)." << endl;

    return 0;
}

실행 결과:

[songlee@localhost ~]$ ./QuickSort 
Traditional quicksort took 1210309 clicks(about 1.21031 seconds).
Randomized quicksort took 457573 clicks(about 0.457573 seconds).
[songlee@localhost ~]$ ./QuickSort 
Traditional quicksort took 1208038 clicks(about 1.20804 seconds).
Randomized quicksort took 644950 clicks(about 0.64495 seconds).

실행 결 과 를 통 해 알 수 있 듯 이 질서 있 는 입력 에 있어 서 랜 덤 버 전의 빠 른 정렬 효율 이 매우 높다.
문제 기록:
우 리 는 두 변 수 를 교환 하 는 값 이 다음 과 같은 세 가지 방법 이 있다 는 것 을 안다.

int tmp = a;  //    
a = b;
b = tmp

a = a+b;  //    
b = a-b;
a = a-b;

a = a^b;  //    
b = a^b;
a = a^b;

그러나 이 프로그램 에서 swap 함수 가 뒤의 두 가지 방법 을 사용 하면 오류 가 발생 할 수 있 습 니 다.방법 2 와 방법 3 은 중간 변 수 를 사용 하지 않 았 기 때문에 교환 값 의 원 리 는 변수의 메모리 유닛 을 직접 조작 하 는 것 이다.만약 에 두 변수 가 대응 하 는 같은 메모리 유닛 이 라면 두 번 의 가감 또는 이동 또는 조작 을 거 쳐 메모리 유닛 의 값 이 0 으로 바 뀌 었 기 때문에 변수 값 교환 을 실현 할 수 없습니다.따라서 교환 값 이 필요 한 변수 가 같은 변수 일 수 있 을 때 세 번 째 변 수 를 사용 하여 교환 을 해 야 합 니 다. 그렇지 않 으 면 변 수 를 제거 합 니 다.