Author |
Topic: Sort behavior (Read 536 times) |
|
Richard Russell
Administrator
member is offline
 
Posts: 1348
|
 |
Sort behavior
« Thread started 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.
|
|
 Logged
|
|
|
|
Hans
New Member
member is offline
Gender: 
Posts: 31
|
|
Re: Sort behavior
« Reply #1 on: Jun 3rd, 2015, 07:22am » |
|
Richard,
please correct me if I am wrong:
not stable means the sequence of items can be altered running Sort a second time this means the sorting is not always 100% correctone would better use something else to sort
I never ran it to this, but maybe it occurs at specific occasions
Regards, Hans
|
|
Logged
|
|
|
|
Hans
New Member
member is offline
Gender:
Posts: 31
|
|
Re: Sort behavior
« Reply #2 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
|
|
Logged
|
|
|
|
Richard Russell
Administrator
member is offline
Posts: 1348
|
|
Re: Sort behavior
« Reply #3 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.
|
|
Logged
|
|
|
|
|
