LB sort is unstable

[tsh73]

unstable as in

en.wikipedia.org/wiki/Sorting_algorithm#Stability


I know it always was this way

but I see benefits in  changing it to stable version

(so if it is already sorted by say first name, sorting by last name leave first names in order)


What do you think?


(actually a wish)

[Carl Gundel]

Hi,

You mean what, that sort order is not guaranteed when two or more identical sort key values exist?

Please provide a code example and output, and the desired output.

-Carl

[Rod]

I think Anatoly means that in multi column data that previous ordering is preserved. So we get all Smiths in order but also within that Smith A Smith B Smith C

Currently we get Smith but perhaps as C A B

We have code examples of concactenating columns prior to sorting. This provides a solution. But it would be really cool if we could pass Liberty a column list when asking for sort. So not sort start end column but sort start end column,column,column,[column]

this variable column list causes Liberty to concactenate on the fly and provide multi column sort.
Then we would get Smith A B C if we sort first name within surname perhaps column would look like 2,1

[Rod]

There is probably another way to "stabilise" the sorting of pre sorted data as Anatoly wishes, but multi column sort offers so much more.


dim db$(5,3)
db$(1,1)="Mike"
db$(1,2)="Smith"
db$(1,3)="Arizona"
db$(2,1)="James"
db$(2,2)="Smith"
db$(2,3)="Nebraska"
db$(3,1)="Tom"
db$(3,2)="Smith"
db$(3,3)="Scotland"
db$(4,1)="Mike"
db$(4,2)="Wilson"
db$(4,3)="Arizona"
db$(5,1)="John"
db$(5,2)="Davidson"
db$(5,3)="USA"

print "Normal Liberty sort"
sort db$(,1,5,2
gosub [showlist]
print "Normal Liberty sort again, note Smith's order changes"
sort db$(,1,5,2
gosub [showlist]
print "Now multi column sort"
call qsort 1,5,"2,1"
gosub [showlist]
print "Now multi column second time preserves order"
call qsort 1,5,"2,1"
gosub [showlist]
wait

[showlist]
for n= 1 to 5
   print db$(n,1),db$(n,2),db$(n,3)
next
return


sub qsort Start, Finish, order$
 'order$ is a comma delimited priority list of columns to sort on "2,1" "7" etc
 i = Start
 j = Finish
 dim temp$(numCol)

 'create the compare string
 r=int((i+j)/2)
 compa$=""
 o=1
 o$=word$(order$,o,",")
 while o$<>""
   compa$=compa$+db$(r,val(o$))
   o=o+1
   o$=word$(order$,o,",")
 wend
 while i <= j
     'create the string to compare against
     compb$=""
     o=1
     o$=word$(order$,o,",")
     while o$<>""
       compb$=compb$+db$(i,val(o$))
       o=o+1
       o$=word$(order$,o,",")
     wend
     while compb$ < compa$
       i = i + 1
       compb$=""
       o=1
       o$=word$(order$,o,",")
       while o$<>""
           compb$=compb$+db$(i,val(o$))
           o=o+1
           o$=word$(order$,o,",")
       wend
   wend
   'create the string to compare against
   compb$=""
   o=1
   o$=word$(order$,o,",")
   while o$<>""
       compb$=compb$+db$(j,val(o$))
       o=o+1
       o$=word$(order$,o,",")
   wend
   while compb$ > compa$
     j = j - 1
     compb$=""
     o=1
     o$=word$(order$,o,",")
     while o$<>""
       compb$=compb$+db$(j,val(o$))
       o=o+1
       o$=word$(order$,o,",")
     wend
   wend
   if i <= j then
       for p=0 to numCol
           temp$(p)=db$(i,p)
       next
       for p=0 to numCol
           dbf$(i,p)=db$(j,p)
       next
       for p=0 to numCol
           db$(j,p)=temp$(p)
       next
       i = i + 1
       j = j - 1
   end if
 wend
 if j > Start then call qsort Start, j,order$
 if i < Finish then call qsort i, Finish,order$
end sub









[cundo]

I understand that an "stabilized" Sort is like in music when you don't move the note between chord changes, when that note is in common and in the "right" position... So if an item doesn't need to be "SORTed", don't move it from its position.

[tsh73]

It was a year ago then "what algorithm Java uses to sort" was asked at me
(and I am not know Java at all)
So it happens that Java uses 2 different algorithms, one for primitives (where "stable" does not matter) and on for Objects
stackoverflow.com/questions/12228659/what-is-the-sorting-algorithm-for-java
from that page - link explaining as to *why*
stackoverflow.com/questions/15154158/why-collections-sort-uses-merge-sort-instead-of-quicksort/15154287#15154287
Very nice explanation I think.

With LB, 2d array sorted behaves as array of objects - single row as one object
So same reason apply.

So with new LB version, changing sort routine to stable breaks nothing - but gives something new/useful, mostly for free.