자료구조 25강 - 쾌속 정렬

쾌속 정렬(Quick Sort)

 

• 분할 정복 구조의 정렬 알고리즘 cf. 합병 정렬 - 분할, 정복, 결합 / 쾌속 정렬 - 분할, 정복
• 결합을 요구하지 않는 분할 정복 구조
• 리스트를 적절하게 분할해서 결합의 필요성을 제거

 

- 쾌속 정렬의 근거

 

• 결합을 요구하지 않도록 리스트를 적절하게 분할(split)하는 방법을 적용
• 분할(split)

1. 기준이 되는 값(pivot)을 중심
2. pivot의 왼쪽에는 더 작은 값이 오도록 배치
3. pivot의 오른쪽에는 더 큰 값이 오도록 배치

 

- 합병 정렬과 비교 

 

• 합병 정렬에서의 분할(divide) : 16, 12, 5, 38 → 16,12 / 5, 38
• 쾌속 정렬에서의 분할(split) : 12, 5 / 16(pivot) / 38

 

- 분할(split) 알고리즘

 

int split(int s, int e, int A[]){
	int pivot, left, right;
	left=s+1; 
	right=e;
	pivot=A[s];
	whlile(left<=right){
		while((A[right]>=pivot) && (left<=right)) right--;
		while((A[left]<=pivot) && (left<=right)) left++;
		if(left<=right) swap(A[left],A[right]);
	}
	swap(A[right],A[s]);//A[s]:pivot;
	return right;
}

 

- 쾌속 정렬 알고리즘 

 

void quick_sort(int s, inte, int A[]){
	if(s>=e)return;
	int m=split(s,e,A);
	quick_sort(s,m-1,A);
	quick_sort(m+1,e,A);
}

 

- 쾌속 정렬 수행 예시

 

A[ ]= { 16, 12, 5, 38, 19, 4, 20, 27}
qs(0, 7); → m=3 : 4, 12, 5 / 16(pivot) / 19, 38, 20, 27
-qs(0, 2); → m=0 : 4 / 12, 5 / 16 / 19, 38, 20, 27
--qs(0, -1) → 잘못된 식으로 예외 규정에 의해 정렬 수행 x
--qs(1, 2); → m=2 : 4 / 5 / 12 / 16 / 19, 38, 20, 27
---qs(1, 1); → 원소가 하나이기 떄문에 수행 x
---qs(3, 2); → 잘못된 식으로 예외 규정에 의해 정렬 수행 x
-qs(4, 7); → m=4 : 4 / 5 / 12 / 16 / 19 / 38, 20, 27
--qs(4, 3); → 잘못된 식으로 예외 규정에 의해 정렬 수행 x
--qs(5, 7); → m=7 : 4 / 5 / 12 / 16 / 19 / 20, 27 / 38
---qs(5, 6); → m=6 : 4 / 5 / 12 / 16 / 19 / 20 / 27 / 38
---qs(8, 7); → 잘못된 식으로 예외 규정에 의해 정렬 수행 x

 

- 쾌속 정렬의 시간 복잡도

 

T(n) = (n+1) + 1/n∑(T(k-1)+T(n-k)) → O(n log n)

 

- 쾌속 정렬과 합병 정렬의 성능 비교

 

케이스 종류	예시	쾌속 정렬	합병 정렬
Best case	5 1 6 3 4 8 7 2	O(n log n)	O(n log n)
Worst case	1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1	O(n²)	O(n log n)
Average case	4 1 3 6 5 2 9 8	O(n log n)	O(n log n)

 

 

내부 정렬 vs 외부 정렬

 

• 내부 정렬(internal sorting) : 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식
• 외부 정렬(external sorting) : 대용량의 보조 기억 장치를 이용해서 정렬하는 방식

 

 

쉘(Shell) 정렬

 

• 일반화된 삽입 정렬
• 배열을 여러 개의 부분 배열로 분할하여 각각 삽입 정렬을 수행
• 정렬된 부분 배열을 통합하면서 삽입 정렬을 반복해서 수행

 

- 쉘 정렬 수행 예시 

 

a[ ] = { 2, 5, 3, 4, 3, 9, 3, 2, 5, 4, 1, 3 }

 

1단계 : 크기 3의 부분 배열 4개로 분할하여 정렬

 

2	5	3	4	→	2	4	1	2
3	9	3	2		3	5	3	3
5	4	1	3		5	9	3	4

 

2단계 : 크기 6의 부분 배열 2개로 분할하여 정렬

 

2	1	→	2	1
3	3		3	2
5	3		4	3
4	2		5	3
5	3		5	3
9	4		9	4

 

3단계 : 하나의 행렬로 통합하여 정렬

 

2	3	4	5	5	9	1	2	3	3	3	4
→
1	2	2	3	3	3	3	4	4	5	5	9

 

 

기수(Radix) 정렬

 

• 버킷(bucket)을 이용하는 분배 방식의 정렬
• 정렬할 원소를 버킷에 분배하는 과정을 반복해서 정렬을 수행함

 

- 기수 정렬 수행 예시

 

0. 초기화 : 10개의 버킷을 준비

 

정렬할 원소

 

69

10

30

2

16

8

31

22

 

버킷0	버킷1	버킷2	버킷3	버킷4	버킷5	버킷6	버킷7	버킷8	버킷9

 

1. 1의 자리수에 따라서 버킷에 저장

 

①

②

③

④

⑤

⑥

⑦

⑧

 

버킷0	버킷1	버킷2	버킷3	버킷4	버킷5	버킷6	버킷7	버킷8	버킷9
10	31	2				16		8	69
30		22

 

2. 버킷에 저장된 수를 정렬

 

10

30

31

2

22

16

8

69

 

버킷0	버킷1	버킷2	버킷3	버킷4	버킷5	버킷6	버킷7	버킷8	버킷9
①	③	④				⑥		⑦	⑧
②		⑤

 

3. 10의 자리수에 따라서 버킷에 저장

 

①

②

③

④

⑤

⑥

⑦

⑧

 

버킷0	버킷1	버킷2	버킷3	버킷4	버킷5	버킷6	버킷7	버킷8	버킷9
2	10	22	30			69
8	16		31

 

4. 버킷에 저장된 수를 정렬

 

2

8

10

16

22

30

31

69

 

버킷0	버킷1	버킷2	버킷3	버킷4	버킷5	버킷6	버킷7	버킷8	버킷9
①	③	⑤	⑥			⑧
②	④		⑦

 

 

정렬의 성질

 

1. Adaptive : 부분적으로 정렬된 데이터에 대해서 더 좋은 성능을 보이는가?
2. Stable : 같은 값을갖는 원소들이 자리를 바꾸는가?
3. In-Place : 추가적으로 요구하는 메모리가 O(1)인가?
4. Online : 계속 증가하는 데이터에 대해서 정렬이 가능한가?

 

 

정렬 결론

 

• 단순 정렬 알고리즘 : O(n²) 성능 : 버블 정렬, 삽입 정렬, 선택 정렬 등
• 분할정복 정렬 알고리즘 : O(n log n) 성능 : 합병 정렬, 쾌속 정렬 등
• 성능의 차이가 크기 때문에 분할정복 정렬 알고리즘을 사용할 것