[SOLVED] Weird Sorting
lazarus / 21-General

----------------------------------------------------------------------
J-G · 2021-02-21 18:42

I haven't needed to ask advice for quite some time since I've been
doing 'other things'  but  today I needed to make a small adjustment
to my accounts program which has been running since 2016 without a
hitch.

The issue was that I omitted to register a transaction in February
2020 and there have been many transactions to that file since then so
I determined that I could just record it now and then [Sort] the
database - a simple enough process one would have thought.

I hadn't bothered to write the sort routine originally since there are
only three transactions per month and they are taken from a bank
statement and missing one out is unlikely.

The transactions are very simple - a date, a value and a reference -
The Reference is either 0,1 or 2, the Value is a variable and the date
is entered via a TdateEdit. The earliest transaction is 7-Apr-2016
(43468) and the last 5-Feb-21 (44232) but after [Sorting] the list
starts at 7-Dec-18 (43441) and counts down to 7-Apr-16 (42467) which
is followed by 5-Feb-21 (44232) then proceeding to 3-Jan-19 (43468). 
This is a 'reverse order' sort but in the normal 'forward order' it
has the same [Jump] going from 5-Feb-21 to 7-Apr-16

I have checked the 'day number' and they are perfectly 'normal'.

This is a very simple [Sort] :-
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i procedure
SortPension;Var  i,j,n,D1,D2 : word;  Temp : PEN;   procedure Swop; 
begin    Temp             := PensionList[i];    PensionList[i]   :=
PensionList[i-1];    PensionList[i-1] := Temp;  end; begin  n :=
PenCount;  Form1.SortPensionBtn.Caption:= InttoStr(n);   repeat    j
:= 0;    for i := 1 to n do      begin        D1 :=
LongWordDate(PensionList[i-1].Paid);        D2 :=
LongWordDate(PensionList[i].Paid);         if D1 > D2 then         
begin            swop;            j := i;          end;      end;    n
:= j;  until n = 0;  Form1.SortPensionBtn.Caption:= 'Done'; end; 
...and is identical in form to other data-types - just the variable
names are changed -  (i.e. Banking, Purchase Orders) which all work as
expected.

As the subject indicates - Weird!

Can anyone suggest a possible cause?   -  Oh - and a solution?

----------------------------------------------------------------------
bytebites · 2021-02-21 19:15

Would be easier to find solution with compilable code and not use time
to reconstruct the problem.

----------------------------------------------------------------------
J-G · 2021-02-21 20:47

Quote from: bytebites on February 21, 2021, 08:15:09 pmWould be easier
to find solution with compilable code and not use time to reconstruct
the problem.
I don't doubt that one bit, but my program runs to 17500+ lines plus a
specialist 'Unit'.

In addition the data, although not particularly sensitive is personal
and stripping out some part of the code would be a mammoth task which
is beyond my wit at the moment.

The report that is generated does the job intended but I would prefer
to have the underlying database correctly sorted in case there may be
some issue in the future. I'm sure I could separate out each 'year'
and re-build the database that way but I would also like to determine
how the - very basic - sorting routine fails in such a way.

----------------------------------------------------------------------
Blaazen · 2021-02-21 21:14

Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i begin  n :=
PenCount;  Form1.SortPensionBtn.Caption:= InttoStr(n);   repeat    j
:= 0;    for i := 1 to n do      begin        D1 :=
LongWordDate(PensionList[i-1].Paid);        D2 :=
LongWordDate(PensionList[i].Paid);
IMO the inner loop should be
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i     for i
:= 1 to n-1 doWhen n is count then valid elements are from 0 to n-1,
accessing n-th item should raise RangeCheckError.

----------------------------------------------------------------------
ASBzone · 2021-02-21 21:59

Quote from: J-G on February 21, 2021, 07:42:19 pmThe transactions are
very simple - a date, a value and a reference - The Reference is
either 0,1 or 2, the Value is a variable and the date is entered via a
TdateEdit. The earliest transaction is 7-Apr-2016 (43468) and the last
5-Feb-21 (44232) but after [Sorting] the list starts at 7-Dec-18
(43441) and counts down to 7-Apr-16 (42467) which is followed by
5-Feb-21 (44232) then proceeding to 3-Jan-19 (43468).  This is a
'reverse order' sort but in the normal 'forward order' it has the same
[Jump] going from 5-Feb-21 to 7-Apr-16
...
Can anyone suggest a possible cause?   -  Oh - and a solution?

If you are going to sort on the date using its visual representation,
then yyyy-mm-dd will allow you to easily sort chronologically.  If you
are using the visual representation, and something other than year is
the first item, then your sorting will have to be more
sophisticated...

----------------------------------------------------------------------
Blaazen · 2021-02-21 22:09

Those numbers are numbers of days from 1900.

----------------------------------------------------------------------
AL · 2021-02-21 22:40

Seems your sorting is not complete.
Most examples uses 2 for loops to go through the array
For example:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i Procedure
BubbleSort(numbers : Array of Integer; size : Integer);Var        i,
j, temp : Integer; Begin        For i := size-1 DownTo 1 do          
    For j := 2 to i do                        If (numbers[j-1] >
numbers[j]) Then                        Begin                        
      temp := numbers[j-1];                               
numbers[j-1] := numbers[j];                                numbers[j]
:= temp;                        End; End.

----------------------------------------------------------------------
J-G · 2021-02-22 09:48

Quote from: ASBzone on February 21, 2021, 10:59:23 pmIf you are going
to sort on the date using its visual representation, then yyyy-mm-dd
will allow you to easily sort chronologically...
That is exactly what I thought and why I wrote the function
'LongWordDate' :-
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i function
 LongWordDate(D : date) : LongWord;begin  Result :=
D.Y*10000+D.M*100+D.D;end; (I wrote this function way back in 2015 ish
when I created my [Date] Unit)

Which turns my 'Date' type :-
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i Type  date
= record                // 4 bytes           d,m : byte;           y 
: word;         End; into a LongWord = yyyymmdd ..  ie.  12/10/2020 
 becomes 20201012  which ......  (thinks........)

D'oh!!
sometimes, just trying to explain a problem to someone else, turns a
light-bulb on...

I'd declared D1 & D2 as 'word' rather than 'LongWord' 

I haven't tested the new declaration yet but suspect that I may have
solved it.

Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i Var  i,j,n
: word;  D1,D2 : longword;  Temp  : PEN;

----------------------------------------------------------------------
avk · 2021-02-22 09:55

Wow, BubbleSort in production.

Quote from: AL on February 21, 2021, 11:40:27 pmSeems your sorting is
not complete.
Most examples uses 2 for loops to go through the array
For example:
...
No, this is an advanced version of bubble sort that is somewhat
adaptive. On a sorted array, it will work in O(n) time, whereas your
sorting is always O(n^2). Only it is a little wrongly implemented. As
Blaazen rightly pointed out, if an array is zero-based,
then it must end with Count-1. And I believe that it is desirable to
avoid unsigned types in Pascal loop counters.
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i procedure
SortPension;Var  i,j,n: LongInt;  D1,D2 : word;  Temp : PEN;  
procedure Swop;  begin    Temp             := PensionList[i];   
PensionList[i]   := PensionList[i-1];    PensionList[i-1] := Temp; 
end; begin  n := PenCount-1;  Form1.SortPensionBtn.Caption:=
InttoStr(n);   repeat    j := 0;    for i := 1 to n do      begin    
  D1 := LongWordDate(PensionList[i-1].Paid);        D2 :=
LongWordDate(PensionList[i].Paid);         if D1 > D2 then         
begin            swop;            j := i-1;          end;      end;  
n := j;  until n = 0;  Form1.SortPensionBtn.Caption:= 'Done'; end; A
small nuance:  j := i-1; This of course will not have a significant
impact on performance, but still...
And of course all this will only work if the comparisons are correct.

----------------------------------------------------------------------
J-G · 2021-02-22 10:12

Just re-compiled and run the sort again - PERFECT !

I'd copied the declaration - in fact the whole procedure - from
another routine which in fact wasn't using the date to sort on (so the
D1,D2 declarations in that procedure were superfluous) and just
changed the variable names.

I ought to have realized that the behaviour was typical of a 'Roll-
Over' where the variable size exceeded the declared type 

I'm seldom concerned over efficiency - the time it takes to sort an
array of this size is less than the blink of an eye - and much prefer
to re-use existing code even though there may have been improvements
over time.