[알고리즘] ch 8. 정렬(2) - 퀵 정렬

8.4 퀵 정렬 

 

- 분할 정복(Divide and Conquer)에 바탕을 둔 알고리즘

 

1) 기준 요소 선정 및 정렬 대상 분류

 - 자료구조에서 기준이 될 요소를 임의로 선정하고 기준 요소(Pivot)의 값보다 작은 값을 가진 요소는 기준 요소의 왼쪽으로, 큰 값을 가진 요소는 오른쪽으로 옮김

 

2) 정렬대상 분할

 

- 기준 요소 왼쪽에는 기준 요소보다 작은 요소의 그룹, 오른쪽에는 큰 요소의 그룹이 생김

여기에서 왼쪽 그룹과 오른쪽 그룹을 분할하여 각 그룹에 대해 1)의 과정 수행

 

3) 반복

- 그룹의 크기가 1 이하여서 더 이상 분할할 수 없을 때까지 1), 2)의 과정을 반복하면 정렬이 완료 

 

ex)

- 5를 기준으로 5보다 작은 요소를 왼쪽에, 큰 요소들은 오른쪽에 모음 

- 5보다 작은 1,4,3,2는 왼쪽 그룹에, 5보다 큰 6,8,7,9는 오른쪽 그룹에 모이게 됨 

- 첫 번째 요소인 1을 기준으로 선정 

- 1,4,3,2 중 1보다 작은 요소는 없고 1보다 큰 요소는 모두 1의 오른쪽에 와 있으므로 이미 분할된 상태 

- 4,3,2 중 첫 번째 요소인 4를 기준으로 선정하여 분할

- 분할 결과 4의 왼쪽 그룹에 3,2가 옮겨져 옴 

- 3,2를 분할 

- 3,2 중 첫 번째에 위치한 3을 서정하여 분할 수행 

 

- 2는 3보다 작으므로 3의 왼쪽에 와야 함 

- 3의 왼쪽 그룹은 크기가 1, 오른쪽 그룹은 크기가 0이므로 최초 분할에서 생긴 왼쪽 그룹이 정렬됨 

- 오른쪽 그룹 분할 시작

- 6을 기준 요소로 선정했는데 6보다 작은 요소가 없음

 -> 6의 오른쪽에 있는 그룹을 분할

 

- 8,7,9 중 첫 번째 요소인 8을 기준으로 선정하고 분할 수행 

 

- 8의 왼쪽 그룹도 7 하나뿐이고 오른쪽 그룹도 9 하나밖에 안 남았으므로 추가적인 분할이 불가능한 상태 

 

8.4.1 퀵 정렬 사용 전 해결해야 하는 2가지 문제 

 

1) 배열을 사용할 경우 퀵 정렬의 분할 과정을 어떻게 효율적으로 처리할 것인가?

 

- 퀵 정렬 알고리즘 분할 과정에서 기준 요소보다 작은 요소는 기준 요소의 왼쪽으로, 큰 요소는 오른쪽으로 이동해야 함

- 배열에서 요소 사이에 새로운 요소를 삽입하려면 다른 요소를 이동시켜야 하는데 이때 오버헤드가 크다는 문제 

 

- 요소의 이동을 최소화하기 위해 '수색 섬멸'작전 

- 정찰병 2명이 1조로 움직이는데, 한 명은 왼쪽부터 오른쪽 방향으로 배열을 순회하면서 기준보다 큰 요소를 찾고, 다른 한명은 오른쪽부터 왼쪽 방향으로 순회하면서 기준보다 작은 요소를 찾음 

- 이 두 정찰병이 찾아낸 두 요소를 맞교환함 

- 정찰병들은 서로 접선할 때까지 교환해야 할 요소를 찾아내고 교환하는 과정을 이어 나감 

- 이 작전은 두 정찰병이 접선하여 기준 요소를 왼쪽 그룹의 마지막 요소와 맞교환하는 것으로 끝남 

 

 

2) 반복되는 분할 과정을 어떻게 처리할 것인가?

 

- 재귀호출 

 

 

8.4.2 퀵 정렬 예제 프로그램

 

 

QuickSort() 함수 

 

- DataSet 배열과, DataSet 내의 정렬 대상 범위 값 Left, Right를 매개변수로 받음

- Left와 Right는 수색섬멸을 수행하는 두 정찰병의 위치를 나타냄

- Left가 Right 보다 크거나 같으면 둘이 만났다는 뜻이므로 실행 종료 

- Left가 Right보다 작으면 Partition() 함수를 실행한 후 QuickSort()를 재귀 호출 

 

Partition() 함수 

 

- 정렬 대상의 첫 번째 요소를 기준 요소(Pivot)으로 지정하고, while 루프를 통해 분할을 수행

- 첫 번째 While 루프는 DataSet의 왼쪽에서 출발해서 Pivot보다 큰 요소를 찾을 떄까지 탐색을 계속하며 Left를 1씩 증가시킴

- Pivot보다 큰 요소를 찾으면 Left에 그 요소가 위치한 인덱스를 저장하고 종료

- 두 번째 While 루프는 DataSet의 오른쪽에서 출발해서 Pivot보다 작은 요소를 찾아 그 요소의 위치를 Right에 저장 

- 그런 다음 Left와 Right를 비교한 후 Left가 Right보다 작으면 두 정찰병이 찾은 요소들을 교환 

 

- 분할 작업이 끝나면  기존 요소와 분할에 의해 왼쪽 자료구조의 오른쪽 끝에 새로 생긴 요소를 교환 

- 마지막에 새 기준이 될 요소의 위치를 반환

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void Swap(int* A, int* B)
{
    int Temp = *A;
    *A = *B;
    *B = Temp;
}

int Partition(int DataSet[], int Left, int Right)
{
    int First = Left;
    int Pivot = DataSet[First]; 

    ++Left;

    while (Left <= Right)
    {
        while (DataSet[Left] <= Pivot && Left < Right)
            ++Left;

        while (DataSet[Right] >= Pivot && Left <= Right)
            --Right;

        if (Left < Right)
            Swap(&DataSet[Left], &DataSet[Right]);
        else
            break;
    }

    Swap(&DataSet[First], &DataSet[Right]);

    return Right;
}

void QuickSort(int DataSet[], int Left, int Right)
{
    if (Left < Right)
    {
        int Index = Partition(DataSet, Left, Right);

        QuickSort(DataSet, Left, Index - 1);
        QuickSort(DataSet, Index + 1, Right);
    }
}



int main(void)
{
	int DataSet[] = { 6,4,2,3,1,5 };
	int Length = sizeof DataSet / sizeof DataSet[0];
	int i = 0;

	printf("정렬 전\n");

	for (i = 0; i < Length; i++)
	{
		printf("%2d", DataSet[i]);
	}
	printf("\n");

    QuickSort(DataSet, 0, Length - 1);

	printf("정렬 후\n");

	//정렬된 자료 구조 출력
	for (i = 0; i < Length; i++)
	{
		printf("%2d", DataSet[i]);
	}

	printf("\n");

	return 0;
}