StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I'm still learning 68k asm, but obviously you could accomplish this task with the <code>cmp</code> opcode.</p> <p>Here's a quicksort implementation I found <a href="http://pat.dmj.free.fr/us/programes.htm" rel="nofollow noreferrer">at this site</a>:</p> <pre><code>************************************************************SIM68K V1.1US*** * * * Program : QSORT.ASM * * Quick Sort is a classical recursive sort algorithm. * * Being very famous, I prefer you search how it works in a computer * * science book. * * This instance of "Quick Sort" algorithm sorts an unsigned byte table * * ($FF = 255) by ascending value. * * * * Stack top contains min and max indexes of the sub-table being sorted * * * * SIM68K.INI options should be : * * - BIOS = 0 or 1 * * - VAL_RAM=RANDOM * * - RAM_AD=$2000 to see table * * * ******************************************(C)1994-1998*Patrick DEMIRDJIAN*** * min and max indexes of main table to be sorted min equ 0 * $3F = MEMORY window size max equ $3f * Program start address org $1000 * Stack pointer init, IT masking and full speed mode setting lea $7ffe,a7 ori.w #$700,sr andi.w #$7fff,sr * A0 holds start address of table lea $2000,a0 * D0 holds min index move.l #min,d0 * D1 holds max index move.l #max,d1 * Q_SORT subroutine call bsr q_sort * End of program by pseudo monitor call trap #0 ***************************************************************************** Q_SORT equ * * Save min and max indexes in the stack move.w d0,-(a7) move.w d1,-(a7) * D2 = "middle" index = D0 + ((D1 - D0) / 2) = "pivot" index * Why is this formula better than (D1+D0)/2 ? move.w d1,d2 sub.w d0,d2 lsr.w #1,d2 add.w d0,d2 * D3 = table "pivot" element move.b 0(a0,d2.w),d3 * Search for table 1st element > pivot, starting from table top next1 equ * cmp.b 0(a0,d0.w),d3 bls next2 addq.w #1,d0 bra next1 * Search for table 1st element < pivot, starting from table bottom next2 equ * move.b 0(a0,d1.w),d4 cmp.b d3,d4 bls swap subq.w #1,d1 bra next2 swap equ * cmp.w d1,d0 bgt suite * Swap elements through D5 move.b 0(a0,d0.w),d5 move.b 0(a0,d1.w),0(a0,d0.w) move.b d5,0(a0,d1.w) * Refresh indexes addq.w #1,d0 subq.w #1,d1 cmp.w d1,d0 bgt suite bra next1 suite equ * cmp.w 2(a7),d1 ble next3 * Save current registers in stack move.w 2(a7),d6 move.w d0,-(a7) move.w d1,-(a7) move.w d6,d0 * Recursive call with new indexes * Sort sub-table bsr q_sort * Get current registers from stack move.w (a7)+,d1 move.w (a7)+,d0 next3 equ * cmp.w (a7),d0 bge fin * Save current registers in stack move.w (a7),d6 move.w d0,-(a7) move.w d1,-(a7) move.w d6,d1 * Recursive call with new indexes * Sort sub-table bsr q_sort * Get current registers from stack move.w (a7)+,d1 move.w (a7)+,d0 fin equ * * Remove indexes from stack adda.l #4,a7 rts * Suggestion_1 * Modify tests to sort signed bytes table ($FF = -1). * Display in D7 stack max size. * Suggestion_2 * Modify Q_SORT to sort word and long word tables. </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload