Κυριακή, 22 Ιουλίου 2018

One QuickSort for Strings and Numeric values, and data in arrays, with no Recursion.

This code is optimized. Run without recursion (use stack for values, which use heap to expand)

Flush
Class Quick {
Private:
partition=lambda-> {
Read &A(), 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)
} : Swap A(i+1), A(r) : Push i+2, i
}
Public:
LE=Lambda->Number<=Number
Module ForStrings {
.partition<=lambda-> {
Read &A\$(), p, r : i = p-1 : x\$=A\$(r)
For j=p to r-1 {If A\$(j)<= x\$ Then i++:Swap A\$(i),A\$(j)
} : Swap A\$(i+1), A\$(r) : Push i+2, i
}
}
Function quicksort {
{If Stackitem() >= Stackitem(2) Then Drop 2 : if empty then {Break} else Restart
over 2,2 : call .partition(ref\$) :shift 3 : Restart}
}
}
Quick=Quick()
Dim A(10)<<Random(50, 100)
rem : A(0):=57, 83, 74, 98, 51, 73, 85, 76, 65, 92
Print A()
Call Quick.quicksort(&A(), 0, Len(A())-1)
Print A()
Quick=Quick()
Function join\$(a\$()) {
n=each(a\$(), 1, -2)
k\$=""
while n {
overwrite k\$, ".", n^:=array\$(n)
}
=k\$
}
Stack New {
Data "1.3.6.1.4.1.11.2.17.19.3.4.0.4" , "1.3.6.1.4.1.11.2.17.19.3.4.0.1", "1.3.6.1.4.1.11150.3.4.0.1"
Data "1.3.6.1.4.1.11.2.17.19.3.4.0.10", "1.3.6.1.4.1.11.2.17.5.2.0.79", "1.3.6.1.4.1.11150.3.4.0"
Dim Base 0, arr(Stack.Size)
i=0 : While not Empty {let arr(i)=piece\$(letter\$+".", ".") : i++ }
}
\\ change compare function
Quick.LE=lambda (a, b)->{
Link a, b to a\$(), b\$()
def i=-1
do {
i++
} until a\$(i)="" or b\$(i)="" or a\$(i)<>b\$(i)
if b\$(i)="" then =a\$(i)="":exit
if a\$(i)="" then =true:exit
=val(a\$(i))<=val(b\$(i))
}
Call Quick.quicksort(&arr(), 0, Len(arr())-1)
For i=0 to len(arr())-1 {
Print join\$(arr(i))
}
Quick=Quick()
Quick.ForStrings
Dim A\$()
A\$()=("one","two", "three","four", "five")
Print A\$()
Call Quick.quicksort(&A\$(), 0, Len(A\$())-1)
Print A\$()