마찬가지로 리스트 [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]를 퀵 정렬하는 과정을 직접 종이에 적으면서 과정을 이해해 보세요.

 

① 리스트에서 기준 값을 하나 정합니다. 이 책에서는 편의상 정렬할 리스트의 맨 마지막 값을 기준 값으로 정하였습니다.

[6 8 3 9 10 1 2 4 7 5]의 기준 값: 5

 

② 기준 값보다 작은 값을 저장할 리스트로 g1, 큰 값을 저장할 리스트로 g2를 만듭니다.

 

③ 리스트에 있는 자료들을 기준 값인 5와 차례로 비교하여 5보다 작은 값은 g1, 큰 값은 g2에 넣습니다. 예를 들어 6은 5보다 크므로 g2에 넣고, 그 다음 값인 8도 5보다 크므로 g2, 3은 5보다 작으므로 g1에 넣습니다.

기준 값: 5

g1: [3 1 2 4]

g2: [6 8 9 10 7]

 

④ 재귀 호출을 이용하여 g1을 정렬합니다. 함수 안에서 퀵 정렬을 재귀 호출하면서 문제를 풀어 [1 2 3 4]를 결과로 돌려줍니다.

 

⑤ 재귀 호출을 이용하여 g2를 정렬합니다. 마찬가지로 퀵 정렬로 문제를 풀어 [6 7 8 9 10]을 결과로 돌려줍니다.

 

⑥ 이제 g1에는‘기준보다 작은 값들’이 정렬되어 있고 g2에는‘기준보다 큰 값들’이 정렬되어 있습니다. 따라서 g1, 기준 값, g2를 순서대로 이어 붙이면 정렬이 완료됩니다.

[1 2 3 4] + [5] + [6 7 8 9 10] → [1 2 3 4 5 6 7 8 9 10]

 

⑦ 최종 결과: [1 2 3 4 5 6 7 8 9 10]