Πέμπτη 14 Νοεμβρίου 2024

Revision 46, Version 12

 The last fault, for slice(), so ? (1,2,3)#slice(0,0) now print 1 (a slice from 0 item to 0 item)

Check this three routines for sorting. The two last have the same compares and swaps.




From my laptop (Windows 11):




form 80, 60
? $(,5)
Stack new {
\\ data push to end of stack (we use it as FIFO)
for i=1 to 200 : data random(-100, 100): next
ss=[]
? ss
? "----------------------------------"
M=Stack.Size-1
comp=0
nmove=0
s=stack(ss)
profiler
for cc=1 to 1 {
flush
stack ! stack(s)
M=Stack.Size-1
While M>0 {
N=1
For i=1 to M {
\\ if peek item i > peek item i+1 then get i+1 to top, and send to i
\\ stack is a linked list, so moving items done with pointers only
if stackitem(i)>=stackitem(i+1) then Shift i+1 : ShiftBack i : N=i : nmove++
comp++
}
M=N-1
}
}
pen 15{? round(timecount, 0)}
print array([])
print comp, nmove
}
global cswap=0
global compare=0


Group Quick {
Private:
      Function partition {
               Read &A(), p, r
               x = A(r): i = p-1
               For j=p to r-1 {If .LE(A(j), x) Then i++:Swap A(i),A(j):cswap++:compare++
               }
               Swap A(i+1),A(r): cswap++:=i+1
            }
Public:
      LE=Lambda (a, b)->a<=b
      Function quicksort {
           Read &A(), p, r
           If p < r Then {
             q = .partition(&A(), p, r)
             Call .quicksort(&A(), p, q - 1)
             Call .quicksort(&A(), q + 1, r)
          }
      }
}
dim a(), b()
a()=array(stack(ss))
b()=a()
profiler
for cc=1 to 1 {
a()=b()
Call Quick.QuickSort(&a(), 0, len(a())-1)
}
pen 15{? round(timecount, 0)}
? a()
? cswap, compare
Class Quick {
Private:
module quicksort (&a()) {
do If Stackitem()>=Stackitem(2) Then Drop 2:if empty then exit else continue
over 2,2
Read p, r : i = p-1 : x=a(r)
For j=p to r-1:If .LE(a(j), x) Then i++:Swap a(i),a(j): compare++:cswap++
Next j : Swap a(i+1), a(r) : Push i+2, i:shift 3 : cswap++
always
}
Public:
// a and b can be strings or numbers
LE=Lambda (a, b)->a<=b
// this is final, we can't change it
Function Final Sort(&a(), a_min, a_max){
stack new {
.quicksort &a(), a_min, a_max
}
}
}
cswap<=0
compare<=0


Q=Quick()
a()=array(stack(ss))
b()=a()
profiler
for cc=1 to 1 {
a()=b()
Call Q.Sort(&a(), 0, len(a())-1)
}
pen 15{? round(timecount, 0)}
? a()
? cswap, compare


Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου

You can feel free to write any suggestion, or idea on the subject.