This project has been created as part of the 42 curriculum by amissa

Table Of Ccontents

1. Description
2. Usage
3. Sorting Algorithm
4. Bonus Part
5. Resources
6. AI Usage

---

Description

push_swap is an sorting algorithmic project where you must sort a stack of integers using only a limited set of operations and two stacks (a and b).

THE GOAL

is to sort a given list of unique integers using a limited set of instructions and only two data structures: stack A and stack B. The primary objective is to achieve the sorted order using the lowest possible number of operations

in case of ERROR the program display error in standerd error

Only these moves are allowed:

• sa (swap a): Swap the first 2 elements at the top of stack a.

• sb (swap b): Swap the first 2 elements at the top of stack b.

• ss : sa and sb at the same time.

• pa (push a): Take the first element at the top of b and put it at the top of a.

• pb (push b): Take the first element at the top of a and put it at the top of b.

• ra (rotate a): Shift up all elements of stack a by 1. The first element becomes the last one.

• rb (rotate b): Shift up all elements of stack b by 1. The first element becomes the last one.

• rr : ra and rb at the same time.

• rra (reverse rotate a): Shift down all elements of stack a by 1. The last element becomes the first one.

• rrb (reverse rotate b): Shift down all elements of stack b by 1. The last element becomes the first one.

• rrr : rra and rrb at the same time.

At the end, stack b must be empty and all integers must be in stack a, sorted in ascending order.

Usage

1. CLONE THE REPOSITORY

	git clone <repository-url>
	cd push_swap

2. Build the Project

The project uses a Makefile for building. Simply run:

	-> make

This Create the push_swap executable

3. Run The Program

	./push_swap 3 2 1

The output will be a list of instructions (one per line) to sort the input

Example:

./push_swap 30 20 10

Output:

ra
sa

SORTING ALGORITHM

I use the best move sorting algorithm to solve this project because I consider it the most efficient approach for this type of problem.

How it works:

The algorithm searches for the number that requires the smallest number of instructions to move, then places it in the correct position in stack B. This process is applied to all numbers in stack A.

Optimization for large datasets:

When the total length of the stack exceeds 400 elements, I leave 50 elements in stack A and sort them using a different algorithm to optimize the total number of instructions. I'll discuss this optimization in detail later.

DATA STRUCTURES

I work with three main structures in this project:

1. t_stack

This structure holds information about each element and creates a linked list.

typedef struct s_stack
{
    int				idx;
	int				value;
	int				cost_a;
	int				cost_b;
	int				total;
	char			rt_type_a;
	char			rt_type_b;
	struct s_stack	*next;
} t_stack;

2. t_stacks

This structure holds both stacks (A and B), a pointer to the node_cost structure, and the sizes of both stacks.

• Purpose: Pass all necessary data as a single parameter to functions
• Contains: Stack A, Stack B, stack sizes, and cost information

typedef struct s_stacks
{
    t_stack		*ska;
    t_stack		*skb;
    t_node_cost	*node_cost;
    int			skasize;
    int			skbsize;
} t_stacks;

3. t_node_cost

This structure holds information about the best node — the node that requires the smallest number of instructions to be placed in its correct position.

Members:

Member	Description
total_cost	Total number of moves required
cost_ska	Number of moves needed in stack A to bring the element to the top
cost_skb	Number of moves needed in stack B to position it correctly
rt_type_a	Rotation type for stack A: 'r' = rotate, 's' = reverse rotate
rt_type_b	Rotation type for stack B: 'r' = rotate, 's' = reverse rotate

typedef struct s_node_cost
{
	int		total_cost;
	int		cost_ska;
	int		cost_skb;
	char	rt_type_a;
	char	rt_type_b;
} t_node_cost;

Now let's break down the algorithm step by step:

STEP 1: VALIDATE USER INPUT

Process:

1. Loop through arguments: Iterate through argv from index 1 to argc - 1

2. Parse each argument: Loop through each character in argv[i] until '\0'

3. Convert to integer: Pass the string to atoi with pointer incrementation

4. Custom atoi validation:

   • Skip leading whitespace
   • Check for operators ('-' or '+')
   • Validate that remaining characters are digits ('0' to '9')
   • Skip trailing whitespace
   • Return 0 (error) if:
     • Current character is not a digit, operator, or space
     • An operator is found and the previous character *(str - 1) is already a digit
     • The number exceeds INT_MAX or INT_MIN

5. Create node: If validation passes, create a new node and add it to the end of the list

6. Continue parsing: The pointer now points after the current number, allowing automatic continuation of validation for the next number in the same argument

Error handling:

If any validation fails, the program:

• Prints "Error\n" to stderr
• Frees all allocated memory
• Returns 0

---

STEP 2: CHECK IF ALREADY SORTED

If the stack is already sorted:

• The program displays nothing
• Returns to the prompt

If the stack is not sorted:

• Proceed to the sorting algorithm

---

STEP 3: INDEX NORMALIZATION

First, I loop through the entire list and convert each value to its corresponding sorted index.

Example:

Input:  50 200 10 95
Output:  1   3  0  2

Explanation:

• 10 is the smallest → index 0
• 50 is the second smallest → index 1
• 95 is the third smallest → index 2
• 200 is the largest → index 3

This means when sorting, the number with index 0 should be placed in position 0, the number with index 1 in position 1, and so on.

now let's start with checking the length of stack if the stack have more than 3 element apply best move algo if the stack len 2 and program enter to this part that mean it's not sorted so swap them to sort the stack and else mean ths stack have 3 element so i sort them by external function that take the bigger element and move them to the end of stack and check first and second element if first > second element swap them so that mean the stack have 3 element sorted in 2 moves in maximum

STEP 3: CHOOSE SORTING STRATEGY

After index normalization, I determine the sorting strategy based on stack size:

Stack size > 3 elements:

• Apply the best move algorithm (detailed below)

Stack size = 2 elements:

• If the program reaches this point, the stack is unsorted
• Execute sa (swap) to sort the stack
• Result: Sorted in 1 move

Stack size = 3 elements:

• Sort using an optimized 3-element function
• Process:
  1. Move the largest element to the end of the stack
  2. Check if the first element > second element
  3. If true, swap them with sa
• Result: Stack sorted in maximum 2 moves

---

STEP 4: BEST MOVE ALGORITHM

OPTIMIZATION: LEAVING ELEMENTS IN STACK A

I use a variable to determine how many elements to leave in stack A:

• Stack A size < 400: Leave 3 elements
• Stack A size ≥ 400: Leave 50 elements

Why leave elements?

The best move algorithm requires rotating stack B each time to place an element in the correct position. Leaving elements in stack A allows for final optimization:

• 3 elements: Can be sorted in maximum 2 moves
• 50 elements: Can be sorted efficiently after the main algorithm completes

The cost of not optimizing:

When stack A contains more than 400 elements, we would need 100-150 rotations to place each element in the correct position. This adds unnecessary instructions.

---

MAIN ALGORITHM LOOP

Process:

Loop through stack A, moving elements to stack B until the threshold is reached:

1. Update stack sizes:

   • Decrement skasize
   • Increment skbsize

2. Calculate rotation costs:

   • Use compute_rot_costs() to calculate the cost of moving each element

3. Find the best move:

   • Use find_min_move_node() to identify the node with the smallest number of instructions

4. Execute the move:

   • Push the best node from stack A to stack B (pb)

---

ROTATION OPTIMIZATION

The t_node_cost structure holds information about the best node:

• Number of rotations needed for stack A
• Number of rotations needed for stack B
• Rotation type for each stack ('r' = rotate, 's' = reverse rotate)

Combined rotations:

When both stacks need the same rotation type, I use combined operations (rr or rrr):

Example:

Stack A needs: 13 rotations (rotate)
Stack B needs: 10 rotations (rotate)

Without optimization: 23 total moves (13 × ra + 10 × rb)
With optimization:    13 total moves (10 × rr + 3 × ra)

This optimization reduces unnecessary operations by performing simultaneous rotations.

---

PONUS PART

The bonus part includes a checker program that validates whether the instructions from push_swap correctly sort the stack.

How it Works

1. READING AND VALIDATING NUMBERS

The checker reads the input numbers the same way as push_swap:

• Takes each number as an element in a struct and adds it to a linked list
• Validates the input using the same logic as check_user_input() in push_swap
• Checks for invalid input and duplicates
• On error: Displays "Error\n" and exits

---

2. READING INSTRUCTIONS FROM STDIN

Buffering process:

1. Read instructions from standard input into a buffer
2. Read 4 bytes at a time and append to the original buffer
3. Validate that the buffer contains only valid instruction characters: p, a, b, r, s, \n
4. If invalid character found: Free the buffer and return error

Parsing and executing instructions:

while (tmp && *tmp)
{
    i = 0;
    while (*(tmp + i) && *(tmp + i) != '\n')
        i++;
    if (i > 3)
        return (free(tmp), 0);
    if (!apply_moves(tmp, i, ska, skb))
        return (free(tmp), 0);
    while (*tmp && i-- >= 0)
        tmp++;
}

How it works:

1. Loop through the buffer until a newline character \n
2. Variable i holds the length from the current position to the newline (instruction length)
3. Validate instruction length: If i > 3, the instruction is invalid → return error
4. Call apply_moves(tmp, i, ska, skb) to validate and execute the instruction
5. Increment the pointer by i to move to the next instruction

---

3. VALIDATING AND EXECUTING MOVES

The apply_moves() function uses ft_strncmp(src, dst, len) to match instructions:

if (ft_strncmp("ra\n", instra, len) == 0 || ft_strncmp("ra", instra, len) == 0)
    rotate(ska);

Process:

• Compare the buffer substring with valid instructions (sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr)
• If match found: Execute the corresponding operation on the stack
• If no match found: Return 0 → Display "Error\n" and exit

Pointer management:

After executing each instruction, increment the pointer by i + 1 (to skip past the newline), making it point to the beginning of the next instruction.

---

Output :

Result	Output
Stack is sorted and stack B is empty	OK
Stack is not sorted or stack B is not empty	KO
Invalid instruction or invalid input	Error

To Build Bonus :

Example usage:

./push_swap 3 2 1 | ./checker 3 2 1
OK

echo -e "sa\npb" | ./checker 3 2 1
KO

echo "invalid_instruction" | ./checker 3 2 1
Error

---

Resource

Key topics I studied:

• Linked Lists
• Sorting Algorithms

Helpful resources:

Link	Description
Sorting Algorithm Comparison	Overview of sorting algorithm types and performance
Push Swap Inspiration	Algorithm strategy and implementation
Sorting Algorithm Types	Understanding different sorting approaches
VisuAlgo - Sorting	Interactive visualization of sorting algorithms (Bubble, Selection, Insertion, Merge, Quick, Heap)

---

AI USAGE

I did not use AI to learn or implement any part of this project.

AI was only used for documentation purposes:

• Formatting and structuring the README file
• Grammar and spelling corrections
• Improving the visual presentation of the documentation

All code, algorithms, and problem-solving were done independently without AI assistance.