MIPS 어셈블리어로 버블소트 및 퀵소트 구현

소개글

MIPS 어셈블리어로 버블소트 및 퀵소트 구현에 대한 보고서 자료입니다.

목차

◎ Program Source 및 설명
1. Bubble Sort
2. Quick Sort

◎ 분석 및 토의

본문내용

pivot으로 설정
beq $t4,$zero, q_out# 최초 push한 0값을 pop하게 되면 끝
move $t2,$s0
move $t3,$s1
addi $t3,$t3,4
j plus_i
q_out:lw $s1, 0($sp) #restore $s0 from stack
lw $s2, 4($sp) #restore $s1 from stack
lw $ra, 8($sp) #restore $ra from stack
addi $sp, $sp, 20 #restore stack pointer
jr $ra
.data
value: .word 71,77,26,41,46,68,59,47,63,30,15,86,61,48,45,87,98,94,5,67
,96,32,8,57,1,63,49,66,70,7,42,37,19,39,33,24,4,36,20,90,93,73,58,78,50,2,
82,14,3,72
insertion: .word 100,6,80,79,60
deletion:.word 90,15,71,39,58
msg0: .asciiz "before sorting =>\n"
msg1: .asciiz "after quick sorting =>\n"
msg2:.asciiz "inserting =>\n"
msg3:.asciiz "deleting =>\n"
space: .asciiz " "
nl: .asciiz "\n"
◎ 분석 및 토의
1. 버블소트
버블소트는 인접한 데이터의 값을 비교해서 순서화되어있지 않으면 교환하는 것이다. 우리가 구현한 것과 같은 오름차순 정렬은 첫 번째와 두 번째의 값을 비교해서 만약 두 번째 값이 첫 번째 값보다 작으면 두 개의 데이터를 서로 바꿔주고, 이런 방법으로 계속해서 인접한 값을 마지막까지 비교하면 한 단계가 끝나게 되는데, 한 단계 수행의 결과로 리스트의 마지막에는 가장 큰 값을 갖는 데이터가 위치한다. 두 번째 단계에서는 마지막 데이터를 제외하고 첫 단계와 동일한 작업을 수행하고 이러한 작업을 모든 데이터가 정렬될 때까지 수행한다. 이러한 알고리즘으로 위의 코드를 구현하였고, 수업교제 2장에 배열과 SORT의 예제에서 그 코드를 참고하여 BUBBLE SORT MIPS PROCEDURE를 구현하였다.
ㅇ INSERTING
MIPS코드를 사용하여 insert는 생각보다 구현이 어려웠다. 그리고 문제를 잘못 읽은 관계로 하나 삽입 후 출력하고 또 다시 하나 삽입 후 출력해야 하는 줄 알고, 그런 식으로 코드를 구현하여, instruction count가 더 증가했다. 그러나 중간중간의 결과를 잘 볼 수 있고, 구현한 노력이 아까워 그냥 그대로 제출하게 되었다. INSERTING은 처음에는 하나의 새로운 값을 집어넣고 다시 SORTING하면 되는 줄 알았지만, 문제가 의도하는 것이 그게 아닌 것 같았다. 그렇게 되면 삽입한 값이 계속 움직이게 되므로 기존의 소팅된 것을 바꾸는 셈이 되는 것 같았다. 그래서 새로운 데이터를 배열 끝에 삽입하고 일단 배열을 가만히 놔둔 상태에서 삽입할 곳을 찾아서 그 자리에 삽입하라는 것이 문제의 의도 것으로 생각하고 INSERTING을 구현하였다. 처음에는 데이터구조에서 배운 링크드 리스트 방법을 적용해 볼까 했지만 그것이 불가능 하거나 복잡하다고 생각하여 제일 생각하기 쉬운 방법을 사용했다. 먼저 배열이 저장되어 있는 메모리 끝에 공간을 하나 더 만들어 삽입할 데이터를 저장한 후 앞에서부터 삽입할 데이터가 들어갈 자리를 찾는다. 그리고 그 자리를 찾았으면, 배열의 맨 끝에서부터 한 칸씩 뒤로 당겨 삽입할 데이터가 들어갈 공간을 만들어 준다. 그러나 이러한 구현은 데이터를 하나씩 삽입하고 버블소트하는 것보다 비교적 느리다고 생각할 수 있다. 물론 삽입할 데이터의 크기에 따라 상황은 달라지겠지만 말이다.
ㅇ DELETING
Deleting은 insertion과 비슷한 방법을 사용했지만, 오히려 더 구현하기 쉬웠다. 일단 지울 데이터를 발견하면 그 데이터를 지울 필요 없이 그 데이터 보다 바로 큰 수(배열의 다음 수)를 한 칸 당겨서 바로 그 자리에 새롭게 저장시켜주기만 하면 되기 때문이다. 그래서 instruction count는 insertion보다 데이터 하나당 한 개가 더 적다고 생각할 수 있다.
ㅇ QUICK SORT
퀵소트는 우선 주어진 입력데이터를 특정한 값보다 작은 값을 갖는 데이터들과 큰 값을 갖는 데이터들로 분리하여 논리적으로 두 개의 부분 리스트로 재배열한다. 그런 다음 각각의 부분 리스트에 대해서 순환적으로 다시 정렬을 적용하여 입력 리스트의 모든 데이터 들을 정렬하는 알고리즘이다. 앞에서 말한 특정한 값이란 pivot을 이야기 하는데, pivot을 어떻게 잡느냐에 따라서 퀵소트의 속도가 달라질 수 있다. 여기서는 소트되기 전 입력배열의 첫 번째 값에 저장된 데이터를 처음에 pivot으로 잡고 한 단계가 끝나면 교환하는 식으로 구현하였다. 그리고 스택에 배열의 처음 값과 마지막 값을 0으로 넣어 그 경계를 알고 스택에서 0을 뽑을 때 알고리즘을 종료할 수 있도록 하였다. 그리고 나머지 INSERTION과 DELETING 방법은 앞에서 한 것과 같이 구현하였다.
ㅇ PRINT PROCEDURE
코딩하다 보니 프리트를 반복적으로 쓸 일이 많아서, 프로시져를 만들어 사용하는 것이 편하겠다고 생각하여 프로시져로 구현하게 되었다. 배열의 시작값과 배열의 크기를 $a0, $a1에 각각 입력하여 보내주면, 배열의 내용을 출력하도록 짜여있다.
수업시간에 이론으로 많이 접했지만, 직접 사용해 본 결과 MIPS는 C나 JAVA와 같은 HIGH LEVEL LANGUAGE에 비해 그 표현과정이 길어서 코드가 길어지고 복잡하게 되었다. 그리고 MIPS로 알고리즘을 구현하는데 있어서 가장 어려웠던 점은 레지스터가 제한되어 있다는 것이다. 그래서 좀 레지스터가 많이 쓰일 것 같은 과정은 프로시져 형태로 만들어 프로시져 호출시 스텍에 변수를 저장하고 사용한 다음 그 값을 돌려주는 방식으로 레지스터 수를 늘려 사용하고, 변해도 앞으로의 과정에 문제가 없다고 생각되는 레지스터들은 재사용하는 방법을 사용하여 변수문제를 해결할 수 있었다.

키워드

MIPS,   SPIM,   어셈블리어,   버블소트,   퀵소트,   bubble,   quick,   source