LB Booster
Programming >> Liberty BASIC language >> Sort behavior
http://lbb.conforums.com/index.cgi?board=lblang&action=display&num=1432985772
Sort behavior
Post by Richard Russell on May 30th, 2015, 11:36am

One of the advantages of LBB over LB is that if you re-sort an already sorted list the record order will not change. The program below demonstrates the difference; if you run it in LB 4.04 it will (probably) report that the record order has changed after the sort, but when run in LBB it won't:

Code:
' Adapted from a program by Anatoly Sheyanov (tsh73)
randomize 0.5
N=15
dim a(N,2), r(N)

for i = 0 to N-1
    a(i,1)= int(i/5)
    a(i,2)= int(rnd(1)*5)
    r(i) = a(i,2)
next

print "by construction sorted by column #1"
for i = 0 to N-1
    print a(i,1), a(i,2)
next

sort a(), 0, N-1, 1
print

print "After re-sorting by column #1"
print "Check whether column #2 has changed"
for i = 0 to N-1
    print a(i,1), a(i,2),
    if i=0 then
        print
    else
        if  a(i,2) <> r(i) then print "order changed" else print
    end if
next

Note that neither LBB nor LB performs a stable sort (using the built-in SORT statement).

Richard.
Re: Sort behavior
Post by Hans on Jun 3rd, 2015, 07:22am

Richard,
please correct me if I am wrong:

I never ran it to this, but maybe it occurs at specific occasions

Regards, Hans
Re: Sort behavior
Post by Hans on Jun 3rd, 2015, 07:49am

I was first working thru your forum and after that the LB forum. So I missed the discussion there about sorting. The answer is there (and on Wikipedia): http://libertybasic.conforums.com/index.cgi?board=open&action=display&num=1432919349

It is not a matter of incorrect sorting, but what is done with the data part that is not object of the sorting.

Hans
Re: Sort behavior
Post by Richard Russell on Jun 3rd, 2015, 4:48pm

on Jun 3rd, 2015, 07:22am, Hans wrote:
not stable means the sequence of items can be altered running Sort a second time

No, that's something different. LBB's sort does guarantee that the order remains unchanged on a repeated sort, but it is not a stable sort.

Quote:
this means the sorting is not always 100% correct

Changing the order doesn't mean the sort is incorrect, so long as the items in the sorted column remain sorted. Both LB and LBB sorts are 'correct' - they do what they claim to do - but only LBB's is guaranteed to leave the order unchanged if the sort is repeated.

Quote:
one would better use something else to sort

If you need a stable sort then you would need to use an alternative method. But that is unusual - I don't think I've ever needed a stable sort.

Richard.