Please do it in LC-3 programming language, and also make sure you run it before you send it. I want to see the solution. Additionally, please pay attention to the note part and the extra instruction before the template. Thank You In Advance!!
Implement arecursivequicksort for sorting the n 16-bit data items stored in the array Data in ascending order. Declare two labels n and Data to hold the # of data items and the actual data to be sorted respectively. You may assume that the data values to be sorted are between 0 and 127. Before performing the sort, print the data elements, treating each as an ASCII character. Once the data has been sorted, print the contents of the array, treating each element as an ASCII character. For testing your program, use the data found in data.asm.
Your output should look something like:
Unsorted data: 9 6 3 0 1 2 8 7 5 4
Sorted data: 0 1 2 3 4 5 6 7 8 9
Implement your solution by creating a routine partition that accepts as parameters a pointer to an array and start and end index values. The routine will use the contents of array[start] as the pivot and returns the index of the pivot value (after partitioning). Your quicksort routine will then make use of partition to perform the sort.
NOTE: implementing a swap routine may prove useful for completing partition. At a minimum youmust use the push and pop routines, that is it must be on a stack.
I have attached a template. Feel free to edit it.Do not CMP or SUB. TY!
.orig x3000
; Register Dictionary
; -------------------
; R0 - data
; R1 - n
; R6 - stack pointer
LD R6, stackbase
LEA R0, data;load the addr of the data into r0
LD r1, n; load n into r1
add r1, r1 #-1; n-1
LEA R2, 0 ; index is 0
ADD R3, R0, R1 ; End index is n-1
JSR quicksort ; Call quicksort with start and end indices
; Halt the program
HALT
;------------------------------------------------------
;Subroutine Push
;pushes the contents of Top of Stack into R0
Push
ADD R6,R6,#-1
STR R0,R6,#0
RET
;------------------------------------------------------
;Subroutine Pop
;pops the contents of Top of Stack into R0
;R0 - will contain value of data popped.
Pop
LD R0,STACKBASE ;get stack back
NOT R0,R0
ADD R0,R0,#1 ;negate it
ADD R0,R0,R6 ;compare stackbase with current stack pointer
BRnp PopOkay
LEA R0,StrUnderflow ;stack underflow
trap x22 ;Content of R0 is undetermined.
BR PopDone
PopOkay
LDR R0,R6,#0
ADD R6,R6,#1
PopDone
RET
n .fill 163 ;# of data points
data .fill x5D ;test data
.fill x38
.fill x57
.fill x56
.fill x55
.fill x54
.fill x53
.fill x30
.fill x2A
.fill x5E
.fill x38
.fill x69
.fill x7A
.fill x52
.fill x51
.fill x50
.fill x4F
.fill x34
.fill x58
.fill x6C
.fill x2A
.fill x38
.fill x6E
.fill x30
.fill x2A
.fill x5E
.fill x35
.fill x34
.fill x32
.fill x31
.fill x30
.fill x39
.fill x38
.fill x37
.fill x36
.fill x5E
.fill x38
.fill x6E
.fill x5C
.fill x60
.fill x34
.fill x4E
.fill x4D
.fill x4C
.fill x4B
.fill x4A
.fill x49
.fill x59
.fill x78
.fill x77
.fill x76
.fill x75
.fill x74
.fill x73
.fill x72
.fill x71
.fill x70
.fill x6F
.fill x6E
.fill x6D
.fill x6C
.fill x6B
.fill x6A
.fill x5A
.fill x68
.fill x67
.fill x66
.fill x65
.fill x47
.fill x46
.fill x45
.fill x44
.fill x63
.fill x62
.fill x61
.fill x5A
.fill x22
.fill x2A
.fill x48
.fill x43
.fill x42
.fill x41
.fill x38
.fill x57
.fill x56
.fill x55
.fill x54
.fill x53
.fill x30
.fill x2A
.fill x5E
.fill x38
.fill x69
.fill x7A
.fill x52
.fill x51
.fill x50
.fill x4F
.fill x34
.fill x58
.fill x6C
.fill x2A
.fill x38
.fill x6E
.fill x30
.fill x2A
.fill x5E
.fill x35
.fill x34
.fill x32
.fill x31
.fill x30
.fill x39
.fill x38
.fill x37
.fill x36
.fill x5E
.fill x38
.fill x6E
.fill x5C
.fill x60
.fill x34
.fill x4E
.fill x4D
.fill x4C
.fill x4B
.fill x4A
.fill x49
.fill x22
.fill x2A
.fill x41
.fill x42
.fill x43
.fill x44
.fill x45
.fill x46
.fill x47
.fill x48
.fill x59
.fill x5A
.fill x5A
.fill x61
.fill x62
.fill x63
.fill x65
.fill x66
.fill x67
.fill x68
.fill x6A
.fill x6B
.fill x6C
.fill x6D
.fill x6E
.fill x6F
.fill x70
.fill x71
.fill x72
.fill x73
.fill x74
.fill x75
.fill x76
.fill x77
.fill x78