OpenEuphoria

2. Re: Natural sort comparison

• Posted by _tom (admin) Jul 20, 2017
• 2316 views

I have been thinking of this stuff as Mike Sort (with obvious inference to some competitive sorting algorithm). Since I didn't invent it I wait for input.

• data: integer|atom|string|object
• stability: TRUE|FALSE
• direction: UP|DN
• order: arithmetic|natural|custom
• column: 0|1|2|...
• index sorting

The API question is:

• a universal sort with five (or more) arguments
• sort with the most "popular" arguments
• lots of specialized sort routines with minimal argument lists

This is a teaching opportunity to show me how to design a library. Time to hear from Pete about what he expects in a sorting library.

The algorithm only takes into account "unbroken" integers within the 
character strings  
it makes no allowance for decimal points (although it 
will still work correctly as long as there are an equal number of digits 
to the right of the decimal point in each number being compared). 

I have not thought about unicode and case sensitivity (monocasting; seems like an ugly word) variations in a custom sort.

In the pastey I left out a second sorting algo that is optimized for objects that are only string sequences--making it about twice as fast. In the original he also uses custom_sort(ID) as a way of executing the sorting.

Since using routine_id is expensive, is it worth writing the sorting comparison directly into the sorting algorithm?

_tom

4. Re: Natural sort comparison

• Posted by petelomax Jul 21, 2017
• 2304 views

My preferred sort API might be (this is all draft, there may be niggles)

    sequence res = sort(sequence s, sequence options={}) 

where s is the data to be sorted and options is an even-length sequence with odd elements being recognised literal strings and even elements actual settings, eg

    ?sort(s,{"direction",-1,"compare",routine_id("my_compare")}) 

The available options would include at least:

As noted by Mike, "preproc" could be significantly more efficient than "compare"; it would be an error to have both.
In fact we might drop "compare" and only offer "preproc", and I now think we should.

This interface could/should effectively make custom_sort obsolete (albeit fiddly to convert compare->preproc).

I would use -2 to indicate "preproc not set", rather than -1 which could conflict with/hide errors from routine_id failures.

A preproc/retset element of 0 means "index".

I would also make it thread-safe, meaning you cannot have the file-level SortType/Column/Keys/CompareRtn.

The innards might look a bit like this:

 
    keys = s 
    if preproc!=-2 then 
        for i=1 to length(keys) do 
            if integer(preproc) then 
                keys[i] = call_func(preproc,{i,keys[i]}) 
            else 
                keys[i] = get_columns(keys[i],i,preproc) 
            end if 
        end for 
    end if 
    keys = actual_sort(keys) 
    if retset!=-2 then 
        for i=1 to length(keys) do 
            keys[i] = get_columns(keys[i],i,retset) 
        end for 
    end if 
    return keys     -- **NB** 

Note that if [parts of] the original s need to be returned, preproc must include them in keys, and "return" specified to extract them from and throw away the other working storage that formed part of keys[i].

A stable sort could be achieved by incorporating the index into keys.

I haven't attempted any of this at all, just a few ideas.

Pete

6. Re: Natural sort comparison

• Posted by petelomax Jul 21, 2017
• 2298 views

The algorithm only takes into account "unbroken" integers within the 
character strings  
it makes no allowance for decimal points (although it 
will still work correctly as long as there are an equal number of digits 
to the right of the decimal point in each number being compared). 

You're gonna hate me: http://rosettacode.org/wiki/Natural_sorting#Phix

It might need enhancing for the 1.009 vs 1.1 case, with some prev='.' tests or similar

Pete

8. Re: Natural sort comparison

• Posted by _tom (admin) Jul 21, 2017
• 2284 views

The algorithm only takes into account "unbroken" integers within the 
character strings  
it makes no allowance for decimal points (although it 
will still work correctly as long as there are an equal number of digits 
to the right of the decimal point in each number being compared). 

You use a syntax trick in Phix; no cut and paste for OE.

A ligature is "two characters combined into one."

hence o and e becomes œ

_tom

10. Re: Natural sort comparison

• Posted by petelomax Aug 11, 2017
• 2158 views

I found a way to improve quick_sort for the all-1s case, along with a minor speedup for the swap:

function quick_sort(sequence s) 
sequence qstack 
integer first, last, stackptr, I, J 
--object tmp, pivot 
object pivot, ti, tj 
 
    qstack = repeat(0,floor((length(s)/5)+10))    -- create a stack 
 
    first = 1 
    last = length(s) 
    stackptr = 0 
    while 1 do 
        while first<last do 
--maybe?: 
--          if last-first<=100 then 
--              s[first..last] = insertion_sort(s[first..last]) 
--              exit 
--          end if 
            pivot = s[floor((last+first)/2)] 
            I = first 
            J = last 
            while 1 do 
--              while s[I]<pivot do 
                while 1 do 
                    ti = s[I] 
                    if ti>=pivot then exit end if 
                    I += 1 
                end while 
--              while s[J]>pivot do 
                while 1 do 
                    tj = s[J] 
                    if tj<=pivot then exit end if 
                    J -= 1 
                end while 
                if I>J then exit end if 
                if I<J then 
                    -- added 6/8/17: 
                    if ti=tj then 
                        {I,J} = {J+1,I-1} 
                        exit 
                    end if 
--                  tmp = s[I] 
--                  s[I] = s[J] 
--                  s[J] = tmp 
                    s[I] = tj 
                    s[J] = ti 
                end if 
                I += 1 
                J -= 1 
                if I>J then exit end if 
            end while 
            if I<last then 
                qstack[stackptr+1] = I 
                qstack[stackptr+2] = last 
                stackptr += 2 
            end if 
            last = J 
        end while 
        if stackptr=0 then exit end if 
        stackptr -= 2 
        first = qstack[stackptr+1] 
        last = qstack[stackptr+2] 
    end while 
    return s 
end function 

Which makes it the clear winner across the board in my "Compare_sorting_algorithms.exw".

Given the performance boost that qstack gives to quick_sort, I wonder whether a similar technique could be applied to merge_sort, likewise turning it from a recursive algorithm to an iterative one, and whether merges could be performed in-situ. I jotted down some outline thoughts:

A stack of length log2 might be enough? Or even ceil(log2(n))-6 if we farm out length<=64 to insertion_sort.

Consider the merge operation of merge_sort, being performed in-situ.
(Note that <done> may in fact be a segment awaiting a future merge with merge(A,B))

xxxxxx,a1,a2,a3,a4,a5,b1,b2,b3,b4,b5 
<done> <----- A ----> <----- B ----> 

Now, if we pick a1, then all that happens is that A shrinks. A' and B remain sorted.
If we pick b1, then a1 must move into that slot. At this stage the rest of B remains sorted, whereas A becomes (not for long) a still-sorted-but-now-circular list.

At some point, however, the circular list aspect of A breaks down (assuming we would rather not physically re-order it), eg:

xxxxx,b1,b2,b3,a4,a5,a1,a2,a3,b4,b5 
<--- done ---> <----- A ----> <-B-> 

(pick a1)

xxxxx,b1,b2,b3,a1,a5,a4,a2,a3,b4,b5 
<----- done ----> <--- A ---> <-B-> 

The obvious solution is to maintain A as a linked list, which can be done using a parallel sequence links, initially the same size as the sequence x being sorted.
There may be opportunities to preset that links sequence during some prior merge operation (but probably not if we palm off short sequences to insertion_sort) - then again maintaining it for the B is pointless.

Lastly, if the merge terminates because A became empty, then any remainder of B is already in place, whereas if B becomes empty, then A must be reordered, using the same linked list, obviously with null-ops for any head(A)==A[1].

Pete

12. Re: Natural sort comparison

• Posted by petelomax Aug 14, 2017
• 2005 views

Here it is

enum SPLIT, MERGE 
 
function pihism_sort(sequence x) 
-- 
-- Pete's Iterative Half-In-Situ Merge Sort. 
-- 
integer first = 1, mid, last = length(x), adx, 
        op = SPLIT,  
        qslen = 2*ceil(log(last)/log(2)+1), 
        qdx=0 
sequence qsop = repeat(0,qslen), 
         qsf = repeat(0,qslen), 
         qsm = repeat(0,qslen), 
         qsl = repeat(0,qslen), 
         a 
object ai, xmid 
 
    while 1 do  -- until qstack is empty 
 
        if op=SPLIT then 
            -- 
            -- just push further split/merge pair(s) onto the stack... 
            -- 
            while first<last do 
                mid = floor((first+last)/2) 
                qdx += 1  
                qsop[qdx] = MERGE 
                qsf[qdx] = first 
                qsm[qdx] = mid 
                qsl[qdx] = last 
                if mid+1<last then 
                    qdx += 1 
                    qsop[qdx] = SPLIT 
                    qsf[qdx] = mid+1 
                    qsl[qdx] = last 
                end if 
                if first=mid then exit end if 
                last = mid 
            end while 
 
        else -- op=MERGE                             
            -- 
            -- first, leave any parts of the first half already in place. 
            -- 
            mid += 1 
            xmid = x[mid] 
            while first<mid and x[first]<=xmid do 
                first += 1 
            end while 
            -- 
            -- then merge until the first half is empty. 
            -- any remainder of the second half will already be in place. 
            -- 
            if first<mid then 
                a = x[first..mid-1] 
                ai = a[1] 
                adx = 1 
                while 1 do 
                    if mid>last 
                    or compare(ai,xmid)<=0 then 
                        x[first] = ai 
                        first += 1 
                        adx += 1 
                        if adx>length(a) then exit end if 
                        ai = a[adx] 
                    else 
                        x[first] = xmid 
                        first += 1 
                        mid += 1 
                        if mid<=last then 
                            xmid = x[mid] 
                        end if 
                    end if 
                end while 
            end if 
        end if 
        if qdx=0 then exit end if 
        op = qsop[qdx] 
        first = qsf[qdx] 
        mid = qsm[qdx] 
        last = qsl[qdx] 
        qdx -= 1 
    end while 
    return x 
end function 
 
sequence s,r,t 
for i=1 to 100 do 
--for i=1 to 1000000 by 10000 do  -- slow! 
--?i 
    t = tagset(i) 
    s = pihism_sort(t) 
    if s!=t then ?9/0 end if 
    s = reverse(t) 
    r = pihism_sort(s) 
    if r!=t then ?9/0 end if 
    s = shuffle(t) 
    r = pihism_sort(s) 
    if r!=t then ?9/0 end if 
end for 
 
constant LIM = 1000000-0 
t = shuffle(tagset(LIM)) 
atom t0 = time() 
s = pihism_sort(t) 
atom t1 = time() 
r = sort(t) 
atom t2 = time() 
?{t1-t0,":",t2-t1} 
     
?"ok" 
{} = wait_key() 

and the medals awarded are:

                  ones    sorted  random  reverse 
  pihism_sort      gold    gold    silver  bronze 
  quick_sort       silver  silver  gold    gold 
  builtin_sort     bronze  bronze  bronze  silver 

Not much in it though. I'm very pleased with that result.

Pete

PS: I tested this, integer-only, on RDS Eu/OpenEuphoria, and can post that version (f06.exw) if required.

PPS: Obviously 100% in-situ with a doubly-linked list was a completely insane idea, but 50% works well.