퀵 정렬(Quick Sort)

이재원·2일 전

알고리즘 퀵정렬

알고리즘

목록 보기

14/15

퀵 정렬(Quick Sort)

퀵 정렬은 분할 정복 알고리즘의 일종으로, 리스트를 정렬하는 효율적인 방법 중 하나이다. 작동 원리는 다음과 같다.

작동 원리

1. 피벗 선택(Pivot)

정렬한 리스트에서 하나의 기준 값(피벗)을 선택한다. 피벗은 리스트의 임의의 값일 수 있으며, 일반적으로 처음, 중간, 마지막 값 중 하나로 설정한다.

2. 분할(partitioning)

피벗을 기준으로 리스트를 두 개의 부분 리스트로 나눈다.

피벗보다 작은 값들로 이루어진 부분 리스트
피벗보다 큰 값들로 이루어진 부분 리스트

3. 재귀적으로 정렬(Recursive Sorting)

분할된 두 개의 부분 리스트에 대해 퀵 정렬을 재귀적으로 적용한다. 이 과정은 리스트가 더 이상 나눌 수 없을 때(부분 리스트의 크기가 1 이하일 때) 종료된다.

4. 합치기(Combine)

정렬된 부분 리스트를 결합하여 최종 정렬된 리스트를 만든다.

시간 복잡도와 공간 복잡도

시간 복잡도

평균: $O(nlogn)$
최악: 이미 정렬된 경우 $O(n^2)$

공간 복잡도

$O(logn)$ (재귀 호출 스택 사용)

장점과 단점

장점

정렬 속도가 빠르고 대부분의 경우 효율적이다.
추가 메모리 공간을 적게 사용한다.

단점

최악의 경우 시간이 많이 걸릴 수 있다.
피벗 선택이 중요한 성능 요인이다.

전체 코드

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

#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

int list[MAX_SIZE];
int n;

int partition(int list[], int left, int right) {
	int pivot, temp;
	int low, high;

	low = left;
	high = right + 1;
	pivot = list[left];
	do {
		do
			// 왼쪽 처음은 피봇이기 때문에 그 다음 값으로 변경
			low++;
		// 피봇보다 큰 데이터가 있을 때까지 반복
		while (list[low] < pivot);
		do
			// low와 맞춰주기 위해 1 증가한 상태에서 다시 1 갑소
			high--;
		// 피봇보다 작은 데이터가 있을 때까지 반복
		while (list[high] > pivot);
		if (low < high)
			SWAP(list[low], list[high], temp);
		// low와 high이 겹칠 때 반복문 탈출
		// low의 증가와 high의 감소가 함께 움직이므로 둘은 교차하게 됨
	} while (low < high);

	// 교차한 상태에서 high의 위치가 피봇의 위치임
	// 만약 피봇보다 작거나 큰 값이 없다면 
	// 작은 경우에는 오른쪽 서브 파일만 생기고, 큰 경우 왼쪽 서브 파일만 생김
	SWAP(list[left], list[high], temp);
	return high;
}

void quick_sort(int list[], int left, int right) {
	if (left < right) {
		int q = partition(list, left, right);
		quick_sort(list, left, q - 1);
		quick_sort(list, q + 1, right);
	}
}

int main(void) {
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i < n; i++)      	// 난수 생성 및 출력 
		list[i] = rand() % 100;

	quick_sort(list, 0, n - 1); // 퀵정렬 호출 
	for (i = 0; i < n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}