다음 데이터를 퀵정렬(quick sort)하려고 한다. 퀵정렬 1단계 … | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 09년 1회차
다음 데이터를 퀵정렬(quick sort)하려고 한다. 퀵정렬 1단계 과정이 끝난 후, 피봇키(pivot key)를 중심으로 좌측에는 피봇키보다 작은 수, 우측에는 피봇키보다 큰 수들로 데이터가 분할된 상태를 올바르게 나타낸 것은? (단, 피봇키는 가장 왼쪽에 있는 값으로 한다)
(초기데이터)
[0][1][2][3][4][5][6][7][8][9]
8149635270

(보기의 인덱스: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9])
1
7 1 4 6 3 5 2 0 8 9
2
7 1 4 0 6 3 5 2 8 9
3
2 1 4 0 6 3 5 7 8 9
4
0 1 4 2 6 3 5 7 8 9
해설

1단계 분할 결과는 7 1 4 0 6 3 5 2 8 9이다.

피봇 8을 두고 왼쪽 포인터 i는 8보다 큰 값, 오른쪽 포인터 j는 8보다 작은 값을 찾아 교환한다.
i는 9([3]), j는 0([9])에서 멈춰 교환 → 8 1 4 0 6 3 5 2 7 9
다시 i는 9([9]), j는 7([8])에서 멈추고 두 포인터가 엇갈린다.
마지막으로 피봇과 j 위치의 7을 교환 → 7 1 4 0 6 3 5 2 8 9

  • 7 1 4 6 3 5 2 0 8 9: 9와 0의 교환이 반영되지 않아 0이 [3]에 오지 않았다.
  • 2 1 4 0 6 3 5 7 8 9: 피봇은 j 위치의 7과 교환되므로 [0]에는 7, [7]에는 2가 그대로 있어야 한다.
  • 0 1 4 2 6 3 5 7 8 9: [0]에는 7, [3]에는 0, [7]에는 2가 와야 하므로 교환 결과와 맞지 않는다.

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

이어서 풀어보기

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