Quick Sort using Mips

※ Quick Sort using Mips

• Tool

- SPIM : Simulator of MIPS Processor (Software in order to execute assembly code

http://spimsimulator.sourceforge.net/

• Instruction Set

https://en.wikipedia.org/wiki/MIPS_instruction_set

•  Result Screen

•  Source Explanation

main:

 addi $v0, $zero, 5

 syscall

 add $s0, $zero, $v0

 la $t0, count

 sw $s0, 0($t0)

 la $t0, array

 li $t1, 0

$v0레지스터에 5를 저장하여 콘솔창에서 입력한 값을 받아오기 위한 시스템 콜을 사용하여 $s0레지스터에 저장하였다.

그 값을 count레이블 위치에(변수처럼 사용) 저장하였다. array레이블(배열)의 주소값을 변수에 저장하기 위해 la명령어를 통해 $t0레지스터에 저장하였다. $t1레지스터는 array배열의 인덱스로 사용한다. $t1레지스터는 반복문 횟수를 위해 0을 저장하여 사용한다.

 

L1:

 beq $t1, $s0, Else # 카운트값과 t1의 0을 비교한다.

 li $v0, 5

 syscall

 sw $v0, 0($t0)

 addi $t0, $t0, 4 # 배열의 크기 만큼 더한다.

 addi $t1, $t1, 1 # 반복문 횟수

 j L1

반복문을 사용하기 위한 곳이다. $t1 (count만큼 반복하기 위한 변수)와 $s0(count)값을 beq명령어를 사용하여 같으면 Else로 넘어가 반복문을 빠져나오게 한다.

$v0에 5를 저장하여 시스템 콜을 이용하여 count값만큼 정렬할 숫자를 입력받는다. 매 반복문 마다 $t0의 값을 4씩 증가시키고(인덱스 주소 접근이기 때문에 4바이트씩 이동하기 위해서) $t1은 1씩 증가시켜 count만큼 반복한다. ($s0와 같아 질 때 까지)

 

Else:

 addi $s0, $s0, -1 # last인덱스를 위해 카운트값에 1을 빼준다.

 li $a0, 0 # left

 add $a1, $zero, $s0 # right

 addi $sp, $sp, -4

 sw $ra, 0($sp)

 jal QuickSort

 lw $ra, 0($sp)

 addi $sp, $sp, 4

QuickSort에 전달할 argument를 결정한다. last ( 만약에 count가 5이면 index는 0~4이기 때문에 )에 1을 빼준다.

argument는 $a0~$a1에 각각 left, right값을 함수로 전달하기 위해 저장한다.

QuickSort 함수를 jal명령어(이 다음 명령어의 주소를 $ra에 저장한다)를 통해 해당 레이블로 이동한다. 스택포인터를 이용해 $ra레지스터에 main문을 부른 곳으로 반환 될 주소를 저장한다.

함수 호출 후 사용한 스택공간은 원래대로 돌려준다.

-----------------------------------------------------------------------------

 la $t1, count

 lw $t1, 0($t1)

 li $t0, 0

 la $t2, array

L2:

 beq $t1, $t0, ProgramExit # 카운트값과 t1의 0을 비교한다.

 li $v0, 1

 lw $t3, 0($t2)

 add $a0, $zero, $t3

 syscall

 

 li $v0, 4

 la $t4, str

 add $a0, $zero, $t4

 syscall

 addi $t2, $t2, 4 # 배열의 크기 만큼 더한다.

 addi $t0, $t0, 1 # 반복문 횟수

 j L2

 

ProgramExit:

 jr $31

QuickSort 함수를 빠져나오게 되면 정렬된 값을 출력하기 위해 count값과 array 주소 값과 반복하기 위한 값을 각각 레지스터에 저장한다. beq반복문을 통해 위와 비슷한 방법으로 같으면 ProgramExit 레이블로 이동한다. 같지 않다면 바로 밑에 명령어부터 차례대로 실행한다.

시스템호출($v0이 1일 때 콘솔창 출력)을 통해 정렬된 값들을 array배열에서 순서대로 하나씩 출력한다.

각 값마다 구분을 짓기 위해 str레이블 주소를 가져와서 (.asciiz " ") 공백 띄어쓰기가 저장되있는 값을 시스템호출( $v0이 4일 때 콘솔창 string 출력)한다.

jr $31을 통해 main함수를 호출했던 곳의 바로 다음 명령어로 돌아간 후 프로그램은 종료된다.

 

-----------------------------------------------------------------------------

QuickSort:

 addi $sp, $sp, -16

 sw $ra, 12($sp)

 sw $a2, 8($sp)

 sw $a1, 4($sp)

 sw $a0, 0($sp)

재귀 함수 호출이 되기 때문에 현재 전달된 parameter값과 복귀할 주소의 레지스터를 –16 만큼 확장한 스택에 저장한다. $a0~$a1은 left~right를 의미한다. $a2는 추후에 사용될 피벗값이 각각 함수마다 적용 하는 값이 다르기 때문에 재귀호출로 인해 없어지기 때문에 스택에 저장한다.

 

 slt $t5, $a0, $a1 #if(left<right)

 beq $t5, $zero, QuickSortElse1

slt명령어는 $a0 < $a1 일 때 $t5에 1을 저장하며 그렇지 않으면 0을 저장한다. 반복문을 위해 사용하였다. left값이 right보다 작은 경우 1이 저장되어 beq에서는 0하고 비교를 하므로 beq입장에서는 조건이 만족되지 않아서 QuickSortElse1 레이블로 이동하지 않는다.

만약 slt명렁어에서 left값이 right보다 커지는 경우는 beq입장에서는 0이 되어 참이 되기 때문에 QuickSortElse1로 이동한다. QuickSortElse1는 해당 QuickSort를 빠져나오는 레이블이다.

 

 jal Partition 

 add $a2, $v0, $zero

피벗값을 구하기 위한 Partition 함수를 호출한다. (해당 레이블로 이동)

Partition을 통해 결정된 피벗은 $v0(return value라는 뜻으로 반환값이 있을 때 주로 사용하는 레지스터)에 저장된 값을 퀵정렬을 위해서 분할하여 QuickSort를 호출하기 위해 $a2에 저장한다.

 

 addi $sp, $sp, -16

 sw $ra, 12($sp)

 sw $a2, 8($sp)

 sw $a1, 4($sp)

 sw $a0, 0($sp)

 addi $a1, $a2, -1

 jal QuickSort

 lw $a0, 0($sp)

 lw $a1, 4($sp)

 lw $a2, 8($sp)

 lw $ra, 12($sp)

 addi $sp, $sp, 16

현재 전달된 parameter값과 복귀할 주소의 레지스터를 –16 만큼 확장한 스택에 저장한다. Partition함수를 갔다오고 여기저기 재귀호출 되기 때문에 Partition전에 파라미터값을 저장했다고 하여 스택에 저장하지 않는다면 추후에 스택의 값을 불러왔을 때 잘못된 값이 저장된다.

pivot값 $a2에 저장된 값에 1을 빼서 pivot-1을 만든다. 그 후 분할된 값들을 재귀호출을 위해 QuickSort(left, pivot-1) 호출한다.

QuickSort(left, pivot-1) 호출후 호출전 스택에 저장했던 값들을 그대로 다시 불러온다. (오른쪽으로 분할할 때 같은 인수들을 사용해야 하기 때문이다.)

 addi $sp, $sp, -16

 sw $ra, 12($sp)

 sw $a2, 8($sp)

 sw $a1, 4($sp)

 sw $a0, 0($sp)

 addi $a0, $a2, 1

 jal QuickSort

 lw $a0, 0($sp)

 lw $a1, 4($sp)

 lw $a2, 8($sp)

 lw $ra, 12($sp)

 addi $sp, $sp, 16

위와 같은 이유로 인수들과 복귀할 주소를 저장한다. pivot+1을 만들기 위해 pivot값이 있는 $a2에 1을 더하여 $a0에 저장한다. 그 후 분할된 값들을 재귀호출을 위해 QuickSort(pivot+1, right) 호출한다.

 

 QuickSortElse1: #left>=right가 되면

 lw $a0, 0($sp)

 lw $a1, 4($sp)

 lw $a2, 8($sp)

 lw $ra, 12($sp)

 addi $sp, $sp, 16

 jr $ra 

QuickSort를 호출할 때 left와 right 조건을 검사하여 left>=right가 되면 QuickSortElse1레이블로 이동하게 된다. 함수가 종료 되더라도 재귀호출이기 때문에 다음 함수에서 사용하기 위해 스택에 저장된 값들을 불러와 저장한다.

jr명령어를 통해 $ra에 들어있는 이 함수를 호출한 곳으로 돌아간다.

 

-----------------------------------------------------------------------------

Partition:

 la $s0, array # array 접근

 sll $t5, $a0, 2 # int pivot = arr[left]; $t5는 인덱스값 구하기용

 add $t6, $t5, $s0 # 배열에 left만큼 접근 $t6은 배열 값용

 lw $t0, 0($t6) # $t0는 피벗

 addi $t1, $a0, 1 # $t1은 int low = left+1; $t1은 low

 addi $t2, $a1, 0 # $t2은 int high = right; $t2는 high

$s0에 array주소를 가져온다. $a0은 전달받은 parameter값(left)이다. left값을 인덱스로 이용하여 해당 배열의 값을 pivot으로 사용한다.(Quick정렬) 레지스터 설명은 해당 주석에 같이 써놓았다.

 

PartitionLoop:

 addi $t3, $t2, 1 # $t3은 high+1 표현

 slt $t4, $t1, $t3 # low < high+1 // $t4는 slt판단 용으로 사용한다.

 beq $t4, $zero, PartitionExit # while(low <= high) // 교차되지 않을 때까지 반복

low<=high를 표현하기 위해 $t3에 $t2(high)값과 1을 저장하여 low값과 비교하게 한다. slt명령어는 $t1<$t3이기 때문에 $t3에 1을 더하게 되면 low<=high 같은 효과를 낼 수 있다.

( 또는 slt 명령어와 beq 로 ‘<’ 사용후 beq명령어로 = 표현하면 <=표현이 가능하다. )

slt을 이용해 $t4값이 <이 성립하여 1이 되면 beq명령어에서는 0과 같은지 비교하기 때문에 같지 않으면 그대로 다음 명령어로 진행되며 같게 되면 PartitionExit레이블로 이동한다.

 

PartitionLoop1:

 la $s0, array

 sll $t5, $t1, 2 # arr[low]

 add $t6, $t5, $s0

 lw $t7, 0($t6) # $t7은 인덱스를 이용한 배열 하나의 값

low 인덱스를 이용한 배열 값을 받기위해 위와 같은 방법으로 배열의 값을 구하여 arr[low]를 구한다.

$t7에 arr[low]값을 저장한다.

 addi $t8, $t0, 1 # pivot >= arr[low] $t8은 임시 피벗

 slt $t4, $t7, $t8 # // while(pivot >= arr[low] && low <= right) // pivot >= arr[low]

 beq $t4, $zero, PartitionElse1

pivot>=이므로 >=을 이용하기 위해 (위와 같은 방법으로 1을 더한다) 임시 레지스터 $t8에 pivot값과 1을 저장하여 arr[low]값과 >= 비교를 위해 slt명령어를 사용한다. 위에서 언급한거와 같이 slt조건에 따라 beq조건이 완성되며 beq조건이 만족 될 시 즉 pivot >= arr[low]가 만족 하지 않는다면 PartitionElse1로 이동한다.

 

 addi $t8, $a1, 1 # // while(pivot >= arr[low] && low <= right) low <= right

 slt $t4, $t1, $t8 # $t8은 '<=' 처리문으로 사용

 beq $t4, $zero, PartitionElse1

 addi $t1, $t1, 1 # low++;

 j PartitionLoop1

여기서는 while(pivot >= arr[low] && low <= right) 두가지 연산을 비교하여 &&연상을 하므로 beq를 두 번 호출 하여 두 조건중 하나라도 맞는다면 같은 레이블 PartitionElse1 이동하게 한다. 위에서 언급한거와 같은 방법으로 low <= right을 구한다. 만약에 두 beq값이 둘 다 조건이 false라면 low값에 1을 더한다. (Quick정렬을 통한 low부터 시작하여 pivot값보다 큰 값을 찾는 현상이다.)

반복문 조건이 하나라도 만족 될 때 까지 j PartitionLoop1로 점프하여 반복한다.

 

PartitionElse1:

위의 두 beq중 하나라도 만족하여 PartitionElse1레이블로 이동하면 high도 pivot값보다 작은 값을 찾기 위해 비슷한 방법을 취한다.

 

PartitionLoop2:

 la $s0, array

 sll $t5, $t2, 2 # arr[high]

 add $t6, $t5, $s0

 lw $t7, 0($t6)

 arr[high]값을 구하기 위해 PartitionLoop1에서 언급한 것과 비슷한 방식으로 구한다.

 # while(pivot <= arr[high] && high >= (left+1))

 addi $t8, $t7, 1 # pivot <= arr[high]

 slt $t4, $t0, $t8

 beq $t4, $zero, PartitionElse2

pivot <= 표현하기 위해 arr[high] 값에 1을 더하여 $t8레지스터에 저장하고 slt와, beq명령어를 이용하여 pivot <= arr[high] 한다. beq조건이 맞는다면 즉 pivot이 더 크다면 PartitionElse2 이동한다.

PartitionElse1과 같이 while(pivot <= arr[high] && high >= (left+1)) 두 조건을 검사하기 위해 beq를 두 번 사용하고 조건이 만족되는 레이블은 하나로 한다.

 

 addi $t8, $t2, 1 # high >= (left+1))

 addi $t9, $a0, 1 # (left+1) 특별히 사용, 위에 것과 구분하기 위해..

 slt $t4, $t9, $t8

 beq $t4, $zero, PartitionElse2

 addi $t2, $t2, -1 $ high--

 j PartitionLoop2

high >= (left+1))을 표현하기 위해 위와 같은 방법이므로 생략한다.

beq 2개가 모두 만족하지 않는다면 high값에 1을 빼준다.

(Quick정렬을 통한 high부터 시작하여 감소하면서 pivot값보다 작은 값을 찾는 현상이다.)

 

PartitionElse2:

두 beq중 어느 하나라도 조건이 만족 하지 않을 시 PartitionElse2레이블로 이동한다.

 

 addi $t8, $t2, 1 # if(low <= high) // 교차되지 않은 상태라면 Swap 실행

 slt $t4, $t1, $t8

 beq $t4, $zero, PartitionElse3

low값과 high값을 비교하여 서로의 값이 교차 했는지 확인한다. beq명령어를 통해 교차된다면 PartitionElse3레이블로 이동한다.

 

 add $s5, $t1, $zero

 add $s6, $t2, $zero

교차되지 않는다면 두 값을 서로 바꿔줘야 하기 때문에 low, high값을 swap함수에서 사용할 $s5, $s6레지스터에 저장한다.

 addi $sp, $sp, -4

 sw $ra, 0($sp)

 jal Swap

 lw $ra, 0($sp)

 addi $sp, $sp, 4

해당 위치로 돌아오기 위해 스택에 -4를하여 주소값을 $ra에 저장후 Swap함수를 호출한다. (Swap 레이블로 이동한다.)

 

PartitionElse3:

if(low <= high)조건이 만족하지 않는다면 다시 PartitionLoop을 하기 위해 돌아간다. low값이 high값보다 커지기 때문에 Partition함수는 끝날 것이다.

조건이 만족하고 이곳으로 온다면 PartitionLoop으로 이동하여 교차될 때 까지 반복할 것이다.

 j PartitionLoop

반복문이 low < high+1 조건이므로 반복하기 위해 PartitionLoop레이블로 다시 점프한다.

 

PartitionExit:

 add $s5, $a0, $zero

 add $s6, $t2, $zero

 addi $sp, $sp, -4

 sw $ra, 0($sp)

 jal Swap

 lw $ra, 0($sp)

 addi $sp, $sp, 4

 add $v0, $zero, $t2

 jr $ra

$s5와 $s6에 left와 high값을 저장후 swap 함수를 호출하여 두 인덱스를 이용하여 배열의 값을 바꾼다.

마지막으로 Quick정렬을 하다보면 high와 low가 교체 될 때, high값은 pivot이 되기 때문에 반환할 pivot값을 $v0레지스터에 저장한다.

jr $ra를 통해 Partition 함수를 반환하고 호출한 위치로 돌아간다.

-----------------------------------------------------------------------------

Swap:

Swap함수로 전달된 2개의 값을 서로 바꾸는 함수이다. 이 함수는 배열 안에 있는 각각 값들을 바꿔주는 역할을 한다.

 

 sll $t5, $s5, 2

 sll $t6, $s6, 2

sll명령어는 shift left logic 로 시프트 연산 명령어이다. 전달된 $s5, $s6값을 각각 왼쪽으로 2씩 이동하면 x4하는 효과가 되어 배열의 인덱스를 사용할 때 해당 주소는 4바이트씩 이동하므로 4를 곱한 이유이다.

 

 la $s0, array

array배열의 주소를 $s0에 저장한다.

 add $t5, $t5, $s0

 add $t6, $t6, $s0

$t5, $t6은 두 값을 구하기 위한 인덱스가 저장된 숫자 이므로 배열의 주소에 각각의 값을 더해서 가져올 값에 대한 주소를 $t5, $t6레지스터에 다시 저장한다.

 lw $s2, 0($t5)

 lw $s3, 0($t6)

$t5, $t6 레지스터에 저장된 인덱스를 lw명령어를 이용하여 배열의 값들을 가져온다.

 

 sw $s3, 0($t5)

 sw $s2, 0($t6)

가져온 값들을 서로 가져온 배열의 인덱스를 바꿔서 교환하게 해줘서 저장한다.

 

 jr $ra

swap함수를 빠져나오고 호출했던 곳으로 돌아간다.

-----------------------------------------------------------------------------

.data

count: .word 1

array: .space 100

str: .asciiz " ＂

데이터로 사용될 스택 공간이며 count값은 정렬할 숫자 개수

array는 100바이트의 공간이 있는 배열

str은 string 공백이 저장된 주소값

-----------------------------------------------------------------------------

s    Source Code