[알고리즘] 퀵정렬 (Quick Sort) - JAVA / 자바

퀵 정렬(Quick Sort)

 - 정렬할 전체 원소에 대해 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬

    ㄴ 왼쪽 부분 집합에는 기준 값보다 작은 원소들 / 오른쪽 부분 집합에는 기준 값보다 큰 원소들

    ㄴ 기준 값 : 피봇(pivot) : 일반적으로 전체 원소 중 가운데 위치한 원소 선택

 - 퀵 정렬은 다음의 두 가지 기본 작업을 반복 수행하여 완성

    ㄴ 분할(divide) : 정렬할 자료들을 기준값을 중심으로 2개의 부분 집합으로 분할

    ㄴ 정복(conquer) : 부분 집합의 원소들 중 기준값보다 작은 원소들은 왼쪽 부분 집합으로, 기준값보다 큰 원소들은 오른쪽 부분 집합으로 정렬, 부분 집합의 크기가 1 이하로 충분치 않으면 순환 호출을 이용하여 재분할

---

 - 수행 방법

• 부분 집합으로 분할하기 위해서 L과 R을 사용
  ① 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 Pivot보다 크거나 같은 원소를 찾아 L로 표시
  ② 오른쪽 끝에서 왼쪽으로 움직이면서 Pivot보다 작은 원소를 찾아 R로 표시
  ③ L이 가리키는 원소와 R이 가리키는 원소를 서로 교환한다.
• L와 R이 만나게 되면 Pivot과 R의 원소를 서로 교환하고, 교환한 위치를 Pivot의 위치로 확정한다.
• Pivot의 확정된 위치를 기준으로 만들어진 왼쪽 부분 집합과 오른쪽 부분 집합에 대해서 퀵 정렬을 순환적으로 반복 수행하는데 부분 집합의 크기가 1이하가 되면 퀵 정렬을 종료한다.

---

 - 수행 과정

정렬되지 않은 배열 list = {69, 10, 30, 2, 16, 8, 61, 22}

 

① 원소의 개수가 8개이므로 네 번째 자리에 있는 원소 2를 첫 번째 Pivot으로 선택하고 퀵 정렬 시작.

69	10	30	2	16	8	31	22
L			Pivot				R
L / R			Pivot
2	10	30	69	16	8	31	22
Pivot < 오른쪽 부분 집합

② Pivot 2의 왼쪽 부분 집합은 공집합이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합에 대해서 퀵 정렬 수행.

2	10	30	69	16	8	31	22
		L		Pivot	R
2	10	8	69	16	30	31	22
			L / R	Pivot
2	10	8	16	69	30	31	22
왼쪽 부분 집합 < Pivot < 오른쪽 부분 집합

③ Pivot 16의 왼쪽 부분 집합에서 원소 10을 Pivot으로 선택하여 퀵 정렬 수행.

2	10	8	16	69	30	31	22
	L / Pivot	R
2	8	10	16	69	30	31	22
왼쪽 부분 집합 < Pivot

④ Pivot 10의 왼쪽 부분 집합의 원소가 한 개이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합은 공집합이므로 역시 퀵 정렬을 수행하지 않는다.

2	8	10	16	69	30	31	22
				L	Pivot		R
2	8	10	16	22	30	31	69
					L / Pivot / R
2	8	10	16	22	30	31	69
왼쪽 부분 집합 < Pivot < 오른쪽 부분 집합

⑤ Pivot 30의 왼쪽 부분 집합의 원소가 한 개 이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합에 대해서 퀵 정렬 수행.

2	8	10	16	22	30	31	69
						L / Pivot	R
						L / Pivot / R
2	8	10	16	22	30	31	69
Pivot < 오른쪽 부분 집합

---

 - 알고리즘

quickSort(list[], begin, end)
    if (m < n) then {
        p ← partition(list, begin, end);
        quickSort(list[], begin, p-1);
        quickSort(list[], p+1, end);
    }
end quickSort()

partiton(list[], begin, end)
    pivot ← (begin + end) / 2;
    L ← begin;
    R ← end;
    while (L < R) do {
        while (list[L] < list[pivot] and L < R) do L++;
        while (list[R] ≥ list[pivot] and L < R) do R--;
        if (L < R) then { // L의 원소와 R의 원소 교환
            temp ← list[L];
            list[L] ← list[R];
        	list[R] ← temp;
        }
    }
    temp ← list[pivot]; // R의 원소와 피봇 원소 교환
    list[pivot] ← list[R];
    list[R] ← temp;
    return L;
end partition()

 - 메모리 사용 공간 : n개의 원소에 대하여 n개의 메모리 사용

 - 연산 시간

    ㄴ 최선의 경우 : 피봇에 의해서 원소들이 왼쪽 부분 집합과 오른쪽 부분 집합으로 정확히 n/2개씩 이등분이 되는 경우가 반복되어 수행 단계 수가 최소가 되는 경우

    ㄴ 최악의 경우 : 피봇에 의해 원소들을 분할하였을 때 1개와 n-1개로 한쪽으로 치우쳐 분할되는 경우가 반복되어 수행 단계 수가 최대가 되는 경우

 - 평균 시간 복잡도 : O(n log2 n) : 같은 시간 복잡도를 가지는 다른 정렬 방법에 비해 자리 교환 횟수를 줄임으로써 더 빨리 실행되어 실행 시간 성능이 좋은 정렬 방법

---

< 분류 > 

정렬 장소 - 내부 정렬(Internal Sort)  >  교환 방식

[자료구조] 정렬 (Sort)