Recursive algorithms
; This program takes an unsorted array and sorts
; it using mergesort.
INCLUDE Irvine32.inc
.data
ProgInfo BYTE "CPSC 232 - Mergesort Program", 0
unSortList DWORD 1000, 501, 100, 51, 0, 1, 1, 0, 50, 101, 500, 1001
;unSortList DWORD 0,1,0,1,0,0,0,1,1,1,0,1,0
;unSortList DWORD 27,10,12,20,25,13,44,15,22,10,44,50,10
;unSortList DWORD 27,1000,12,20,25,13,44,15,22,10,44,50,10
;unSortList DWORD 100,99,98,97,96,95,94,93,92,91,90,50,51,52,53,54,55,56,57,59,59,10,9,8,7,6,5,4,3,2,1,0
tempList DWORD (LENGTHOF unsortList) DUP(0)
List1 BYTE "The unsorted list is: ", 0
List2 BYTE 10,"The sorted list is: ", 0
comma BYTE ", "
.code
Display PROC
mov eax,[esi]
add esi, 4
call writedec
dec ecx
DisplayLoop:
lea edx, comma
call writestring
mov eax,[esi]
add esi, 4
call writedec
loop DisplayLoop
ret
Display ENDP
Merge proc
L1:
cmpebx, 0
je AddArray2
cmpecx, 0
je AddArray1
mov eax,[esi]
cmpeax,[edi]
jl AddArray1 ;Jump if less
jmp AddArray2 ;Jump if greater or equal
AddArray1:
cmpebx, 0
je EndJump
mov eax,[esi]
mov [edx],ax
add esi,4
add edx,4
dec ebx
jmp L1
AddArray2:
cmpecx, 0
je EndJump
mov eax,[edi]
mov [edx],ax
add edi,4
add edx,4
dec ecx
jmp L1
EndJump:
ret
Merge ENDP
; Sorts using mergesort,
; requires esi = array to sort, edi = temporary array, ecx = array length
MergeSort PROC
push ecx ; save length
push esi ; save array
push edi ; save temp array
cmpecx, 1 ; if length is 1, it's sorted
jleendSort
push ecx
shr ecx,1 ; divide length by 2
call MergeSort ; sort the half array
mov eax, ecx
pop ecx
push esi
push eax
sub ecx, eax ; get length of second half of array
shleax, 2 ; multiply first array length by 4
add esi, eax ; advance pointer
call MergeSort ; sort the half array
mov edx, edi
mov edi, esi
pop ebx ; load length of first array
pop esi ; load address of first array
call Merge
mov esi,[esp] ; load address of temp array
mov edi,[esp + 4] ; load address of initial array
mov ecx, [esp+8] ; load number of elements
; copy from temp to initial array
copy:
mov eax,[esi]
mov [edi], eax
add esi, 4
add edi, 4
loop copy
endSort:
pop edi ; restore registers
pop esi
pop ecx
ret
MergeSort ENDP
main PROC
mov edx, OFFSET Proginfo
call WriteString
call Crlf
call Crlf
mov edx, offset List1
call writestring
mov ecx,lengthofunsortList
mov esi,offsetunsortList
call Display
mov esi,OFFSETunsortList
mov edi,OFFSETtempList
mov ecx,LENGTHOFunsortList ; elements in list
call MergeSort
mov edx, offset List2
call writestring
mov ecx,lengthofunsortList
mov esi,offsetunsortList
call Display
call Crlf
exit
main ENDP
END main
Defining and calling functions
# Get a valid coffee order
def get_customer_order():
print("We serve Long Black, Flat White, Latte, Short Black")
coffee = input("What would you like? ")
while coffee != "Long Black"\
and coffee != "Flat White"\
and coffee != "Latte"\
and coffee != "Short Black":
coffee = input("Can you please try again? ")
return coffee
# Function to force the user enter a Y or N answer
def confirm(prompt):
while True:
response = input(prompt)
if response == "Y" or response == "N":
return response
# Get whether there will be milk on the side
def get_extras():
if confirm("Do you want milk on the side (Y/N)? ") == "Y":
return "Milk on the side"
return "No extras"
# Get whether to take out or dine in
def get_here_or_to_go():
if confirm("Would you like your order to go (Y/N)? ") == "Y":
return "To go"
return "In cafe"
if __name__ == '__main__':
print("Welcome to my Coffee Shop")
# Set the coffee settings
coffee = get_customer_order()
extras = "No extras"
if coffee == "Long Black" or coffee == "Short Black":
extras = get_extras()
here_or_to_go = get_here_or_to_go()
# Print the order
print()
print(coffee)
if extras is not None:
print(extras)
print(here_or_to_go)
