Differences

This shows you the differences between two versions of the page.

--- base:quicksort_16-bit_elements [2016-08-16 10:45] – 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) ======
-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 very odd that it is not implemented for 6502 for all of 42 years, from 1975 to 2016.  The main problem is in the stack depending nature of Quicksort and the stack limit of 256 bytes of 6502 architecture.  It is solvable.
+It is well known that the best, the fastest sort routine is Quicksort.  It is very odd that its implementations for 6502 for all of 42 years (from 1975 to 2016) have a bit blurred and unofficial status.  The main problem is in the stack depending nature of Quicksort and the stack limit of 256 bytes of 6502 architecture.  It is solvable.
 The next Pascal code was translated to 6502 assembler.
@@ Line 61: / Line 61: @@
           tya
           adc i2hi
-          lsr
+          ror
           sta zp1hi
           ror zp1lo
@@ Line 251: / Line 251: @@
 qs_csp    ldx #0
-          dex
-          dex
           txs
@@ Line 263: / Line 261: @@
           lda #<array
           sta lblo
+          tsx
+          stx qs_csp+1
 qsok      lda lblo
           sta i2lo
@@ Line 277: / Line 277: @@
           tya
           adc i2hi
-          lsr
+          ror
           sta zp1hi
           ror zp1lo
@@ Line 395: / Line 395: @@
 </code>
-The locations //m3hi//, //m3lo//, //m4hi//, //m4lo// maybe situated anywhere in RAM.  The invocation should be in the next form.
+The locations //m3hi//, //m3lo//, //m4hi//, //m4lo// maybe situated anywhere in RAM.  The invocation just a call to quicksort routine.  However it is required to put the proper constants after //quicksort// label.  This makes the invocation code more complex in the general case.
-<code>
-          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 in the general case.
+The other published 6502 Quicksort is at [[http://www.vcfed.org/forum/showthread.php?4687-QuickSort-in-6502-assembler|Vintage Computer Federation]]. More information can be found on page [[https://github.com/litwr2/6502-sorting|6502 sorting]]