퀵 정렬(Quick Sort)

 퀵 정렬(Quick Sort)은 효율적이고 널리 사용되는 정렬 알고리즘입니다. 주요 특징들입니다.

• 분할 정복 방식: 배열을 정렬하기 위해 배열을 작은 부분 배열로 분할하고 각 부분 배열을 재귀적으로 정렬합니다.
• 피벗 선택: 배열에서 하나의 요소를 피벗(pivot)으로 선택
• 분할: 피벗을 기준으로 작은 값들을 왼쪽, 큰 값들은 오른쪽으로 분할
• 재귀적 정렬: 분할된 두 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다.

퀵 정렬 구조 예시

 pivot은 기존 배열에서 자주 사용한 head와 전혀 다른 형태입니다. 배열에서 head와 tail은 배열의 양 끝 고정이지만 pivot은 정렬 과정 중 해당 요소를 주기적으로 바꿔가며 오름차순을 만들어냅니다. 가장 자주 사용하는 정렬로 이름대로 빠르다는 장점이 있습니다.

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

#define MAX_LEN 10

void Init(int* _pArr, int _len);
void QuickSort(int* _pArr, int _len, int _startIdx, int _endIdx);
int Partition(int* _pArr, int _len, int _startIdx, int _endIdx);
void PrintAll(int* _pArr, int _len);
void PrintWithPivot(int* _pArr, int _startIdx, int _endIdx, int _pivotIdx);

int main()
{
	srand(time(NULL));		//현재 시간 기준 난수 함수

	int arr[MAX_LEN] = { 0 };	//arr[10]
	Init(arr, MAX_LEN);		//Init 함수 호출
	PrintAll(arr, MAX_LEN);		//호출문

	printf("\n");
	QuickSort(arr, MAX_LEN, 0, MAX_LEN - 1);	//퀵 정렬 함수 호출
	printf("\n");

	PrintAll(arr, MAX_LEN);		//호출문
}


void Init(int* _pArr, int _len)
{
	if (_pArr == NULL || _len < 1) return;	// 예외처리

	for (int i = 0; i < _len; ++i)
		_pArr[i] = rand() % 100;	//랜덤값 가진 배열 생성용 반복문
}

void QuickSort(int* _pArr, int _len, int _startIdx, int _endIdx)
{
	if (_pArr == NULL || _len < 1) return;	//예외처리

	if (_startIdx >= _endIdx) return;	//예외처리

	int pivotIdx = Partition(_pArr, _len, _startIdx, _endIdx);	//pivot 생성 변수

	QuickSort(_pArr, _len, _startIdx, pivotIdx - 1);//QuickSort 재귀 함수
	QuickSort(_pArr, _len, pivotIdx + 1, _endIdx);	//위가 끝나고 추가 재귀 함수
}

int Partition(int* _pArr, int _len, int _startIdx, int _endIdx)	//pivot 생성 함수
{
	if (_pArr == NULL || _len < 1) return -1;	//예외처리

	int pivotIdx = _startIdx;	//피봇을 시작인덱스로 설정
	int leftIdx = _startIdx + 1;//왼쪽 인덱스는 시작 인덱스 + 1
	int rightIdx = _endIdx;		//오른쪽 인덱스는 마지막 인덱스
	int leftEnd = leftIdx;	
	int rightEnd = rightIdx;

	while (leftIdx < rightIdx)
	{
		// 1. 왼쪽에서 오른쪽으로 이동하면서
		//    피봇 보다 큰 숫자 찾기
		while (leftIdx < rightEnd && _pArr[leftIdx] <= _pArr[pivotIdx])
			++leftIdx;

		// 2. 오른쪽에서 왼쪽으로 이동하면서
		//    피봇 보다 작은 숫자 찾기
		while (rightIdx > leftEnd && _pArr[rightIdx] >= _pArr[pivotIdx])
			--rightIdx;

		// 3. 왼쪽, 오른쪽 인덱스가 서로 교차했다면
		//    탐색이 끝난 것이기 때문에 [종료]
		if (leftIdx >= rightIdx) break;

		// 4. 두 인덱스가 교차하기 전에
		//    값을 찾았다면 교환
		int tmp = _pArr[leftIdx];
		_pArr[leftIdx] = _pArr[rightIdx];
		_pArr[rightIdx] = tmp;
	}

	// 5. 피봇값이 오른쪽값 보다 크면 교환
	//    파티션 피봇 반환
	if (_pArr[pivotIdx] > _pArr[rightIdx])
	{
		int tmp = _pArr[pivotIdx];
		_pArr[pivotIdx] = _pArr[rightIdx];
		_pArr[rightIdx] = tmp;

		PrintWithPivot(_pArr, _startIdx, _endIdx, rightIdx);

		return rightIdx;
	}

	PrintWithPivot(_pArr, _startIdx, _endIdx, pivotIdx);

	// 6. 피봇값 반환
	return pivotIdx;
}

void PrintAll(int* _pArr, int _len)
{
	if (_pArr == NULL || _len < 1) return;

	for (int i = 0; i < _len; ++i)
		printf("[%d] - ", _pArr[i]);
	printf("(%d)\n", _len);
}

void PrintWithPivot(int* _pArr, int _startIdx, int _endIdx, int _pivotIdx)
{
	if (_pArr == NULL || _startIdx < 0 || _endIdx < 0 || _startIdx > _endIdx || _pivotIdx < 0)
		return;

	for (int i = _startIdx; i <= _endIdx; ++i) 
	{
		if (_pivotIdx == i)
			printf("<%d> - ", _pArr[i]);
		else
			printf(" %d  - ", _pArr[i]);
	}
	printf("(%d)\n", _endIdx - _startIdx + 1);
}

 

<출력값>

[48] - [81] - [7] - [52] - [15] - [60] - [60] - [79] - [95] - [53] - (10)
srand(time(NULL));
int arr[MAX_LEN] = { 0 };
Init(arr, MAX_LEN);
PrintAll(arr, MAX_LEN);
 7  -  15  - <48> -  52  -  81  -  60  -  60  -  79  -  95  -  53  - (10)
<7> -  15  - (2)
<52> -  81  -  60  -  60  -  79  -  95  -  53  - (7)
 53  -  60  -  60  -  79  - <81> -  95  - (6)
<53> -  60  -  60  -  79  - (4)
<60> -  60  -  79  - (3)
<60> -  79  - (2)
QuickSort(arr, MAX_LEN, 0, MAX_LEN - 1);
[7] - [15] - [48] - [52] - [53] - [60] - [60] - [79] - [81] - [95] - (10)

PrintAll(arr, MAX_LEN);

 

끝