다음을 참조하여, 피봇(pivot)값을 이용하는 정렬 방법과 아래의 ㉠… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 07년 1회차
다음을 참조하여, 피봇(pivot)값을 이용하는 정렬 방법과 아래의 ㉠ ~ ㉤에 들어갈 값이 올바르게 나열된 것은?데이터 = {60, 50, 13, 92, 52, 2, 69, 30, 78, 42}
단계1) 피봇값 : ( ㉠ )
- 왼쪽으로부터 비교 : ( ㉡ )에서 비교 멈춤
- 오른쪽으로부터 비교 : ( ㉢ )에서 비교 멈춤
- ( ㉣ )과(와) ( ㉤ )의 저장 위치 교환
정렬 방법 ㉠ ㉡ ㉢ ㉣ ㉤
1
퀵 정렬 52 60 42 60 42
2
쉘 정렬 52 60 42 60 42
3
퀵 정렬 60 92 42 92 42
4
쉘 정렬 60 92 42 92 42
해설
피봇을 쓰는 정렬은 퀵 정렬이고, 첫 원소 60을 피봇으로 잡으면 92와 42의 위치를 교환한다.
왼쪽부터는 피봇보다 큰 값을 찾아 50, 13을 지나 92에서 멈추고, 오른쪽부터는 피봇보다 작은 값을 찾아 바로 42에서 멈춘다. 이어 두 값의 저장 위치를 바꾼다.
- 쉘 정렬과 짝지은 나열: 쉘 정렬은 간격을 줄여 가며 삽입 정렬을 반복하는 방식으로 피봇을 쓰지 않는다.
- 피봇을 52로 둔 퀵 정렬 나열: 분할 구간의 첫 원소를 피봇으로 삼는 기본 방식과 맞지 않는다.
오류나 개정된 내용이 보이면 알려주세요