퀵 정렬

퀵 정렬 진행 과정

pivot

13

10

4

3

8

6

11

7

↓

↑ ↑

L R

 

가장 먼저 pivot(피봇)을 가운데 숫자인 3으로 지정한 뒤, pivot을 기준으로 가장 왼쪽인 13을 L, 가장 오른쪽인 8을 R로 설정

 

pivot

13

10

4

3

8

6

11

7

↓

↑ ↑

L R

 

L은 13으로 Pivot 이상이기 때문에 그대로지만 R은 Pivot보다 작은 값을 찾지못해 13까지 이동한다. 그러면 L과 Pivot의 값이 서로 바뀌고 옮겨진 위치 그대로 고정된다.

3

10

4

13

8

6

11

7

그리고 Pivot인 3 기준으로 왼쪽 집합 정렬을 시도하지만 왼쪽은 공집합으로 정렬 대상이 없기 때문에 정렬하지 않고 Pivot의 우측 집합을 대상으로 퀵 정렬을 시작

pivot

3

7

4

13

8

6

11

10

↓

↑ ↑

L R

이번엔 가장 왼쪽인 10을 L로 가장 오른쪽인 7을 R 그리고 중심 값인 8을 pivot으로 설정한다. L은 Pivot 이상이고, R은 8미만 이므로 서로 교환해주고 퀵 정렬 진행

pivot

3

7

4

13

8

6

11

10

↓

↑ ↑

L R

L은 아까와 마찬가지로 8 이상의 값을 찾아가다가 13에서 멈췄고,

R은 8보다 작은 값을 찾아가다가 6에서 멈춘 뒤 그대로 둘의 값을 변경한다.

pivot

3

7

4

6

8

13

11

10

↓

↑ ↑

L R

그리고 한 칸씩 전진해서 L은 8 이상의 값인 Pivot을 만나 멈추고 R은 L과 만나 멈춘 뒤 Pivot 위치를 확정시킨다.

pivot

3

7

4

6

8

13

11

10

↓

↑ ↑

L R

다음으로 Pivot이었던 8 기준으로 왼쪽 집합을 퀵 정렬 한다. Pivot은 가운데 값인 4로 설정

pivot

3

7

4

6

8

13

11

10

↓

↑↑

L R

L은 4이상이지만 R은 4 미만 숫자가 없어 6 -> 4을 거쳐 L과 만난다.

L과 R이 만났으니 Pivot과 교환한다.

3

4

7

6

8

13

11

10

 

3,4가 확정 되어 왼쪽은 공집합이라 진행할 필요가 없고 우측은 2개의 원소(7, 6)가 있으니 퀵 정렬을 진행한다.

 

pivot

3

4

7

6

8

13

11

10

↓

↑ ↑

L R

7이 L, 8은 R이 되었고 Pivot으로는 7로 설정한다.

L은 피봇 이상, R은 피봇 미만이므로 서로 교환해준다.

3

4

6

7

8

13

11

10

 

확정된 왼쪽 집합의 원소가 하나 밖에 없고 우측은 공집합이기 때문에 더 이상 진행할 수 없다.

그리고 8을 기준으로 이번에는 오른쪽 집합을 이어서 정렬

pivot

↓

3

4

6

7

8

13

11

10

↑ ↑

L R

L은 Pivot 이상이고, R은 Pivot미만이니 서로 교환해준다.

pivot

↓

3

4

6

7

8

10

11

13

↑↑

L R

L과 R이 그대로 진행하여 마지막으로 Pivot과 만나 위치를 확정 짓는다.

pivot의 왼쪽과 오른쪽 집합 모두 원소가 한 개이므로 정렬을 진행 하지 않는다.

3

4

6

7

8

10

11

13

 

더 이상 정렬할 집합이 없으므로 퀵 정렬을 완료한다.