// file: part.isc // author: keller // purpose: partitioning portion of quicksort // // description: // Label array_base at the very end of this code is used as // the address of the first location of an array (of longs). // Numbers are read from the input device (the standard input) // and stored into increasing locations in this array. // // Subroutine 'part' is called, which partitions the array whose // lower and upper addresses are passed in arg1 and arg2. // Partitioning involves selecting the median element as a "pivot", // then using the pivot to divide the array so that elements // below the divider are <= the pivot and elements above the // divider are >= than the pivot. Note that elements equal to // the pivot may occur in either half. The pivot value is returned // as the value of the subroutine (in register result). // After calling 'part', the pivot element is output for reference, // then the partitioned array is output. // example: // // If the input is: 9 3 1 7 5 8 6 2 0 4 // Then the output is: 5 4 3 1 0 2 8 6 5 7 9 // where the first 5 is the value of the pivot element // The paritition break occurs between 2 and 8. Values 4 3 1 0 2 // are <= 5 an values 8 6 5 7 9 are >= 5. define max_size 2000 // limit on array size for this program // test with: random N | isc part.isc // where N is a number not more than max_size above // This program sets the input routine to jump to the address in // register 'end_of_file' on end of file. By using end-of-file to // delimit the list of numbers, we don't have to input a count of // the number of elements in the list. // Convention: specific register assignments will be used for all subroutines register return 0 // standard return address reg register result 1 // standard result register register arg1 2 // first argument register register arg2 3 // second argument register // Other arbitrary register uses use jump_target // use to hold jump target addresses use zero // use to hold 0 use end_of_file // use to hold address of where to go on eof use in_el // pointer to array location for input use out_el // pointer to array location for output use top_el // pointer to top possible element use input_word // register to hold input_word use input_status // register to hold input_status use output_word // register to hold output_word use output_status // register to hold input_status use pivot // registers used in qsort use ai use aj use temp origin 0 // start loading instructions at location 0 // set up standard register contents lim zero 0 // constant 0 lim jump_target io_setup // initialize io jsub jump_target return // // input phase // lim end_of_file eof // set up end-of-file address lim in_el array_base // initialize array element pointer aim in_el -1 // always points to last element input lim top_el array_base // pointer to last possible array element aim top_el max_size aim top_el -1 label in_loop jgt zero in_el top_el // immediate exit if array is full lim jump_target input // load address of input routine jsub jump_target return // get input value aim in_el 1 // point to next location in array store in_el result // put value from result into array lim jump_target in_loop junc jump_target // go back for more input label eof // come here on end of input file // // top-level call to part // lim arg1 array_base // load argument registers copy arg2 in_el lim jump_target part // call part subroutine jsub jump_target return // // output phase // copy arg1 result // get pivot element lim jump_target output // load address of output routine jsub jump_target return // output pivot element lim out_el array_base // initialize array element pointer aim out_el -1 // always points to previous element output label out_loop lim jump_target exit jgte jump_target out_el in_el // stop when last element was output aim out_el 1 // increment pointer load arg1 out_el // get value from array into arg1 lim jump_target output // load address of output routine jsub jump_target return // put output value lim jump_target out_loop junc jump_target // go back for more output label exit junc zero // leave the program // // part subroutine // refer to /cs/cs60/sorts/quicksort_ptr.h to see derivation of code // label part jgt return arg1 arg2 // go back if partitioning done add temp arg1 arg2 // compute hi + lo lim pivot 1 // use pivot as a temp shr temp temp pivot // compute (hi + lo)/2 load pivot temp // use middle array element as pivot aim arg1 -1 // set up for up_loop aim arg2 1 // set up for down_loop label part_loop lim jump_target up_loop label up_loop // do aim arg1 1 // { i++; } load ai arg1 jlt jump_target ai pivot // while( a[i] < pivot ) lim jump_target down_loop label down_loop // do aim arg2 -1 // { j--; } load aj arg2 jgt jump_target aj pivot // while( a[j] > pivot ) lim jump_target break jgte jump_target arg1 arg2 // if( i >= j ) break store arg1 aj // exchange(a[i], a[j]) store arg2 ai lim jump_target part_loop junc jump_target label break copy result pivot // return the pivot value junc return // i/o routines define input_word_loc -1 // fixed location for input word define input_status_loc -2 // fixed location for input status define output_word_loc -3 // fixed location for output word define output_status_loc -4 // fixed location for output status trace 0 label io_setup // setup registers for i/o lim input_word input_word_loc // memory-mapped input lim input_status input_status_loc // input status lim output_word output_word_loc // memory-mapped output lim output_status output_status_loc // input status junc return label input // input routine, returns result in register 'result' lim jump_target input // set up to loop back store input_status zero // wait for input ready load temp input_status // get input status jlt end_of_file temp zero // jump on end-of-file load result input_word // load from input word jeq jump_target temp zero // loop back if previous input not done junc return label output // output routine, outputs word in register 'arg1' load temp output_status // get output status in temp lim jump_target output // set up loop address jeq jump_target temp zero // wait for output ready store output_word arg1 // set up for output of result store output_status zero // request output junc return trace 1 label array_base // the array will be stored starting here