Do it! 자료구조와 함께 배우는 알고리즘 입문 [파이썬] #6장 정렬 알고리즘

[Do it! 자료구조와 함께배우는 알고리즘 입문] 내용을 정리한 내용입니다.

 

 

목차

• 06-5 셸 정렬 
• 06-6 퀵 정렬
• 06-7 
• 06-8 
• 06-9 

 

---

✔06-5

 

---

✔06-6 퀵 정렬

퀵 정렬 : 가장 빠른 정렬 알고리즘

키가 168cm인 학생 A를 선택하여 이 학생을 기준으로 168cm 미만인 그룹과, 168cm이상인 그룹으로 나눕니다. 이때 그룹을 나누는 기준을 피벗이라고 합니다.

 

          pl                                                                              피벗(x)                                                                               pr

5

7

1

4

6

2

3

9

8

a[pl] >= x가 성립하는 원소를 찾을 때까지 pl을 오른쪽 방향으로 스캔합니다.
a[pr] <= x가 성립하는 원소를 찾을 때까지 pr를 왼쪽 방향으로 스캔합니다. 

 

pl과 pr은 다음 그림에서 정지합니다. pl은 피벗 이상인 원소에, pr는 피벗 이하인 원소에 위치합니다. 여기서 pr과 pr가 위치하는 원소 a[pl]과 a[pr]의 값을 교환합니다. 그러면 피벗 이하인 값은 왼쪽으로 이동하고, 피벗 이상인 값을 오른쪽으로 이동합니다.

                               pl                                                                                                         pr

5

7

1

4

6

2

3

9

8

 

다시 스캔을 계속하면 pl과 pr는 다음 그림의 위치에서 정지하고, 원소 a[pl]과 a[pr]의 값을 교환합니다. 

 

                                                                                               pl                   pr

5

7

1

4

6

2

3

9

8

 

다시 스캔을 계속하면 다음 그림처럼 pl과 pr가 서로 교차합니다.

 

                                                                                               pr                  pl

5

7

1

4

2

6

3

9

8

 

pl과 pr가 교차하면 이로써 그룹을 나누는 과정이 끝나고, 배열은 두 그룹으로 나뉩니다.

피벗 이하인 그룹 : a[0], a[pl - 1]
피벗 이상인 그룹 : a[pr + 1], a[n - 1]
피벗과 일치하는 그룹 : a[pr + 1], a[pl - 1]

 

 

 

---

✔06-7

 

---

✔06-8

 

 

---