rask24 / push_swap

Push Swap

This repository contains the implementation of the push_swap project, which focuses on sorting a stack of numbers using a limited set of actions.

Build

Prerequisites

• GCC or Clang compiler
• Make
• Git (for submodule management)

Compilation

• Clone the repository and initialize submodules

clone <repository-url>
cd <repository-directory>
git submodule update --init

• Compile the main program

make

This will create the push_swap executable.

• Compile the checker (bonus):

make bonus

This will create the checker executable.

Additional Targets

• Clean object files

make clean

• Remove all generated files

make fclean

• Recompile everything

make re

Development Options

• To compile with development flags (including sanitizers)

make DEV_FLAGS="-O0 -g -fsanitize=address,integer,undefined -D DEV"

• To compile with leak checking

make LEAK_FLAGS="-D LEAK"

Testing

• Run unit tests

make test

• Generate code coverage

make coverage
make report_coverage

Norminette

• Check code style:

make norm

Note: Ensure you have all necessary dependencies installed before building and running the project.

Algorithm

日本語版

The sorting is done in two stages:

1. Push from stack_a to stack_b, dividing into segments according to the value of the elements.
2. Greedily push from stack_b back to stack_a, starting with the largest segments

First, a rough sort is performed, followed by a more precise sort in the second stage.

1. Pushing to stack_b in Segments

Determine the number of segments as shown in the table below.

Number of Elements in Stack	Number of Segments
~ 99	1
100 ~ 249	3
250 ~ 499	5
500 ~ 749	7
...	...

Segments are rough groupings, where smaller element numbers in the stack correspond to smaller segment numbers.

In this process, rotate stack_a and sequentially push elements with smaller segment numbers to stack_b.

2. Greedily Pushing Back to stack_a

From stack_b, push elements back to stack_a, starting with those in the largest segments. Ensure that stack_a always maintains a broadly sorted state during this process. A broadly sorted state means that when the stack's top and bottom are connected to form a ring, the minimum and maximum values are adjacent, and all other elements are sorted.

If there are multiple elements with the same segment number, choose the one that minimizes the number of moves needed to maintain a broadly sorted state and push it. The minimum number of moves refers to calculating all four possible ways of pushing for each element and selecting the one with the smallest number among all elements.

push_swap's Issues

handle empty string

./push_swap “”

Modify Function Pointer Typedef

update rake test

add e2e test
fix pain.sh

update push_b_segmented

add member “segment” to t_content

Submodule HTTP Migration

rename opt

e2e test

Introduce typedefs for function pointers

content: 0-indexed

[Refactor] Google test

fix module

implement sort

greedy sort

data structure

t_content

typedef struct s_content
{
	int			index;   // compressed number of the input
    int         sf_cost; // selection forward cost
    int         sr_cost; // selection reverse cost
    int         if_cost; // insert forward cost
    int         ir_cost; // insert reverse cost
}				t_content;

flow

• implement selection setter
• test selection setter
• implement insertion setter
• test insertion setter
• calculate the best way of 4
• test calclate the best way
• move with optimized way
• integrated test

delete _put_void

refactor

type

• t_list -> t_stack

variable

• stack_a -> a
• **stack_a -> **p_a;

structure (pending)

use module

• push_swap.h
• sort.h
• utils.h
• stack_operation.h
• checker.h(bonus)

implement nano_sort

add google test to github actions

add README

implement argument checker

1. some arguments aren't integer
2. some integers are bigger than an integer
3. there are duplicates

fix test

optimize initial push_b on large sort

optimizetion for preordered stack

handle string argumet

e.g.
case ./push_swap "1 4 3 2"

implement checker

[Feature] Add Codecov

implement micro sort

• element: 4
• element: 5

update README

optimize micro sort

add test check allowed external functions

Convert is_invalid_argument to check_args

• update function
• update tests