키 값 1, 2, 3, 4, 5를 가지는 5개의 레코드로 이루어진 리스… | [7급 국가직 자료구조론] 20년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 20년 1회차
키 값 1, 2, 3, 4, 5를 가지는 5개의 레코드로 이루어진 리스트를 퀵 정렬(quick sort)로 오름차순 정렬하고자 한다. 정렬 과정에서 총 비교 횟수가 가장 많은 리스트는? (단, 피봇(pivot)은 정렬하고자 하는 대상의 첫 번째 레코드로 선택한다)
1
1, 2, 3, 4, 5
2
2, 3, 1, 4, 5
3
3, 1, 2, 4, 5
4
3, 1, 2, 5, 4
해설
총 비교 횟수가 가장 많은 리스트는 이미 정렬된 1, 2, 3, 4, 5이다.
첫 레코드를 피봇으로 쓰면 정렬된 입력에서는 피봇이 항상 최솟값이 되어 한쪽이 비고 다른 쪽이 하나만 줄어드는 최악의 분할이 반복된다. 분할 한 번에 피봇을 나머지 원소와 비교한다고 보면 다음과 같다(구현에 따라 세부 횟수는 달라도 대소 순서는 같다).
- 2, 3, 1, 4, 5: 피봇 2로 [1]과 [3, 4, 5]로 나뉘어 회이다.
- 3, 1, 2, 4, 5: 피봇 3이 가운데 값이라 두 원소씩 균형 있게 나뉘어 회이다.
- 3, 1, 2, 5, 4: 마찬가지로 피봇 3으로 균형 분할되어 6회이다.
오류나 개정된 내용이 보이면 알려주세요