수안이의 컴퓨터 연구실

버블소트

이번엔 버블소트를 배워보도록 하겠다. C를 할 줄 안다면 버블소트 정도는 잘 알 테지만, 어셈블리어로 어떻게 구현되는지 한번 유심히 살펴보길 바란다.
버블소팅을 해주는 프로시져를 하나 정의해 보겠다.

BubbleSort PROC USES eax ecx esi, pArray:PTR DWORD, Count:DWORD mov ecx, Count dec ecx L1: push ecx mov esi, pArray L2: mov eax, [esi] cmp [esi+4], eax jge L3 xchg eax, [esi+4] mov [esi], eax L3: add esi, 4 loop L2 pop ecx loop L1 L4: ret BubbleSort ENDP

< 그림 3 : 버블소트 >내부적으로 eax, ecx, esi레지스터를 쓰기에 USES 디렉티브를 사용하여 프로시져 호출 전과 후에 각 레지스터 값이 변하지 않게 하였다. 첫번째 인자로 DWORD형 배열에 대한 주소를 넘겨받고 두번째 인자로 배열 내의 원소수를 넘겨받는다. 물론 호출시 주소를 넘길 때는 ADDR연산자를 사용해야 한다는 것을 잊지 않기 바란다.

우선 루프가 두개 있음을 진한 글씨를 통해 알 수 있을 것이다. 바깥루프가 한 번 도는 동안 어떤 변화가 일어나는지는 그림3을 참고하면 이해가 빠를 것이다.

L1레이블 이전까지를 살펴보자. 버블소트에서 바깥 루프는 (원소의 개수 - 1)만큼 돌게 되므로 ecx에 값을 대입시킨다.
L1레이블은 바깥 루프의 시작부분이다. 여기서 ecx를 스택에 넣는 것은 이중 루프를 돌리기 위함이다. 두 루프가 모두 ecx를 카운터로 사용한다는 점을 염두해 두면 이해할 수 있을 것이다. 그리고 esi에 배열의 시작주소를 넣는다.
L2레이블은 안쪽 루프의 시작부분으로서, esi가 가리키는 원소와 그 다음 원소를 비교해서 순서가 맞지않을 경우 두 자료를 교환해준다. 만약 순서가 맞아서 교환할 필요가 없다면 L3로 점프하게 된다. 즉, 교환하지 않는다.
L3레이블에서는 esi가 다음 원소를 가리키게 하고, (여기서 DWORD형이기 때문에 4를 증가시킨 것임을 알아두어라) 아까 스택에 넣어두었던 ecx를 꺼내게 된다. 다시 한번 말하지만, 이는 이중루프를 돌리기 위한 것이다.
L4레이블은 함수를 종료하는 부분이다. 단지 보기 편하라고 달아둔 것이니 헷갈리지 않기 바란다.

여기서는 버블소트에 대한 알고리즘을 익히고자 한 것이 아니라, 배열과 관련된 내용을 많이 배웠으니 실제 사용할 때 어떻게 쓰이는지 익히고자 하는 의도였다. 따라서 알고리즘이 이해되지 않아도 신경쓸 필요가 없는 것이다. 다만 배열을 저렇게 사용할 수 있구나, 하는 것만 알아두기 바란다.

마치는 글

이번 회에서는 조금 특이한 형태의 인스트럭션도 배웠다. CPU내의 인스트럭션 차원에서 배열을 지원해 준다는 것이 어찌보면 의외였을지도 모르겠다. 또, 이차원 배열의 사용법과 버블소트 예제를 배웠는데, 이렇게 하나하나 배워가는 것이 여러분들의 컴퓨터에 대한 이해에 도움을 주었길 빈다. 다음 회에서는 구조체와 매크로를 배운 후, 링크드리스트를 만들어 간단히 테스트하는 예제도 배울 것이다. 구조체를 직접 어셈블리어로 만들어 보는 것도 매우 흥미롭지 않을까 생각한다.다음 회에서 다시 뵙길 빌며 이만 본회를 마치겠다.

"Assembly" 카테고리의 다른 글