Quick Sort (퀵 정렬)

---

1. 분할 정복법

- 분할 : 배열을 다음과 같은 조건이 만족 되도록 두 부분으로 나눈다.

1. 자기 자신 보다 작은 값들

2. 자기 자신 보다 큰 값들

- 정복 : 각 부분을 순환적으로 정렬 한다.

​

 

2. 퀵 정렬

1. 정렬할 배열이 주어짐. 마지막 수를 기준(pivot)으로 삼는다.

31

8

48

73

11

3

20

29

65

15

 

2. 기준보다 작은 수는 기준의 왼쪽에 나머지는 기준의 오른쪽에 오도록 재배치 분할 한다.

8

11

3

15

31

48

20

29

65

73

 

3. 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다.

3

8

11

15

20

29

31

48

65

73

 

 

3. sudo 코드

quickSort(A[], p, r) { // A[p....r]을 정렬한다.
    if (p < r) then {
        q = partition(A, p, r); // 분할
        quickSort(A, p, q-1);   // 왼쪽 부분배열 정렬
        quickSort(A, q+1, r);   // 오른쪽 부분배열 정렬
    }
}
    
partition(A[], p, r) {
    배열 A[p....r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고
    A[r]이 자리한 위치를 return 한다;
}

 

 

4. Partition

 

 

 

 

 

 

 

5. Partition sudo 코드

if A[j] >= x
    j = j +1;
else
    i = i + 1;
    exchange A[i] and A[j];
    j = j + 1;

 

 

 

 

6. Pivot 선택 방법

1. 첫번째 값이나 마지막 값을 피봇으로 선택

- 이미 정렬된 데이터 혹은 거꾸로 정렬된 데이터가 최악의 경우

- 현실의 데이터는 랜덤하지 않으므로 (거꾸로) 정렬된 데이터가 입력으로 들어올 가능성은 매우 높음

- 따라서 좋은 방법이라고 할 수 없음

 

2. Median of three

- 첫번쨰 값과 마지막 값, 그리고 가운데 값 중에서 중간값(median)을 피봇으로 선택

- 최악의 경우 시간복잡도가 달라지지는 않음

 

3. Randomized QuickSort

- 피봇을 랜덤하게 선택

- no worst case instance, but worst case execution

- 평균 시간복잡도 O(NlogN)

 

 

 

7. 데이터의 종류에 따른 Sorting 알고리즘 속도 비교

Sorting Algorithms Animations