[알고리즘] 정렬 알고리즘: Quick Sort

 

Quick Sort

https://yujuwon.tistory.com/

분할 정복 알고리즘이라고도 하며, 특정값을 기준으로 한 배열을 두개의 부분 배열로 나누어 정렬하는 알고리즘이다.

 

pivot을 정하고, 나머지 배열의 양쪽끝에서부터 검사를 한다.

배열의 왼쪽에는 pivot보다 작은 값, 배열의 오른쪽에는 pivot보다 큰 값이 놓이도록,

잘못된 위치에 있는 원소들을 교환한다.

 

한 검사가 끝나면 적어도 pivot은 제 위치를 찾은 것이고, 나눠진 배열들에 또 퀵 정렬을 적용하고 반복하면

정렬이 완료되게 된다.

 

이 알고리즘은 while문과 재귀함수로 구현할 수 있다.

배열들을 검사하며 교환하는 while문과 나눠진 두 배열에 퀵 정렬을 적용하는 재귀함수로 이루어진다.

 

퀵 정렬은 최선의 경우와 최악의 경우에 따라 시간 복잡도가 달라지는데

정렬된 배열을 검사할 땐 비교하는 부분이 제외되서 배열을 나누는 부분만 계산하여 O(logn)이 된다.

선택한 pivot이 최대,최소일때 나눠진 한쪽 배열이 비어있기 때문에 배열을 나누는 이점이 사라져서 O(n^2)이 된다.

 

코드

#include <iostream>

using namespace std;

void quick_sort(int arr[],int start,int end)
{
	if(start>=end) //start가 end와 같거나 크다면 배열이 1보다 작거나 문제가 있는 것
    	return;
	int pivot = start;     //시작부분을 pivot으로
    int left = start+1;
    int right = end;
    while(left<=right)     //: left와 right 검사가 끝날때까지
    {
    	while(arr[left]<=arr[pivot] && left<=end)
        	left++;
        while(arr[right]>=arr[pivot] && right>=start+1)
        	right--;
        if(left<right)    //: 위의 while문들을 통해 left와 right에 교체해야할 원소가 놓여있음
        {
        	int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
        }else{           //pivot과 right의 위치를 바꿔 pivot이 중앙에 놓이도록
        	int tmp = arr[pivot];
            arr[pivot] = arr[right];
            arr[right] = tmp;
        }
    }
    //pivot값이 저장된 right_idx를 기준으로 배열을 나누어 퀵 정렬 실행
    quick_sort(arr,start,right-1); 
    quick_sort(arr,right+1,end); 
}

void arr_print(int arr[],int n)
{
	for(int i=0;i<n;i++)
    	cout<<arr[i]<<" ";
}

int main(){
	int n=5;
	int arr[n] = {8,6,2,7,1};
    quick_sort(arr,0,n-1); 
    arr_print(arr,n);
	return 0;
}