퀵 정렬(Quick sort)

박경린·2021년 4월 17일

정렬

목록 보기

4/9

1. 퀵 정렬이란?

정렬 알고리즘 중 하나로 비교만으로 정렬을 수행하는 알고리즘입니다.
오름차순을 기준으로 정렬한다고 했을 시에
1. 리스트 중 하나를 pivot으로 지정하고 그 pivot을 기준으로 작은 수 는 왼쪽으로, 큰 수는 오른쪽으로 옮깁니다.
2. 이를 재귀적으로 반복합니다.
위 과정으로 만들어지는 알고리즘입니다.

2. 사용 예시

위 배열을 오름차순으로 정렬해 보도록 하겠습니다.

가장 오른쪽 원소를 pivot으로, pivot을 제외한 리스트의 가장 왼쪽을 i로, 가장 오른쪽을 j로 지정합니다.

i와 j를 비교해서 i가 pivot보다 크고, j가 pivot보다 작을 경우 i와 j를 바꿉니다.

비교를 할 때마다 i를 오른쪽으로 j를 왼쪽으로 이동합니다.
이 다음에도 같은 과정을 거칩니다.

i가 pivot보다 작고, j가 pivot보다 크면 넘어갑니다.

j가 pivot보다 크고 i가 pivot보다 클 경우 j를 왼쪽으로 옮김니다.

i와 j가 같은 위치에 있을 경우 pivot과 위치를 변경합니다.
pivot을 기준으로 왼쪽 배열과 오른쪽 배열로 나누어 줍니다.

위 과정을 나누어진 배열에 재귀적으로 진행해 줍니다.

3. 코드

코드상의 편의를 위해 보통 pivot은 리스트의 가운데로 지정합니다.

void quickSort(int[] arr, int left, int right){
	
    if (left >= right) return;
    int i = left;
    int j = right;
    int pivot = arr[(i + j) / 2];
    
    while(i < j){
    	
        while(i < j && arr[j] > pivot) j--;
        while(i < j && arr[i] < pivot) i++;
        
        swap(arr[i], arr[j]);
    }
       
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}