키 값 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이다.

첫 레코드를 피봇으로 쓰면 정렬된 입력에서는 피봇이 항상 최솟값이 되어 한쪽이 비고 다른 쪽이 하나만 줄어드는 최악의 분할이 반복된다. 분할 한 번에 피봇을 나머지 원소와 비교한다고 보면 다음과 같다(구현에 따라 세부 횟수는 달라도 대소 순서는 같다).
4+3+2+1=104 + 3 + 2 + 1 = 10

  • 2, 3, 1, 4, 5: 피봇 2로 [1]과 [3, 4, 5]로 나뉘어 4+2+1=74 + 2 + 1 = 7회이다.
  • 3, 1, 2, 4, 5: 피봇 3이 가운데 값이라 두 원소씩 균형 있게 나뉘어 4+1+1=64 + 1 + 1 = 6회이다.
  • 3, 1, 2, 5, 4: 마찬가지로 피봇 3으로 균형 분할되어 6회이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 20년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기