Κυριακή, 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 {
           Read ref$
           {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))
}
\\ Fresh load
Quick=Quick()
Quick.ForStrings
Dim A$()
A$()=("one","two", "three","four", "five")
Print A$()
Call Quick.quicksort(&A$(), 0, Len(A$())-1)
Print A$()




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

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