summary |
shortlog | log |
commit |
commitdiff |
tree
first ⋅ prev ⋅ next
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 [Tue, 5 Mar 2024 09:47:39 +0000 (10:47 +0100)]
Refactor code to comply with the 42 Norm
Lukas Jiriste [Tue, 5 Mar 2024 08:41:51 +0000 (09:41 +0100)]
Make errors print to stderr instead of stdout
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 [Fri, 1 Mar 2024 11:43:41 +0000 (12:43 +0100)]
Merge branch 'correct' into trunk
This merge fixes the sort before inclusion of LIS.
Now all problems should be only within LIS.
Lukas Jiriste [Fri, 1 Mar 2024 11:02:09 +0000 (12:02 +0100)]
Fix a logic bug in final reverse rotation
Lukas Jiriste [Fri, 1 Mar 2024 09:22:59 +0000 (10:22 +0100)]
Adjust 42 header and header guards to new name
This is required by the 42 Norm.
Lukas Jiriste [Fri, 1 Mar 2024 09:08:20 +0000 (10:08 +0100)]
Rename checker.h to push_swap.h
The push_swap is the major part so it makes sense to have the header
bear its name.
Lukas Jiriste [Fri, 1 Mar 2024 09:01:33 +0000 (10:01 +0100)]
Bring source code to compliance with the 42 Norm
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 16:24:02 +0000 (17:24 +0100)]
Update libft for a fix of ft_vec
Lukas Jiriste [Thu, 29 Feb 2024 09:38:34 +0000 (10:38 +0100)]
Add subprojects' inc dir as compilation prerequisite
This forces make to download the subproject headers that are necessary
for compiling the source files to object files.
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 13:13:56 +0000 (14:13 +0100)]
Refactor push.c so as to conform with the Norm
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 11:25:52 +0000 (12:25 +0100)]
Use newline as an output separator instead of space
Lukas Jiriste [Fri, 23 Feb 2024 11:13:25 +0000 (12:13 +0100)]
Weaken the 3 or less sort and fix binary search
The a_sort_three_or_less function needs not to rotate,
as the a stack will be rotated many times during the insertion.
Lukas Jiriste [Fri, 23 Feb 2024 09:59:51 +0000 (10:59 +0100)]
Fix is_sorted so it does not change its argument.
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.
Lukas Jiriste [Fri, 23 Feb 2024 09:36:20 +0000 (10:36 +0100)]
Update Libft to gain access to ft_max and ft_min
Lukas Jiriste [Tue, 6 Feb 2024 13:55:32 +0000 (14:55 +0100)]
Refactor stack functions from checker.c
Lukas Jiriste [Tue, 6 Feb 2024 12:23:16 +0000 (13:23 +0100)]
Refactor dir structure and prog argument parsing
Lukas Jiriste [Wed, 24 Jan 2024 13:44:15 +0000 (14:44 +0100)]
Start the project, implement checker