This project has been created as part of the 42 curriculum by ppalamio, kjurkows

All functions are written in C and compiled with cc using the flags -Wall -Wextra -Werror.
All functions are written in accordance with the The Norme coding style.
Everything is documented using doxygen.

Description

push_swap is a program that implements 3 different sorting algorithms by using a set of instruction utilized on the stack.

This project is using libft extra written by kjurkows.

Program flow

The program flow is as follows:

stateDiagram-v2
   [*] --> PARSER : parse the input arguments
   PARSER --> DISORDER : analyze the disorder of the stack
   DISORDER --> ALGORITHM : select the best algorithm based on the disorder
   ALGORITHM --> BENCH : execute the algorithm and benchmark the sorting process
   BENCH --> [*] : print the benchmark results

Loading

Bonus

The bonus part of the project is a program called checker that checks if the stack is sorted after executing a series of operations.

It is a simple checker program that reads a list of operations from standard input and applies them to the stack. After all operations are applied, it checks if the stack is sorted in ascending order.

Instructions

Compilation

The project is compiled as multiple modules, with the main program being push_swap.

To compile push_swap, you can use the provided Makefile. Run the following command in your terminal:

make

Bonus

make bonus

Makefile Targets

Target	Description
all	Compiles the push_swap program
bonus	Compiles the checker program
clean	Removes object files
fclean	Removes object files and the push_swap program
re	Cleans and re-compiles the project
debug	Compiles the push_swap program with debug flags enabled
debug-bonus	Compiles the checker program with debug flags enabled
libft	Compiles the libft library
mod[name]	Compiles a specific module (e.g., make modPARSER)

Usage

push_swap accepts 3 types of parameters:

./push_swap --{algorithm} --bench "{stack}"

Mandatory arguments

"{stack}"

The {stack} is an unique list of integers separated by space. It can be declared with or without quotes.

They can be passed as multiple arguments, like this:

./push_swap 1 2 3 4 5

Or as a single argument, like this:

./push_swap "1 2 3 4 5"

If the stack contains a duplicate integer, push_swap will exit and print "Error" to stderr.

Optional arguments

--{algorithm}

By default push_swap will use an adaptive algorithm to sort the stack. However, you can specify a different algorithm by using the --{algorithm} option.

Possible values for {algorithm} are:

Options	Description
simple	sort the stack by using a simple algorithm
medium	sort the stack by using a medium algorithm
complex	sort the stack by using a complex algorithm
adaptive	sort the stack by using a adaptive algorithm (default)

--bench

Benchmark mode is also available by using the --bench option. It will print a summary of the sorting process to stderr.

Example usage:

./push_swap -100 45 -28 -69 200

./push_swap --complex "5 4 3 2 1"

./push_swap --bench "4 -3 -5 -6 -2"

./push_swap --simple 42 21 -128 --bench

Bonus

To use the bonus checker program, you can run it as follows:

./push_swap "{stack}" | ./checker "{stack}"

Remember that the {stack} must be the same for both programs, otherwise the result will be incorrect.

Other usage examples:

ARG=$(shuf -i 0-9999 -n {count}); ./push_swap $ARG | ./checker $ARG

Resources

• Google
• Wikipedia
• man pages

AI usage

Note

No code was generated by AI, and no code was copied from any AI source. The AI was used only for research purposes.

Gemini & Google AI Overviews

Gemini and Google AI Overviews were used to find, research and help understand different sorting algorithms and their complexities.

Gemini was also used as an aid while implementing the algorithms, when wikipedia didn't provide sufficient information about the algorithm.

Algorithms

Before all algorithms are executed, the stack is analyzed to determine the best algorithm to use based on the disorder of the stack.

The stack is also normalized, so that the algorithms can work with normal values instead of raw values. (0 = smallest, n-1 = largest)

small_sort

The small sort is algorithm for sorting up to 3 elements in A. It is used when A has no more than 3 elements.

It always sorts a stack of 2 elements in 1 move (or 0 moves if already sorted) and a stack of 3 elements in at most 2 moves (or 0 moves if already sorted).

It does not use stack B at all.

Simple algorithm ($\textbf O(n^2)$) [$disorder\lt0.2$]

Selected algorithm: Min/Max Selection Sort

While A has more than 3 elements:

1. Find the position of the element whose value equals the target (starting at 0).
2. Rotate it to the top of A using cheaper operations:
   • ra if it's in the first half of the stack
   • rra if it's in the second half
3. Push it to B with pb - each operation places the next-smallest value on top of B.
4. Increment the target.

small_sort is used at the end of this loop to pick the most optimized operations.

The last step is draining B onto A which completes this sorting algorithm.

Medium algorithm ($\textbf O(n \sqrt n)$) [$0.2\le disorder\lt0.5$]

Selected algorithm: range-based Bucket sort

The algorithm works by splitting the stack B into multiple ranges (or buckets) of values, and then pushing them back to A in the correct order.

Basically it calculates window size based on the size of the stack, and then pushes all elements in A that are in the current range to B. Then it pushes them back to A in the correct order.

Additionally, it uses small_sort to sort the remaining 3 elements in A at the end of phase 1.

Phase 1

$A \to B$

If the top element of A is in the current range, it will be pushed to B. If not, it will be rotated to the bottom of A.

Repeat this process until all elements in A that are in the current range are pushed to B.

Then the range is updated to the next range, and the process is repeated until all elements in A are pushed to B.

Phase 2

$B \to A$

Elements in B are pushed back to A in the correct order:

• Find the last remaining range in B (the range with the largest values).
• Find the largest element in B that is in the current range.
• Rotate B to bring the largest element to the top of B.
• Push the largest element from B to A.

Repeat this process until all elements in B are pushed back to A.

Complex algorithm ($\textbf O (n\log n)$) [$disorder\ge0.5$]

Selected algorithm: Turk

The algorithm is based on the Turk sorting algorithm for push_swap made by another 42 student.

It has been slightly modified to fit the requirements of this project, and to improve its performance.

It works in 2 simple phases:

1. Push to B
2. Push back to A

Basically before any move it calculates the best move to make based on cost calculation and analysis.

It works under a few assumptions for each phase...

If less than 3 elements are in A it will sort them with a special small_sort algorithm.

small_sort

If the input has at most 3 elements phase 1 and phase 2 will not be executed, and the small sort will be used instead.

Small sort is always used at the end of phase 1 to sort the remaining 3 elements in A.

It always sorts a stack of 2 elements in 1 move (or 0 moves if already sorted) and a stack of 3 elements in at most 2 moves (or 0 moves if already sorted).

It does not use stack B at all.

Cost calculation

First the basic fact is: 'You never need more than $size/2$ moves to bring any element to the top of the stack'.

The cost of moving an element to the top of the stack is calculated as follows:

• If the element is in the first half of the stack, the cost is equal to its index in the stack.
• If the element is in the second half of the stack, the cost is equal to the size of the stack minus its index.

Then to optimize the moves, the algorithm checks if the element in A and the element in B can be moved together with a single rotation. If so, it calculates the cost of moving both elements together and compares it to the cost of moving them separately. (using rr or rrr instead of ra and rra or rb and rrb)

Phase 1

Assumptions:

• A is unsorted
• B is empty
• A has more than 3 elements
• B is in descending order

Note

This phase will only run if A has more than 3 elements and be repeated until A has exactly 3 elements left.

Before this phase at most 2 elements are pushed to B to make sure that B is in descending order and not empty.

Then every push to be will ensure that B is in descending order, so the algorithm will always find the correct position for the element to be pushed to B.

Tip

Stack B might not always start with the largest element, but it will always be in descending order.
If the largest element is not at the top of B, the algorithm considers the largest element in B to be the one at the top (basically stack start and end of B are considered linked).

1. Find the element with the lowest cost to move to B (so it can be placed in the correct position in B).
2. Rotate both stacks to the most optimal position to move the element from A to B.
3. Push the element from A to B.
4. Repeat until A has exactly 3 elements left.

After phase 1 is done small_sort is performed on A to sort the remaining 3 elements.

Phase 2

Assumptions:

• A is sorted
• A has exactly 3 elements
• B is in descending order
• B is not empty

Note

This phase will only run if B is not empty. And it will be repeated until B is empty.

Before phase 2 (after phase 1) small_sort is performed on A to sort the remaining 3 elements (only once).

Then every push to A will ensure that A is in ascending order, so the algorithm will always find the correct position for the element to be pushed to A.

Tip

Stack A might not always start with the smallest element, but it will always be in ascending order.
If the smallest element is not at the top of A, the algorithm considers the smallest element in A to be the one at the top (basically stack start and end of A are considered linked).

1. Find the element with the lowest cost to move to A (so it can be placed in the correct position in A).
2. Rotate both stacks to the most optimal position to move the element from B to A.
3. Push the element from B to A.
4. Repeat until B is empty.

After phase 2 is done the algorithm will rotate A to make sure that the smallest element is at the top of the stack.

Contributions

All functions, enums, structs and algorithms are documented using doxygen. The documentation always includes @author field indicating the author of the function, enum, struct or algorithm.

42 Headers are also present in all files, though due to multiple refactors they might not always include the true metadata (like the original creation date or the original author). You should refer to the doxygen documentation for the true author of the function, enum, struct or algorithm.

Bellow is a short list of contributions made by each author. For a more detailed list of contributions, please refer to the doxygen documentation.

ppalamio

• Most of the module PARSER
• Most of the module BENCH
• simple() algorithm

kjurkows

• Most of the module STACK
• Module DISORDER
• complex() algorithm
• medium() algorithm
• Makefile
• libft library used by this project
• checker program (bonus)
• get_next_line used by the bonus program