Codebase64 wiki

User Tools

Site Tools

Trace:
base:quicksort_16-bit_elements

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
Next revisionBoth sides next revision
base:quicksort_16-bit_elements [2016-08-15 20:28] – litwr2base:quicksort_16-bit_elements [2016-08-18 12:19] – 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 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 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.
Line 214: Line 215:
 | |Insertion |21.4 |0.14 |39.75 |0.16 | | |Insertion |21.4 |0.14 |39.75 |0.16 |
 | |Shell     |1.75 |0.8  |1.12  |0.82 | | |Shell     |1.75 |0.8  |1.12  |0.82 |
-| |Quick     |0.75 |0.4  |0.43  |0.9  |+| |Quick     |0.75 |0.4  |0.47  |0.94  |
  
 ^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     |8.12   |4.02 |5.25   |4    | | |Shell     |8.12   |4.02 |5.25   |4    |
-| |Quick     |3.63   |1.85 |2.02   |4.13 |+| |Quick     |3.67   |1.88 |2.04   |4.21 |
  
 ^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     |30.18  |13.82|18.05  |13.81| | |Shell     |30.18  |13.82|18.05  |13.81|
-| |Quick     |11.67  |6.78 |7.28   |12.93|+| |Quick     |11.74  |6.83 |7.33   |13.07|
 //Random//, //Ordered//, //Reversed//, //Zeros// mean the type of array filling.  Random filling just copies ROM content into array.  Ordered filling uses numbers from 0 with step 1.  Reversed filling uses numbers from $ffff with step -1.  Zeros filling is just an array filled with the zeros only. //Random//, //Ordered//, //Reversed//, //Zeros// mean the type of array filling.  Random filling just copies ROM content into array.  Ordered filling uses numbers from 0 with step 1.  Reversed filling uses numbers from $ffff with step -1.  Zeros filling is just an array filled with the zeros only.
  
base/quicksort_16-bit_elements.txt · Last modified: 2020-10-20 18:53 by litwr2