왜 이 소문제를 따로 배우는가
bubble sort의 inner loop에는 off-by-one, Byte scaling, compare inversion이 한꺼번에 들어 있습니다. bound→주소→값→skip branch의 네 상태를 분리하면 out-of-bounds와 불필요한 swap을 동시에 막을 수 있습니다.
이 페이지는 Aufgabe 3의 공통 템플릿이 아니라 3-5 안쪽 loop와 비교에 필요한 내용만 담습니다. 챕터 전체 배경이 필요하면 Aufgabe 3 개념 수업을 먼저 읽으세요.
이 소문제에서 실제로 쓰는 용어
정의뿐 아니라 이 문제의 어느 판단에 쓰이는지까지 연결합니다.
- inner bound
- 현재 outer iteration에서 j가 가질 수 있는 exclusive upper bound `n-i-1`입니다.이 소문제에서: `j>=bound`이면 outer_inc로 나가도록 비교합니다.
- adjacent elements
- array에서 index가 1 차이 나는 `arr[j]`와 `arr[j+1]`입니다.이 소문제에서: 같은 base address에서 offset 0과 4로 두 word를 load합니다.
- ble
- 첫 signed operand가 둘째보다 작거나 같으면 branch하는 pseudo instruction입니다.이 소문제에서: 이미 오름차순인 `arr[j]<=arr[j+1]`이면 swap을 건너뜁니다.
- off-by-one
- loop bound에서 1이 빠지거나 더해져 한 iteration을 누락하거나 범위를 넘는 오류입니다.이 소문제에서: `j+1`이 최대 n-1이 되도록 j의 bound가 `n-i-1`인지 검산합니다.
이 소문제 전용 규칙과 종이 작업
exclusive bound 규칙
inner body는 `j < n-i-1`일 때만 실행하므로 반대 조건 `j>=n-i-1`에서 종료합니다.
종이에: `bound=n-i-1`, `valid j=0…bound-1`을 씁니다.
이웃 주소 재사용 규칙
`int` 이웃은 4 Byte 차이므로 `&arr[j]`를 한 번 만든 뒤 offset 0과 4로 load하면 됩니다.
종이에: `t1=&arr[j]`, `0(t1)=arr[j]`, `4(t1)=arr[j+1]`을 표시합니다.
swap 필요 조건 분리
오름차순에서는 왼쪽 값이 더 클 때만 swap하므로 `left<=right`이면 swap을 skip합니다.
종이에: `swap iff left>right; skip iff left<=right` 두 줄을 씁니다.
Aufgabe 전체 흐름은 챕터 흐름도에서 확인할 수 있습니다. 여기서는 현재 판단에 직접 필요한 규칙만 적용합니다.
이 소문제 전용 작은 예제
n=6, i=2, j=1, base=`0x1000`, arr[1]=9, arr[2]=4일 때 inner guard, 주소, 비교 결과를 trace하세요.
주어진 것
- s1=n=6, s2=i=2, s3=j=1입니다.
- `int`는 4 Byte입니다.
- inner bound를 계산하고 j와 비교합니다.
memory access 전에 j와 j+1이 유효한지 확인합니다.
종이 산출물: `bound=6-2-1=3; 1>=3 false → continue`
- `&arr[1]`과 이웃 주소를 계산합니다.
base+scaled index에서 두 word를 읽어야 합니다.
종이 산출물: `t1=0x1000+1×4=0x1004; neighbor=0x1008`
- 두 값을 load해 skip 조건을 검사합니다.
9<=4가 거짓이므로 현재 순서가 잘못되어 swap이 필요합니다.
종이 산출물: `t2=9, t3=4; ble 9,4 false`
- control-flow 결론을 씁니다.
ble가 taken되지 않으면 다음 instruction인 swap call로 fall-through합니다.
종이 산출물: `fall-through → swap(arr,1,2)`
예제 답과 독립 검산 보기
bound=3이라 body를 실행하며 주소는 `0x1004`와 `0x1008`입니다. 9<=4가 거짓이므로 swap을 호출해야 합니다.
독립 검산: swap 후 두 값이 4,9가 되어 오름차순 이웃 조건을 만족하는지 확인합니다.
이제 실제 시험 문제를 micro-work로 풀기
공식 시험이 요구하는 것
`j < n-i-1`과 `arr[j] > arr[j+1]`을 구현하세요.
공식 답을 보기 전, 내 답 먼저 남기기
완성 문장이 아니어도 좋습니다. 중간값·register·cycle·cache state처럼 채점 가능한 흔적을 먼저 적으세요.
각 작업의 중간 산출물을 직접 적고 완료 조건을 만족한 뒤 체크하세요. 단계별 이유·산출물·오류가 현재 소문제에 맞게 따로 작성되어 있습니다.
현재 inner bound `n-i-1`을 t0에 계산합니다.
- 왜 하는가
- 각 outer iteration마다 정렬된 suffix가 하나씩 늘어나므로 검사 범위가 i에 따라 줄어듭니다.
- 종이 산출물
- `sub t0,s1,s2; addi t0,t0,-1 # t0=n-i-1`
- 완료 조건
- t0가 n-i가 아니라 n-i-1로 표시되어 있습니다.
막혔을 때 단계 힌트·대표 오류
힌트: 먼저 n-i를 구한 뒤 1을 빼세요.
이 단계의 대표 오류: `n-i`까지만 계산해 j+1이 array 끝을 넘을 수 있게 만드는 것입니다.
j>=bound이면 outer_inc로 탈출합니다.
- 왜 하는가
- 유효 조건 `j<bound`의 부정이며 더 이상 비교할 이웃 쌍이 없음을 나타냅니다.
- 종이 산출물
- `bge s3,t0,outer_inc # if j>=n-i-1 exit inner`
- 완료 조건
- source s3=j, t0=bound와 target outer_inc가 맞습니다.
막혔을 때 단계 힌트·대표 오류
힌트: j가 bound와 같아지는 순간 `arr[j+1]`이 현재 범위를 벗어납니다.
이 단계의 대표 오류: `bgt`만 사용해 j=bound에서도 body를 한 번 더 실행하는 것입니다.
j를 4배하고 arr base를 더해 `&arr[j]`를 만듭니다.
- 왜 하는가
- RISC-V memory address는 Byte 단위이며 int index는 4-Byte scale이 필요합니다.
- 종이 산출물
- `slli t1,s3,2; add t1,s0,t1 # t1=&arr[j]`
- 완료 조건
- t1의 최종 의미가 scaled offset이 아니라 absolute address입니다.
막혔을 때 단계 힌트·대표 오류
힌트: s0에는 Prolog에서 보존한 arr base가 있습니다.
이 단계의 대표 오류: s3를 그대로 s0에 더하거나 s0 자체를 destination으로 덮는 것입니다.
`0(t1)`과 `4(t1)`에서 이웃 값을 load합니다.
- 왜 하는가
- `arr[j+1]`는 int 하나 뒤이므로 새 index/address 계산 없이 현재 주소+4를 사용할 수 있습니다.
- 종이 산출물
- `lw t2,0(t1) # left; lw t3,4(t1) # right`
- 완료 조건
- t2=arr[j], t3=arr[j+1]의 방향이 표시되어 있습니다.
막혔을 때 단계 힌트·대표 오류
힌트: 두 번째 offset은 index 1이 아니라 Byte 4입니다.
이 단계의 대표 오류: `lw t3,1(t1)`로 한 Byte 뒤에서 misaligned word를 읽는 것입니다.
left<=right이면 inner_inc로 가서 swap을 건너뜁니다.
- 왜 하는가
- 오름차순에서 이미 올바른 이웃은 교환할 필요가 없고, left>right일 때만 call로 fall-through해야 합니다.
- 종이 산출물
- `ble t2,t3,inner_inc # skip swap if ordered`
- 완료 조건
- taken=skip, not taken=swap이라는 control-flow가 값 조건과 일치합니다.
막혔을 때 단계 힌트·대표 오류
힌트: swap 조건 `left>right`의 반대를 branch 조건으로 사용하세요.
이 단계의 대표 오류: `bge` 방향을 잘못 사용해 정렬된 쌍을 swap하고 역순 쌍을 건너뛰는 것입니다.
공식 답을 열기 전 마지막 회상
왜 bubble sort의 안쪽 upper bound는 반복마다 1씩 줄어드나요?
내 풀이 후 공식 결론·이유·대표 함정 확인
공식 결론
`sub t0,s1,s2; addi t0,t0,-1; bge s3,t0,outer_inc; slli t1,s3,2; add t1,s0,t1; lw t2,0(t1); lw t3,4(t1); ble t2,t3,inner_inc`.
왜 이 답이 되는가
매 반복에서 현재 upper bound를 계산하고, 이웃 두 word는 같은 base address에서 offset 0과 4로 읽을 수 있습니다.
대표 함정
`j+1` 주소를 다시 처음부터 계산할 필요 없이 현재 주소+4를 쓸 수 있습니다.
명령어와 식을 줄 단위로 읽기
본문 속 code를 한 줄씩 분리했습니다. 각 줄에서 source, operation, destination을 표시하세요.
j < n-i-1
arr[j] > arr[j+1]
sub t0,s1,s2;
addi t0,t0,-1;
bge s3,t0,outer_inc;
slli t1,s3,2;
add t1,s0,t1;
lw t2,0(t1);
lw t3,4(t1);
ble t2,t3,inner_inc;새 문제로 전이하기
세 문항은 앞 문장의 반복이 아닙니다. 직접 답을 입력하면 rubric의 필수 기준을 하나씩 검사하고, 첫 누락 기준을 알려 줍니다.
1. 개념 재구성
bubble sort inner iteration 하나를 bound check, address, two loads, skip condition의 네 상태로 복원하고 각 register 의미를 쓰세요.
t0, t1, t2, t3이 각각 무엇을 담는지 고정하세요.
제출 후 모델 답 보기
`t0=n-i-1`을 만들고 `j>=t0`이면 종료합니다. `t1=base+j×4=&arr[j]`를 만들고 `t2=0(t1)=left`, `t3=4(t1)=right`를 load합니다. `left<=right`이면 swap을 skip하고, 아니면 swap을 호출합니다.
2. 변형 문제
n=5, i=1, j=2이고 arr[2]=3, arr[3]=7이다. inner bound, guard 결과, load offset, ble 결과를 계산하세요.
bound는 exclusive이며 j와 같아도 종료합니다.
제출 후 모델 답 보기
`bound=5-1-1=3`, `j=2<3`이므로 body를 실행합니다. `&arr[2]`에서 offset 0과 4로 3과 7을 load하고 `3<=7`이 참이라 ble가 taken되어 swap을 skip합니다.
3. 오류 진단
학생 code는 bound를 `n-i`로 두고 j=bound-1에서도 `arr[j+1]`을 읽습니다. n=5, i=0에서 첫 off-by-one과 접근 index를 계산해 고치세요.
올바른 마지막 j와 잘못된 마지막 j를 각각 구하세요.
제출 후 모델 답 보기
첫 오류는 bound에서 마지막 -1을 빠뜨린 것입니다. 잘못된 bound=5이면 j=4까지 body가 가능해 `arr[5]`를 읽어 out-of-bounds입니다. 올바른 bound는 `n-i-1=4`이고 valid j는 0…3이라 마지막 이웃은 `arr[4]`입니다.
이 소문제를 끝냈다고 말할 수 있는 기준
이 소문제의 정확한 공식 페이지와 대조하기
왼쪽은 문제를 읽을 때, 오른쪽은 자신의 풀이를 끝낸 뒤에 확인하세요. 해설 이미지를 먼저 보면 중간 과정을 스스로 만드는 연습이 사라집니다.
Source: Probeklausur.pdf / Probeklausur Musterlösung und Hinweise.pdf · 시험 p7–8 · 공식 해설 p8–11 · SoSe26 Probeklausur 시험 p7–8 Aufgabe 3의 inner loop·이웃 비교와 공식 해설 p10의 bound/address/load/ble 구현 범위.