열혈 자료구조 - 10.2 복잡하지만 효율적인 알고리즘(2)

퀵 정렬

- 1단계(초기화)

- 퀵정렬을 위해서는 left / right / low / high / pivot이 필요

    -> left, right : 데이터의 시작과 끝

    -> pivot : 중심점, 기준

    -> low, high : pivot을 제외한 다음 위치

- 2단계(low와 high의 이동)

    -> low : 피벗보다 정렬의 우선순위가 낮은 데이터를 만날 때까지 이동

    -> high : 피벗보다 정렬의 우선순위가 높은 데이터를 만날 때까지 이동

    -> low와 high 이동은 별개

- 3단계(low와 high의 교환)

    -> 2단계의 low와 high위치의 데이터를 교환

    -> low와 high가 역전할 때 까지 계속 이동

- 4단계(pivot의 이동)

    -> 3단계를 실행함으로써 high 다음의 데이터들은 pivot보다 우선순위가 낮음을 확인했음

        * high가 내려오면서 우선순위가 높은것들은 자리를 바꿨음

    -> high의 데이터와 pivot의 데이터를 교환

    -> 그럼으로써 pivot의 데이터는 자리를 잡고 pivot의 데이터를 기준으로 좌우측은 섞일 필요가 없어짐

    -> 이제 pivot의 데이터(high 위치)를 기준으로 좌우측으로 나누어서 위의 단계를 반복

        * left가 right보다 커질때 까지 반복 => 더이상 쪼갤 영역이 없음

- 1단계 ~ 4단계를 구현한 함수

int Partition(int arr[], int left, int right)
{
	int pivot = arr[left];    
	int low = left+1;
	int high = right;     // 1단계

	while(low <= high)    
	{	
		while(pivot >= arr[low] && low <= right) {
            	    low++;
		} // low 이동

		while(pivot <= arr[high] && high >= (left+1)) {
		    high--;
		} // high 이동

		if(low <= high)    // 교차되지 않은 상태라면 Swap 실행
			Swap(arr, low, high);    // 3단계 : low와 high가 가리키는 대상 교환
	} // 2단계, 3단계 : 교차되지 않을 때까지 반복

	Swap(arr, left, high);    // 4단계 : 피벗과 high가 가리키는 대상 교환
        
	return high;    // 옮겨진 피벗의 위치 정보 반환(왼쪽 오른쪽을 구분짓는 중간의 인덱스 값)
}

void QuickSort(int arr[], int left, int right)
{
	if(left <= right)
	{
		int mid = Partition(arr, left, right);    // 영역을 나누고 중간 값을 받음
		QuickSort(arr, left, mid-1);    // 왼쪽 영역을 정렬
		QuickSort(arr, mid+1, right);   // 오른쪽 영역을 정렬
	}
}

- 피벗 선택에 대한 논의

    -> 위의 경우 선정한 pivot의 데이터가 정렬하고자 하는 데이터들의 중간값 정도이기 때문에 좌우측 영역이 골고루 나눠져 효율적인 연산을 했음

    -> 만약 아래와 같이 pivot의 데이터가 그렇지 않은 경우에는 효율적이지 못함

    -> 단계별로 필요한 비교 연산의 횟수가 늘어남

    -> 결론적으로 피벗은 가급적 중간에 해당하는 값을 선택하는 것이 퀵정렬의 효과를 극대화할 수 있음

    -> 맨 앞, 뒤, 중간 값을 비교해서 2번째 값을 피벗으로 선택하거나, 앞에 데이터 3개를 비교해서 2번째 값을 피벗으로 선택하는 방법 등

- 퀵 정렬의 시간 복잡도

    -> 최선의 경우 : 피벗이 제대로 선택된 경우

        * 데이터가 8개일 경우 3번에 거쳐서 나눠지면서 정렬이 진행

        * low와 high가 이동될때마다 pivot과 비교

    -> 최악의 경우 : 피벗이 제대로 선택되지 못한 경우