퀵 정렬(Quick sort)

퀵 정렬이란?

• 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘
• 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
• n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(nlogn)번의 비교를 수행
• 수행속도가 매우 빠르다.

설명

1. 임의의 수를 pivot(피봇)이라는 이름으로 기준을 잡는다.(pivot은 중간값이 적절)
2. pivot값을 기준으로 pivot값보다 작은 값은 pivot 앞으로 큰 값은 뒤로 가게 값들의 위치를 바꾼다.
3. 이 과정이 마무리되면 pivot은 중간에 들어가 있게 되어 있다.(중간값이 적절한 자리를 찾음)
4. pivot을 기준으로 좌우로 나누고(분할) 나눠진 리스트에 대해서 다시 1, 2, 3 과정을 반복한다(재귀).

예시

피벗은 p, 리스트 왼쪽 끝과 오른쪽 끝에서 시작한 인덱스들을 i,j라고 하자.

5 - 3 - 7 - 6 - 2 - 1 - 4
                                   p

리스트 왼쪽에 있는 i 위치의 값이 피벗 값보다 크고, 오른쪽에 있는 j 위치의 값은 피벗 값보다 작으므로 둘을 교환한다.

5 - 3 - 7 - 6 - 2 - 1 - 4
i                            j    p   -> i와 j swap!
1 - 3 - 7 - 6 - 2 - 5 - 4
i                            j    p

j 위치의 값이 피벗 값보다 작지만, i 위치의 값도 피벗값보다 작으므로 교환하지 않는다.

1 - 3 - 7 - 6 - 2 - 5 - 4
i                       j         p

i위치를 피벗 값보다 큰 값이 나올 때 까지 진행해 j 위치의 값과 교환한다.

1 - 3 - 7 - 6 - 2 - 5 - 4
            i           j         p
1 - 3 - 2 - 6 - 7 - 5 - 4
            i           j        p

i위치가 j 위치보다 커지면, i 위치의 값과 피벗 값을 교환한다.

1 - 3 - 2 - 6 - 7 - 5 - 4
                                   p
1 - 3 - 2 - 4 - 7 - 5 - 6
                  p

피벗 값 좌우의 리스트에 대해 각각 퀵 정렬을 재귀적으로 수행한다.

1 - 3 - 2  7 - 5 - 6
1 - 2 - 3  5 - 6 - 7

완성된 리스트는 다음과 같다.

1 - 2 - 3 - 4 - 5 - 6 - 7

 

pivot 선택방법

퀵 정렬에서 피벗 위치를 결정하는 방법에는 여러가지 방법이 있다. 기초적인 방법으로는 난수 분할이 사용되는데, 안정성이 떨어진다. 많은 라이브러리에서는 세 값(좌측 끝, 중앙, 우측 끝)의 중위법을 이용하여 분할한다. 이 방법을 사용하면 중앙에서 분할될 가능성이 높아 전체적으로 정렬의 성능이 좋아진다.

 

코드(Java)

public void quickSort(int[] arr, int left, int right) {
    int i, j, pivot, tmp;
    if (left < right) {
        i = left;   j = right;
        pivot = arr[(left+right)/2];
        //분할 과정
        while (i < j) {
            while (arr[j] > pivot) j--;
            // 이 부분에서 arr[j-1]에 접근해서 익셉션 발생가능함.
            while (i < j && arr[i] < pivot) i++;

            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        //정렬 과정
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

public static void quick(int left, int right, int[][] arr) {

	int pivot = left;
	int j = pivot;
	int i = left + 1;
	int temp; // swap 하기위한 변수
		if (left < right) {
		for (; i <= right; i++) {
			if (arr[i][2] < arr[pivot][2]) {
				j++;
				for (int k = 0; k < 3; k++) {
					temp = arr[j][k];
					arr[j][k] = arr[i][k];
					arr[i][k] = temp;
				}
			}
		}
		for (int k = 0; k < 3; k++) {
			temp = arr[left][k];
			arr[left][k] = arr[j][k];
			arr[j][k] = temp;
		}
		pivot = j;
		quick(left, pivot - 1, arr);
			quick(pivot + 1, right, arr);
	}
}

references

https://ko.wikipedia.org/wiki/퀵_정렬

퀵 정렬 - 위키백과, 우리 모두의 백과사전

https://kingname.tistory.com/78

[JAVA/알고리즘] Quicksort 큌정렬을 알아보자!