Lukas Jiriste [Tue, 5 Mar 2024 10:57:32 +0000 (11:57 +0100)]
Disable using LIS for very small input
When sorting lists smaller than 7 elements, the LIS
algorithm performes worse than the push-only one.
This is probably caused by additional rotations, that are
needed to isolate LIS in stack A.
Lukas Jiriste [Sat, 2 Mar 2024 11:59:54 +0000 (12:59 +0100)]
Fix the usage of lis
The lis was created in such a way, that the top may not have been
the first number of the stack that is part of the found lis.
This has been fixed by synchronously rotating lis and stack to the
initial rotation of stack.
Lukas Jiriste [Thu, 29 Feb 2024 16:25:47 +0000 (17:25 +0100)]
Implement detection of largest increasing subsequence
This lowers the number of operations needed for sorting.
We can leave an increasing subsequence inside A because
the sorting algorithm before this commit just builded
incresing sequence anyway.
Leaving a number in stack A costs just one rotate, while
pushing it to B costs at least an additional
push back to A plus probably a bunch of rotates over it
while trying to push other entries back to A.
Lukas Jiriste [Thu, 29 Feb 2024 09:29:12 +0000 (10:29 +0100)]
Change return type of stack_push from void
Previously the return type was void as handling any error was percieved
as too annoying and action_push must have been void anyway.
This change is done for future changes that may benefit from the
information of error, while the return value is ignored in the
functions that expect void.
Lukas Jiriste [Sat, 24 Feb 2024 10:18:02 +0000 (11:18 +0100)]
Fix "off by one" errors, fix find_target_ind
The function find_target_ind used (malfunctioning) binary search,
but that proved to be more difficult so I reimplemented it using
basic linear search.
Lukas Jiriste [Fri, 23 Feb 2024 09:36:57 +0000 (10:36 +0100)]
Implement a sorting algorithm
The idea is to push everything except for 3 elements from a to b.
Stack a can then be trivially sorted after which we can insert
(the cheapest) elements from b to the correct place in a.
The implementation needs to be refined as it does not actually sort.