base:quicksort_16-bit_elements
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
base:quicksort_16-bit_elements [2016-08-15 20:17] – litwr2 | base:quicksort_16-bit_elements [2020-10-20 18:53] (current) – a link added litwr2 | ||
---|---|---|---|
Line 1: | Line 1: | ||
====== Quicksort (for 16-bit Elements) ====== | ====== Quicksort (for 16-bit Elements) ====== | ||
- | by Vladimir Lidovski aka litwr, 13 Aug 2016 | + | by Vladimir Lidovski aka litwr, 13 Aug 2016 (with help of BigEd) |
- | It is well known that the best, the fastest sort routine is Quicksort. | + | It is well known that the best, the fastest sort routine is Quicksort. |
The next Pascal code was translated to 6502 assembler. | The next Pascal code was translated to 6502 assembler. | ||
Line 61: | Line 61: | ||
tya | tya | ||
adc i2hi | adc i2hi | ||
- | | + | |
sta zp1hi | sta zp1hi | ||
ror zp1lo | ror zp1lo | ||
Line 214: | Line 214: | ||
| |Insertion |21.4 |0.14 |39.75 |0.16 | | | |Insertion |21.4 |0.14 |39.75 |0.16 | | ||
| |Shell | | |Shell | ||
- | | |Quick | + | | |Quick |
^4096 Integers^Sort Type ^Random ^Ordered ^Reversed ^Zeros ^ | ^4096 Integers^Sort Type ^Random ^Ordered ^Reversed ^Zeros ^ | ||
| |Insertion |317.98 |0.6 |635.13 |0.58 | | | |Insertion |317.98 |0.6 |635.13 |0.58 | | ||
| |Shell | | |Shell | ||
- | | |Quick | + | | |Quick |
^12288 Integers^Sort Type ^Random ^Ordered ^Reversed ^Zeros ^ | ^12288 Integers^Sort Type ^Random ^Ordered ^Reversed ^Zeros ^ | ||
| |Insertion |2877.48|1.78 |5714.08|1.75 | | | |Insertion |2877.48|1.78 |5714.08|1.75 | | ||
| |Shell | | |Shell | ||
- | | |Quick | + | | |Quick |
//Random//, // | //Random//, // | ||
Line 231: | Line 231: | ||
This version of Quicksort requires almost all stack (about 240 bytes) to sort fast more than 32 KB of data. The required minimum is about 176 bytes but the stack with the only such minimum may slow down sorting dramatically. | This version of Quicksort requires almost all stack (about 240 bytes) to sort fast more than 32 KB of data. The required minimum is about 176 bytes but the stack with the only such minimum may slow down sorting dramatically. | ||
- | It is possible to reduce the stack load by the tail call optimization. It makes Quicksort slightly faster (only by 3-4%) but reduces the stack load more than 50%. So 128 free bytes in the stack will make the sort of 60 KB data without delays. | + | It is possible to reduce the stack load by tail call elimination. It makes Quicksort slightly faster (only by 3-4%) but reduces the stack load more than 50%. So 128 free bytes in the stack will make the sort of 60 KB data without delays. |
< | < | ||
+ | i2lo = zp0lo | ||
+ | i2hi = zp0hi | ||
+ | j2lo = zp2lo | ||
+ | j2hi = zp2hi | ||
+ | x_lo = m2lo | ||
+ | x_hi = m2hi | ||
+ | ublo = m3lo | ||
+ | ubhi = m3hi | ||
+ | lblo = m4lo | ||
+ | lbhi = m4hi | ||
+ | |||
quicksort0 | quicksort0 | ||
tsx | tsx | ||
cpx #16 ;stack limit | cpx #16 ;stack limit | ||
- | bcs qsok0 | + | bcs qsok |
qs_csp | qs_csp | ||
- | dex | ||
- | dex | ||
txs | txs | ||
Line 252: | Line 261: | ||
lda #<array | lda #<array | ||
sta lblo | sta lblo | ||
+ | tsx | ||
+ | stx qs_csp+1 | ||
qsok lda lblo | qsok lda lblo | ||
sta i2lo | sta i2lo | ||
Line 266: | Line 277: | ||
tya | tya | ||
adc i2hi | adc i2hi | ||
- | | + | |
sta zp1hi | sta zp1hi | ||
ror zp1lo | ror zp1lo | ||
Line 384: | Line 395: | ||
</ | </ | ||
- | The invocation should be in the next form. | + | The locations //m3hi//, //m3lo//, //m4hi//, //m4lo// maybe situated anywhere |
- | < | + | |
- | tsx | + | |
- | stx qs_csp+1 | + | |
- | jsr quicksort | + | |
- | </code> | + | |
- | It is required to put the proper constants after //quicksort// label. This makes the invocation code more complex | + | The other published 6502 Quicksort |
base/quicksort_16-bit_elements.txt · Last modified: 2020-10-20 18:53 by litwr2