4기준 값의 중요성

 

줄 세우기에서 선생님이 기준으로 정한 학생이 하필이면 열 명 중 키가 가장 작은 학생이었다면 어떻게 될까요? 안타깝게도 기준보다 작은 그룹(g1)에는 학생이 한 명도 없고, 기준보다 큰 그룹(g2)에는 나머지 학생이 모두 모인 상황이 됩니다. 이렇게 되면 그룹을 둘로 나눈 의미가 없어져 퀵 정렬의 효율이 낮아집니다.

 

따라서 퀵 정렬에서는 ‘좋은 기준’을 정하는 것이 정렬의 효율성을 가늠하므로 굉장히 중요합니다. 다만, 좋은 기준을 정하는 방법은 이 책의 범위를 넘어서는 어려운 내용이므로 예제 프로그램에서는 간단히 자료의 마지막 값을 기준 값으로 사용하였습니다.

 

그림 11-2 기준을 잘못 정한 예 ①: 가장 작은 학생을 기준으로 잡은 경우

 

그림 11-3 기준을 잘못 정한 예 ②: 가장 큰 학생을 기준으로 잡은 경우