-
[문제해설] 다음 자료에 대하여 버블 정렬을 이용하여 오름차순으로 정렬할 경우 “pass 1"의 실행 결과는?전자계산기조직응용기사/필기 기출문제 해설 2021. 11. 1. 00:11반응형
전자계산기조직응용기사 필기 기출문제 (2과목 자료구조 및 데이터통신-정렬) - 2019년3회, 2016년3회
다음 자료에 대하여 버블 정렬을 이용하여 오름차순으로 정렬할 경우 “pass 1"의 실행 결과는?
4, 7, 3, 1, 5, 8, 2, 6 ① 3, 1, 4, 5, 2, 6, 7, 8
② 1, 3, 4, 2, 5, 6, 7, 8
③ 4, 3, 1, 5, 7, 2, 6, 8
④ 1, 3, 2, 4, 5, 6, 7, 8
- 문제 해설 -
버블 정렬(bubble sort)은 리스트에서 2개의 인접한 값을 비교하여 그 크기에 따라 위치를 서로 교환하는 정렬 방식입니다. 버블 정렬은 간단한 정렬이면서 기사 시험에서 자주 출제되는 정렬이기도 합니다. 알고리즘은 간단해서 쉽게 이해되지만, 여러 가지 정렬을 학습하다 보면 각 회전(pass)의 주기가 어디부터 어디까지인지가 헷갈리니 정확하게 확인해야 합니다.간단한 버블 정렬의 예시를 살펴보겠습니다.(다른 기출문제)
리스트에 위와 같은 순으로 데이터가 저장되어 있습니다. 버블 정렬로 오름차순으로 정렬하겠습니다.
먼저 1번째, 2번째 값을 비교합니다. 큰 값이 오른쪽이어야 합니다. 8이 5보다 크니 두 값을 교환합니다.
이번에는 2, 3번째 값을 비교합니다. 8이 6보다 크니 두 수를 교환합니다.
3,4번째 값을 비교합니다. 8이 2보다 크니 두 수를 교환합니다.
4,5번째 값을 비교합니다. 8이 4보다 크니 두 수를 교환합니다. 그리고 가장 좌측의 8은 위치가 확정됩니다.
여기까지가 Pass 1(1회전)입니다. 매 Pass마다 최우 측 자료의 위치가 고정됩니다. 같은 알고리즘으로 반복한 전체 pass 결과는 다음표와 같습니다.
초기값 8 5 6 2 4 Pass 1 5
5
5
58
6
6
66
8
2
22
2
8
44
4
4
8Pass 2 5
5
56
2
22
6
44
4
68
8
8Pass 3 2
25
44
56
68
8Pass 4 2 4 5 6 8 위 표에서 각 라인의 2개의 보라색이 비교하는 데이터이고, 초록색은 위치가 확정된 데이터입니다.
다시 강조하면, 교환 알고리즘도 알아야 되지만, 패스 주기도 정확하게 알아야 합니다.
그럼 본문제에서 주어진 리스트(4, 7, 3, 1, 5, 8, 2, 6)를 버블 정렬 알고리즘으로 정렬하면 다음 표와 같습니다.
초기값 4 7 3 1 5 8 2 6 Pass 1 4
4
4
4
4
4
47
3
3
3
3
3
33
7
1
1
1
1
11
1
7
5
5
5
55
5
5
7
7
7
78
8
8
8
8
2
22
2
2
2
2
8
66
6
6
6
6
6
8Pass 2 3
3
3
3
3
34
1
1
1
1
11
4
4
4
4
45
5
5
5
5
57
7
7
7
2
22
2
2
2
7
66
6
6
6
6
78
8
8
8
8
8Pass 3 1
1
1
1
13
3
3
3
34
4
4
4
45
5
5
2
22
2
2
5
56
6
6
6
67
7
7
7
78
8
8
8
8Pass 4 1
1
1
1
13
3
3
3
34
4
4
2
22
2
2
4
45
5
5
5
56
6
6
6
67
7
7
7
78
8
8
8
8Pass 5 1
1
13
2
22
3
34
4
45
5
56
6
67
7
78
8
8Pass 6 1
12
23
34
45
56
67
78
8Pass 7 1 2 3 4 5 6 7 8 본문제에서 묻고 있는 Pass 1의 실행 결과는 [4, 3, 1, 5, 7, 2, 6, 8]이니, 정답은 3번입니다.
https://youtube.com/playlist?list=PLboXycXmAIDuukQ2A6EvMZI-x1IMy3Xc-
전자계산기조직응용기사 필기
국가기술자격증 '전자계산기조직응용기사' 필기 강의
www.youtube.com
반응형'전자계산기조직응용기사 > 필기 기출문제 해설' 카테고리의 다른 글
[문제해설] 한 문자가 6비트로 되어있는 자료에서 한 문자를 전송하는데 100ms가 소요되었다면 몇 bps로 전송되는가? (0) 2021.11.09 [문제해설] 정규화 과정 중 1NF에서 2NF가 되기 위한 조건은? (0) 2021.11.03 [문제해설] Infix 표기의 식 (A/(B^C))*D＋E를 Postfix 방법으로 바르게 표현한 것은? (0) 2021.10.28 [문제해설] 2진수 덧셈으로 8비트(bit) 레지스터 250과 10을 더하는 ADC 명령어를 사용하여 덧셈한 결과는? (0) 2021.10.26 [문제해설] 다음의 프로그램을 실행한 결과로 옳은 것은? (0) 2021.10.25