[정렬 알고리즘] 퀵 정렬

🏆 목차.

1. 퀵 정렬이란?
2. 퀵 정렬 코드
3. 결론

 

🛒 퀵 정렬이란?

 

퀵 정렬은 평균적으로 다른 정렬 알고리즘보다 빠른 "분할 정복 알고리즘"으로

평균이나 최선의 경우 O(n * log n)의 성능을 가지고 있으며 최악의 경우 O(n^2) 시간복잡도를 가지고 있습니다.

 

퀵 정렬은 하나의 원소를 피벗(Pivot)으로 선택하고, 피벗을 기준으로 배열을 두개의 배열로 분할합니다.

피벗보다 작은 원소들은 왼쪽 배열에, 큰 원소들은 오른쪽 배열에 위치시킵니다.

 

배열에 저장된 값을 arr[10] = {4, 5, 3, 7, 8, 1, 9, 2, 10, 6};

으로 가정하고 설명하겠습니다.

 

처음에 피벗을 설정할때 배열의 가장 왼쪽에 있는 원소나 가장 끝에 있는 원소로 설정하는데 왼쪽원소로 설정하겠습니다.

 

 

이제 피벗을 제외하고 배열의 첫번째 원소에서 왼쪽으로 이동을 합니다.

마찬가지로 배열의 마지막 원소에서 오른쪽으로 이동합니다.

 

이때 각자 값을 선택하게되는데 왼쪽으로 이동할 때 피벗보다 큰 값을 선택해야 하며,

오른쪽으로 이동할 때 피벗보다 작은 값을 선택해야 합니다.

 

위 그림에서 왼쪽 진행방향은 첫 번째 원소인 5가 피벗보다 크니 선택이 되었습니다.

오른쪽 진행방향은 피벗보다 작은 2가 선택되었습니다.

 

다음 두 원소를 교체해 줍니다.

 

 

다시 반복을 해서 7과 1이 교체가 됩니다.

 

이런 식으로 반복을 하면 서로 교차하는 부분이 발생합니다.

4보다 큰 수는 8이고 반대에서 왼쪽방향으로 진행 중 4보다 작은 수는 1인데 8을 지나쳐버립니다.

이때 왼쪽 숫자와 피벗의 위치를 교체해 줍니다.

 

 

이제 4를 기준으로 왼쪽과 오른쪽으로 분할이 되고, 앞서했던 과정을 다시 반복을 합니다.

왼쪽 그룹의 피벗은 1이 되고 오른쪽 그룹의 피벗은 8이 되는 것입니다.

 

🎨 퀵 정렬 코드

 

#include<iostream>

using namespace std;

int arr[10] = {4, 5, 1, 3, 2, 6, 9, 10 ,8, 7};
int num = 10;


void QuickSort(int *arr, int start,int end ){
	if(start >= end) //원소가 1개 남았다면 -> 시작점과 끝점이 같다면 종료
	{
		return; 
	}
	int key = start; //피벗
	int i = start+1; //시작점
	int j = end; //끝점
	int temp;
	while(i<= j) //두 점이 교차하기전까지 반복
	{
		while(arr[i]<= arr[key]){  
        //시작점의 값이 피벗의 값보다 작다면 큰 값을 찾을때까지 i증가
			i++;
		}
		while(arr[j]>= arr[key] && j>start){
        //끝점의 값이 피벗의 값보다 크다면 작은 값을 찾을때까지 j감소
        //j가 start보다 커야함
			j--;
		}
        //만약 서로 교차한다면 왼쪽에 있는 값을 피벗으로 설정 
		if(i>j){
			temp = arr[j];
			arr[j] = arr[key];
			arr[key] = temp;
		} 
		else{
        //교차하지않는다면 서로 값 교체
		 	temp = arr[j];
		 	arr[j] = arr[i];
		 	arr[i] = temp;
		 }
	}
	QuickSort(arr,start, j-1);
	QuickSort(arr,j+1,end);
	
} 
int main(){
	
	QuickSort(arr,0,num-1);
	for(int i = 0 ; i< num; i++)
	{
		cout<<arr[i]<<" ";
	}
}

 

🎯 결론

 

퀵 정렬은 평균적으로 앞서 배운 정렬과 다른 점은 일단 재귀적으로 정렬을 반복한다는 점입니다.

그리고 피벗보다 작은 그룹은 왼쪽으로 큰 그룹은 오른쪽으로 분할하여 정렬을 진행합니다.

 

시간복잡도는 최악의 경우 O(n^2)이지만 평균적으로 O(n*logn)의 성능을 보입니다.