2750 - 수 정렬하기

info

• 문제 보기: 2750 - 수 정렬하기
• 소요 시간: 38분 ??초
• 풀이 언어: nasm x64
• 체감 난이도: 2️⃣~3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

정렬

풀이 코드

info

• 메모리: 4352 KB
• 시간: 0 ms

;#------------------------
;#  BOJ_2750 by QPID 0.<❤️
;#------------------------
default rel

global main
extern printf, scanf

section .data
    scan_fmt: db "%d", 0
    print_fmt: db "%d", 10, 0

section .bss
    n: resd 1
    arr: resd 1000

section .text

main:
    push rbp
    mov rbp, rsp

;--- input ---
scan_n:
    mov rdi, scan_fmt
    lea rsi, [n]
    xor rax, rax
    call scanf
    
scan_arr:
    xor r12, r12

scan_arr_loop:
    mov eax, [n]
    cmp r12d, eax ; i < n
    jge bubble_sort ; i >= n then sort
    
    mov rdi, scan_fmt
    lea rsi, [arr + r12*4] ; arr[i]
    xor rax, rax
    call scanf
    
    inc r12
    jmp scan_arr_loop

;--- sort ---
bubble_sort:
    mov r12d, [n]
    dec r12d
    xor r13, r13 ; idx

bubble_iloop:
    cmp r13d, r12d
    jge print_res
    xor r14, r14 ; jdx

bubble_jloop:
    mov eax, r12d
    sub eax, r13d
    cmp r14d, eax
    jge iloop_nxt
    
    ; compare arr[j] & arr[j+1]
    ; ascending order
    mov eax, [arr + r14*4]
    mov ebx, [arr + r14*4+4]
    cmp eax, ebx
    jle jloop_nxt
    
    ; swap in case of eax > ebx
    mov [arr + r14*4], ebx
    mov [arr + r14*4+4], eax
    jmp jloop_nxt
    
jloop_nxt:
    inc r14
    jmp bubble_jloop
    
iloop_nxt:
    inc r13
    jmp bubble_iloop
    
;--- output ---
print_res:
    xor r12, r12

print_loop:
    mov eax, [n]
    cmp r12d, eax
    jge cleanup
    
    mov rdi, print_fmt
    movsx rsi, dword [arr + r12*4]
    xor rax, rax
    call printf
    
    inc r12
    jmp print_loop

cleanup:
    xor rax, rax
    leave
    ret

풀이 해설

📌 r12부터 사용하는 이유

x86-64 아키텍처에서 레지스터는 크게 두 가지 부류로 나뉜다.

---

Caller-saved (Volatile)

rax, rcx, rdx, rsi, rdi, r8~r11

함수를 호출하면 값이 변할 수 있는 레지스터들이다.

Callee-saved (Non-volatile)

rbx, rbp, r12, r13, r14, r15

함수 내부에서 사용하더라도, 함수가 끝나기 전 원래의 값으로 복구해 놓아야 하는 레지스터들이다. 안해도 되긴 함

---

r12~r14를 인덱스 카운터, 데이터 보관용으로 사용한 이유는 다음과 같다.

1. printf, scanf 호출 시에도 데이터를 보존해야 해서
2. r12~r15는 외부 함수를 호출해도 값 유지가 보장되므로, 반복문의 루프 카운터를 안정적으로 유지할 수 있다.

📌 mov가 아닌 movsx를 사용한 이유

• mov: source 와 destination의 크기가 같아야 함
• movsx: sx(=sign extension)라서, 작은 크기의 signed integer source를 큰 destination 레지스터에 옮길때 사용
  • 32비트 MSB가 1이면(=음수) 남은 64비트 공간을 모두 1로 채우고, 0이면(=양수) 모두 0으로 채움

즉, arr이 dword인 resd 배열이기 때문에 64비트인 rsi 레지스터에 넣기 위해 사용한 것이다.

그 외 비교 요약

명령어	의미	비트 확장 방식
mov	단순 복사	확장 기능 없음 (크기 일치 필수)
movsx	부호 확장 복사	최상위 비트(부호) 값으로 빈 공간을 채움
movzx	제로 확장 복사	빈 공간을 무조건 0으로 채움 (unsigned일 시 사용)

메모

• x86-64 playground는 printf, scanf call이 불가하고
• tio도 마찬가지로 안되고
• Godbolt는 nasm 지원이 제대로 안되고
• JDoodle은 x86만 지원하는듯?
• 그래서 그냥 홈서버 컴에서 테스트해보고 있는데 비효율적이라서 다른 방법을 알아봐야 할 듯