7.1 QuickSort

p는 pivot을, i는 low side, j는 high side를 가르킨다.

(a) 배열의 초기 상태이다. p가 가르키는 값을 한번 스왑한다.

(b) pivot 값은 스스로 swap을 한다.

(c) - (d) p가 가르키는 값보다 크므로, high side는 커진다. 

(e) j가 가르키는 값이 p가 가르키는 값 보다 작으므로, i + 1과 가르키는 값과 swap한다. 

(f) j가 r-1이 되면 j와 r을 swap한다.

 

Excercise1. 13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11을 quick sort 정렬함을 보여주세요.

j											r
13	19	9	5	12	8	7	4	21	2	6	11
i	j										r
13	19	9	5	12	8	7	4	21	2	6	11
	i	j									r
13	9	19	5	12	8	7	4	21	2	6	11
		i	j								r
13	9	5	19	12	8	7	4	21	2	6	11
			i	j							r
13	9	5	12	19	8	7	4	21	2	6	11
				i	j						r
13	9	5	12	8	19	7	4	21	2	6	11
					i	j					r
13	9	5	12	8	7	19	4	21	2	6	11
						i	j				r
13	9	5	12	8	7	4	19	21	2	6	11
						i		j			r
13	9	5	12	8	7	4	19	21	2	6	11
							i		j		r
13	9	5	12	8	7	4	2	21	19	6	11
								i		j	r
13	9	5	12	8	7	4	2	6	19	21	11
										j	i
13	9	5	12	8	7	4	2	6	11	21	19