데이터 구조 | 빠 른 정렬, 2 번 빠 른 정렬, 3 번 빠 른 정렬

빠 른 정렬, 2 번 빠 른 줄, 3 번 빠 른 줄
1. 빠 른 정렬
1. 개념
빠 른 정렬 은 분 치 된 사상 으로 데 이 터 를 정렬 합 니 다.

하나의 기준 치 선택

기준 치보다 작은 것 은 기준 치 의 왼쪽 에 놓 고 나머지 (크 거나 같 음) 는 오른쪽

에 놓는다.

그리고 왼쪽 과 오른쪽 을 계속 구분 하여 구간 길이 가 1

이 될 때 까지 한다.
2. 시간 복잡 도
빠 른 정렬 구간 을 나 눌 때 O (logN) 이 고 매번 시간 복잡 도 를 O (N) 로 정렬 해 야 합 니 다.
그래서 빠 른 배열 의 시간 복잡 도 는 O (NLogN) 이 고 이 는 기준 치 에 대해 구간 을 대충 등분 할 수 있 는 상황 이다.
데이터 가 질서 가 있 으 면 매번 나 눌 때마다 한 쪽 에 데이터 가 하나 도 없고 다른 한 쪽 은 데이터 가 있 을 수 있 습 니 다. 그러면 거품 정렬 과 같 습 니 다. 시간 복잡 도 는 O (N ^ 2) 입 니 다.
위 에서 말 한 바 와 같이:
가장 좋 은 시간 복잡 도: O (NLogN)
최 악의 시간 복잡 도: O (N ^ 2)
3. 어 울 리 는 장면
빠 른 정렬 은 데이터 가 무질서 한 상황 에 적합 합 니 다. 데이터 가 질서 가 있 을 때 시간 복잡 도 는 O (N ^ 2) 일 가능성 이 높 고 빠 른 배열 의 장점 을 나타 내지 않 습 니 다.
4. 최적화

동네 로 나 눌 때 삽입 정렬 을 사용 하고 빠 른 정렬 을 사용 하지 않 습 니 다

재 귀 실현 에 대한 빠 른 배열 은 비 재 귀 로 바 꾸 고 스 택 을 이용 하여 실현 할 수 있다

기준 치 를 선택 할 때마다 첫 번 째 또는 마지막 요 소 를 직접 선택 하지 않 습 니 다.

세 가지 방법 으로 중 법 을 취하 거나 랜 덤 으로 기준 치 를 선택 할 수 있다.
5. 실현
빠 른 배열 의 parion 함수 에 대해 세 가지 실현 방법 이 있 습 니 다.

좌우 지침 의 방법

굴착 법

전후 지침 법

이곳 은 앞 뒤 지침 의 방법 을 채택 하여 실현 한다

//     
int Partion(int array[], int left, int right)
{
    int cur = left;
    int prev = cur - 1;
    while (cur < right)
    {
        if (array[cur] <= array[right] && ++prev != cur)
        {
            std::swap(array[cur], array[prev]);
        }
        cur++;
    }
    std::swap(array[++prev], array[right]);
​
    return prev;
}
​
void QuickSort(int array[], int left, int right)
{
    if (array == nullptr)
    {
        return;
    }
​
    if (left < right)
    {
        int index = Partion(array, left, right);
        QuickSort(array, left, index - 1);
        QuickSort(array, index + 1, right);
    }
}

기타 실현 방법 및 최적화 코드:https://github.com/YKitty/LinuxDir/blob/master/DS/Sort/Sort.c
2. 2 번 고속 열차
1. 나타 난 원인
빠 른 배열 에 있어 데이터 요소 가 너무 많 고 요소 의 크기 가 매우 가깝다 면 이때 좌우 로 나 눌 때 한 쪽 은 모두 데이터 이 고 다른 한 쪽 은 데이터 가 없 으 면 효율 이 떨 어 지고 시간 복잡 도 는 O (N ^ 2) 로 변 한다.
예 를 들 어 템 플 릿 으로 정렬 과 빠 른 정렬 시간 을 테스트 하고 1000000 개의 배열 을 설정 합 니 다. 배열 요 소 는 0 - 10 사이 에 무 작위 로 값 을 추출 합 니 다. 그러면 병합 을 사용 하려 면 0.290727 s 가 필요 하고 빠 른 배열 은 171.151 s 가 필요 합 니 다. 맞습니다. 잘못 보지 않 았 습 니 다.빠 른 정렬 이 가장 좋 을 때 는 o (nlgn) 이 고 이 때 는 o (n ^ 2) 의 단계 로 퇴화 되 었 습 니 다.왜 이래?
위 에서 내 가 쓴 빠 른 배열 에 대해 기준 치 보다 작은 데 이 터 를 모두 왼쪽 에 놓 고 큰 것 을 오른쪽 에 놓 으 면 문제 가 생 길 수 있다.조건 이 같 든 작 든 배열 에서 중복 요소 가 매우 많 을 때 기준 치 와 같은 요소 가 너무 많 으 면 배열 은 극도로 불 균형 한 두 부분 으로 나 뉜 다. 기준 치 와 같은 부분 은 항상 배열 의 한 쪽 에 집중 되 기 때문이다.
이때 2 번 빠 른 배열 을 사용 하면 최적화 되 어 효율 이 떨 어 지 는 것 을 막 을 수 있다.
2 번 빠 른 속도 로 해결 하 는 문제:
기준 치 와 같은 요 소 를 모두 배열 의 한쪽 에 집중 시 키 지 않 습 니 다.
2. 사상

우 리 는 기준 치보다 작은 원 소 를 모두 수조 의 왼쪽 에 놓 고 기준 치보다 큰 원 소 는 수조 의 오른쪽 에 놓는다

왼쪽 에 색인 left 가 있 고 오른쪽 에 색인 right

가 있 습 니 다.

left 가 기준 치보다 작 을 때 뒤로 + +, 기준 치보다 큰 left 를 만 날 때 까지;right 가 기준 치 보다 클 때 앞으로 -, 기준 치 보다 작은 right

를 만 날 때 까지

이때 left 와 right 의 데이터 요 소 를 교환 한 다음 left +, right -

왼쪽 = = right 정지

이때 기준 치 와 left 위치의 요 소 를 교환 하고 기준 치 를 되 돌려 주면 됩 니 다

이런 사상 은 중복 되 는 데이터 요소 가 많 더 라 도 이 를 거의 똑 같이 나 눌 수 있 고 한 쪽 의 데이터 양 이 많 지 않 으 며 다른 한 쪽 은 데이터 가 없다.
3. 어 울 리 는 장면
배열 에서 중복 되 는 요소 가 너무 많 을 때 빠 른 배열 을 사용 할 수 없고 2 번 빠 른 배열 을 사용 하면 된다.
4. 실현
이 루어 질 때 는 파 티 온 함수 만 바 꾸 면 됩 니 다.

int Partion_Two(int array[], int left, int right)
{
    int l = left;
    int r = right - 1;
    while (1)
    {
        while (l <= r && array[l] < array[right])
        {
            l++;
        }
        while (l <= r && array[r] > array[right])
        {
            r--;
        }
        if (l > r)
        {
            break;
        }
        std::swap(array[r], array[l]);
    }
    std::swap(array[l], array[right]);
​
    return r;
}

주의: 왼쪽 에서 작 지 않 은 것 을 찾 고 오른쪽 에서 크 지 않 은 것 을 찾 은 다음 에 판단 교환 을 합 니 다.
3. 3 번 고속도로
1. 생각
배열 을 세 부분 으로 나 누 어 기준 치 보다 적 고 기준 치 와 같은 기준 치 의
다음 세 개의 아래 표 시 를 기록 합 니 다:
lt: 기준 치 보다 작은 마지막 아래 표
gt: 기준 치 보다 큰 첫 번 째 아래 표
index: 옮 겨 다 니 는 아래 표 시 를 표시 합 니 다.
index 기준 치보다 작 음: 교환 index 와 l + 1, l + +
index 기준 치 이상: 교환 index 와 lt - 1, gt --
index 는 기준 값 과 같 습 니 다: index +
종료 조건: index = lt
마지막 교환 기준 치:
swap(arr[lt], arr[right])
계속 진행 되 는 구간:
[left,lt-1]
[gt, right]
 
2. 실현

void QuickSort_Three(int array[], int left, int right)
{
	if (array == nullptr)
	{
		return;
	}

	if (right <= left)
	{
		return;
	}

	int lt = left - 1;
	int gt = right;
	int index = left;
	int key = array[right];
	while (index < gt)
	{
		if (array[index] < key)
		{
			std::swap(array[index], array[lt + 1]);
			lt++;
			index++;
		}
		else if (array[index] > key)
		{
			std::swap(array[index], array[gt - 1]);
			gt--;
		}
		else
		{
			index++;
		}
	}
	std::swap(array[index], array[right]);
	QuickSort_Three(array, left, lt );
	QuickSort_Three(array, gt, right);
}