Re: Contest #2... Example Programs
- Posted by PeteE Dec 12, 2010
- 2822 views
Quicksort: recursive function using a stack. The quicksort function prints the upper index, pivot index, and upper index at each invocation, and displays the partially sorted array after partitioning. The stack grows downward from the top of ram, and is used for return address and saving local registers. Function arguments and return values are passed in registers.
288 r8=8 (stack pointer) *** quicksort *** 485 r8*=5 (40) 485 r8*=5 (200) 485 r8*=5 (1000) 877 r7=[r7] (-1, keep it constant throughout) 211 r1=1 (load the initial array starting at ram[1]) 209 r0=9 304 r0+=4 (13) 403 r0*=3 (39) 402 r0*=2 (78) 901 [r1]=r0 311 r1+=1 207 r0=7 403 r0*=3 (21) 302 r0+=2 (23) 901 [r1]=r0 311 r1+=1 209 r0=9 405 r0*=5 (45) 402 r0*=2 (90) 901 [r1]=r0 311 r1+=1 208 r0=8 901 [r1]=r0 311 r1+=1 207 r0=7 405 r0*=5 (35) 901 [r1]=r0 311 r1+=1 209 r0=9 304 r0+=4 (13) 901 [r1]=r0 311 r1+=1 207 r0=7 407 r0*=7 (49) 901 [r1]=r0 311 r1+=1 209 r0=9 409 r0*=9 (81) 302 r0+=2 (83) 901 [r1]=r0 311 r1+=1 209 r0=9 406 r0*=6 (54) 901 [r1]=r0 311 r1+=1 208 r0=8 407 r0*=7 (56) 305 r0+=5 (61) 901 [r1]=r0 561 r6=r1 (upper index, constant throughout) 208 r0=8 407 r0*=7 (56) 305 r0+=5 (61) 687 r8+=r7 908 [r8]=r0 (push return address) 299 r9=9 494 r9*=4 (36) 391 r9+=1 (37) 492 r9*=2 (74) 099 if r9 show_array 209 r0=9 408 r0*=8 (72) 301 r0+=1 (73) 687 r8+=r7 908 [r8]=r0 (push return address) 201 r0=1 (lower index) 516 r1=r6 (upper index) 296 r9=6 495 r9*=5 (30) 391 r9+=1 (31) 493 r9*=3 (93) 099 if r9 quicksort 100 halt 201 r0=1 (lower index) <-- show_array 517 r1=r7 (-1) 716 r1*=r6 (-upper index) 610 r1+=r0 (loop counter) 890 r9=[r0] <-- show_loop 301 r0+=1 ??9 (print value) 311 r1+=1 299 r9=9 394 r9+=4 (13) 493 r9*=3 (39) 492 r9*=2 (78) 091 if r1 show_loop 890 r9=[r0] ?9 (print value) 898 r9=[r8] (pop return address) 381 r8+=1 099 goto r9 (ret) 300 nop 687 r8+=r7 <-- quicksort (r0: lower index, r1: upper index, [r8]=return address) 918 [r8]=r1 (push upper index) 687 r8+=r7 908 [r8]=r0 (push lower index) 717 r1*=r7 520 r2=r0 621 r2+=r1 299 r9=9 392 r9+=2 (11) 495 r9*=5 (55) 492 r9*=2 (110) 092 if r2 check_index 300 nop 382 r8+=2 (pop upper and lower index) <-- quicksort_done 898 r9=[r8] (pop return address) 381 r8+=1 099 goto r9 (ret) 627 r2+=r7 <-- check_index 298 r9=8 495 r9*=5 (40) 493 r9*=3 (120) 092 if r2 calculate_pivot1 297 r9=7 497 r9*=7 (49) 394 r9+=4 (53) 492 r9*=2 (106) 099 if r9 quicksort_done (lower index > upper index) 311 r1+=1 <-- calculate_pivot1 520 r2=r0 621 r2+=r1 299 r9=9 492 r9*=2 (18) 391 r9+=1 (19) 497 r9*=7 (133) 092 if r2 calculate_pivot2 299 r9=9 495 r9*=5 (45) 392 r9+=2 (47) 493 r9*=3 (141) 099 if r9 found_pivot 301 r0+=1 <-- calculate_pivot2 520 r2=r0 621 r2+=r1 298 r9=8 495 r9*=5 (40) 493 r9*=3 (120) 092 if r2 calculate_pivot1 300 nop 520 r2=r0 (pivot index) <-- found_pivot 838 r3=[r8] (lower index) 381 r8+=1 848 r4=[r8] (upper index) 687 r8+=r7 ??3 (print lower index) ??2 (print pivot index) ?4 (print upper index) 802 r0=[r2] (pivot value) 814 r1=[r4] (upper value) 912 [r2]=r1 (swap them) 904 [r4]=r0 523 r2=r3 (store index) 554 r5=r4 757 r5*=r7 653 r5+=r3 (loop counter) 300 nop 803 r0=[r3] (index value) <-- quicksort_loop 814 r1=[r4] (pivot value) 298 r9=8 497 r9*=7 (56) 493 r9*=3 (168) 395 r9+=5 (173) 687 r8+=r7 998 [r8]=r9 (push return address) 298 r9=8 495 r9*=5 (40) 493 r9*=3 (120) 391 r9+=1 (121) 492 r9*=2 (242) 099 if r9 compare 300 nop 299 r9=9 494 r9*=4 (36) 391 r9+=1 (37) 495 r9*=5 (185) 090 if r0 quicksort_loop_next 803 r0=[r3] (index value) 812 r1=[r2] (store value) 913 [r3]=r1 (swap them) 902 [r2]=r0 321 r2+=1 300 nop 300 nop 331 r3+=1 <-- quicksort_loop_next 351 r5+=1 299 r9=9 498 r9*=8 (72) 397 r9+=7 (79) 492 r9*=2 (158) 095 if r5 quicksort_loop 804 r0=[r4] (pivot value) 812 r1=[r2] (store value) 914 [r4]=r1 (swap them) 902 [r2]=r0 298 r9=8 495 r9*=5 (40) 495 r9*=5 (200) 399 r9+=9 (209) 687 r8+=r7 998 [r8]=r9 (push return address) 299 r9=9 494 r9*=4 (36) 391 r9+=1 (37) 492 r9*=2 (74) 099 if r9 show_array 300 nop 300 nop 808 r0=[r8] (lower index) 687 r8+=r7 928 [r8]=r2 (push pivot index) 512 r1=r2 617 r1+=r7 (pivot index - 1) 299 r9=9 495 r9*=5 (45) 495 r9*=5 (225) 687 r8+=r7 998 [r8]=r9 (push return address) 296 r9=6 495 r9*=5 (30) 391 r9+=1 (31) 493 r9*=3 (93) 099 if r9 quicksort (recursively call quicksort) 300 nop 808 r0=[r8] (pop pivot index) 381 r8+=1 301 r0+=1 (pivot index + 1) 381 r8+=1 818 r1=[r8] (load upper index) 687 r8+=r7 297 r9=7 497 r9*=7 (49) 394 r9+=4 (53) 492 r9*=2 (106) 687 r8+=r7 998 [r8]=r9 (push return address) 296 r9=6 495 r9*=5 (30) 391 r9+=1 (31) 493 r9*=3 (93) 099 if r9 quicksort (recursively call quicksort) 707 r0*=r7 <-- compare (returns with r0=0 if r0<=r1, r0=1 otherwise) 610 r1+=r0 (find the difference and make a copy. increment the first copy 501 r0=r1 and decrement the second copy until one of them reaches zero.) 300 nop 311 r1+=1 <-- compare_1 298 r9=8 498 r9*=8 (64) 494 r9*=4 (256) 090 if r0 compare_2 (return 0 if r0 <= r1) 898 r9=[r8] (pop return address) 381 r8+=1 099 goto r9 (ret) 300 nop 300 nop 607 r0+=r7 <-- compare_2 298 r9=8 495 r9*=5 (40) 391 r9+=1 (41) 493 r9*=3 (123) 492 r9*=2 (246) 091 if r1 compare_1 201 r0=1 (return 1 if r0 > r1) 898 r9=[r8] (pop return address) 381 r8+=1 099 goto r9 (ret)
