TioElvis | Elvis Vera - Personal Development Blog

push_swap

sortingstacksalgorithmCradix sort42 project

The push_swap project is an algorithmic challenge that involves sorting a stack of integers using a limited set of operations and a second auxiliary stack. The primary goal is to achieve the sorted state using the minimum possible number of operations, making it a test of algorithmic efficiency and strategic thinking. This project is a core part of the 42 curriculum, designed to hone problem-solving skills and a deep understanding of data structures and algorithms in C.

Prerequisites

To build and run push_swap, you will need the following software installed on your system:

GCC (GNU Compiler Collection): A C compiler to compile the source code.
Make: A build automation tool used to manage the compilation process.

These tools are standard on most Unix-like operating systems (Linux, macOS). If you are on Windows, you might need to use a compatibility layer like WSL (Windows Subsystem for Linux) or MinGW.

Getting Started

Follow these steps to get a local copy of push_swap up and running on your machine.

Cloning the Repository

First, clone the repository to your local machine using Git:


git clone https://github.com/TioElvis/push_swap.git
cd push_swap

Building the Project

Navigate into the cloned directory and compile the project using make:


make all

This command will compile both the libft library (a collection of utility functions) and the push_swap executable. You should see output similar to this:


📚 Building libft...
✅ libft compiled successfully!
🔗 Linking push_swap...
✅ push_swap successfully compiled!

            ________o8A888888o_
        _o888888888888K_1888888o
                  ~~~+8888888888o
                      ~8888888888
                      o88888888888
                     o8888888888888
                   _8888888888888888
                  o888888888888888888_
                 o88888888888888888888_
                _8888888888888888888888_
                888888888888888888888888_
                8888888888888888888888888
                88888888888888888888888888
                88888888888888888888888888
                888888888888888888888888888
                ~88888888888888888888888888_
                 488888888888888888888888888
                  888888888888888888888888888
                   888888888888888888888888888_
                   ~8888888888888888888888888888
                     +88888888888888888888~~~~~
                      ~=888888888888888888o
               _=oooooooo888888888888888888
                _o88=8888==~88888888===8888
                ~   =~~ _o88888888=      ~~~
                        ~ o8=~88=~
    🐧 TioElvis says: Great job! Your program is ready! 🐧

Running the Program

Once built, you can run the push_swap executable by providing a list of integers as command-line arguments:


./push_swap 2 1 3 6 5 8

The program will output the sequence of operations required to sort the given numbers. For example:


./push_swap 2 1 3

Expected Output:


sa
ra

Project Structure

The project is organized into a main executable and a custom utility library (libft). Below is a simplified overview of the directory structure:


.
├── Makefile
├── main.c
└── src/
    ├── args_validation.c
    ├── free_memory.c
    ├── init_stack.c
    ├── libft/
    │   ├── ft_atoi.c
    │   ├── ft_bzero.c
    │   ├── ... (many other libft files)
    │   ├── ft_printf/
    │   │   ├── ft_printf.c
    │   │   └── ...
    │   ├── get_next_line/
    │   │   ├── get_next_line.c
    │   │   └── ...
    │   └── libft.h
    ├── push_operations.c
    ├── push_swap.h
    ├── radix_sort.c
    ├── reverse_rotate_operations.c
    ├── rotate_operations.c
    ├── sort_stack.c
    ├── stack_utils.c
    ├── swap_operations.c
    └── utils.c

Makefile: Contains rules for compiling the project, including the libft submodule.
main.c: The entry point of the program. It handles argument parsing, initial stack creation, validation, and calls the main sorting logic.
src/: This directory contains all the core logic for the push_swap program.
- push_swap.h: The main header file defining the t_stack structure and prototypes for all functions.
- libft/: A custom C library providing essential utility functions like string manipulation, memory management, and custom ft_printf and get_next_line implementations.
- *_operations.c: Files dedicated to implementing the various stack operations (push, swap, rotate, reverse rotate).
- *_sort.c: Contains the sorting algorithms, including specific strategies for small stacks and the Radix Sort implementation.
- *_utils.c: Helper functions for stack management, argument validation, and error handling.
- args_validation.c: Functions responsible for checking the validity of command-line arguments, ensuring they are integers and within range, and handling duplicates.
- free_memory.c: Contains functions to properly deallocate memory used by the stacks and split strings, preventing memory leaks.

Core Concepts

Understanding the fundamental data structures and operations is crucial to grasping how push_swap works.

Data Structure: `t_stack`

The project uses a singly linked list to represent the stacks. Each node in the stack is defined by the t_stack structure:


typedef struct s_stack
{
    int             value;  // The integer value stored in the node
    int             index;  // A normalized index used for sorting (especially Radix Sort)
    struct s_stack  *next;  // Pointer to the next node in the stack
}                   t_stack;

The value field holds the actual integer from the input. The index field is dynamically assigned based on the value's rank among all input numbers, which is critical for the Radix Sort implementation.

Allowed Operations

The push_swap problem defines a specific set of operations that can be performed on the two stacks, a and b. Each operation prints its name to standard output.

Swap Operations

sa: Swap the first two elements of stack a. (Does nothing if a has less than two elements).
sb: Swap the first two elements of stack b. (Does nothing if b has less than two elements).
ss: sa and sb at the same time.

Push Operations

pa: Push the top element of stack b onto stack a. (Does nothing if b is empty).
pb: Push the top element of stack a onto stack b. (Does nothing if a is empty).

Rotate Operations

ra: Shift all elements of stack a up by one. The first element becomes the last.
rb: Shift all elements of stack b up by one. The first element becomes the last.
rr: ra and rb at the same time.

Reverse Rotate Operations

rra: Shift all elements of stack a down by one. The last element becomes the first.
rrb: Shift all elements of stack b down by one. The last element becomes the first.
rrr: rra and rrb at the same time.

Sorting Algorithms

The push_swap program employs different sorting strategies depending on the number of elements in the initial stack a. For very small stacks, optimized direct sorting functions are used. For larger stacks, a Radix Sort approach is implemented.

Small Stack Sorts

For stacks with 2, 3, or 5 elements, push_swap uses specialized, highly optimized sorting functions to minimize the number of operations.

Sorting 2 Elements (`sort_two`)

If stack a has two elements, they are simply swapped if they are not already in order.


void    sort_two(t_stack **a)
{
    if ((*a)->value > (*a)->next->value)
        sa(a);
}

Sorting 3 Elements (`sort_three`)

Sorting three elements involves a series of sa, ra, and rra operations to place them in the correct order. The logic covers all 6 possible permutations to find the optimal sequence of moves.


void    sort_three(t_stack **a)
{
    int x;
    int y;
    int z;

    x = (*a)->value;
    y = (*a)->next->value;
    z = (*a)->next->next->value;
    if (x > y && y < z && x < z) // e.g., 3 1 2
        sa(a);
    else if (x > y && y > z) // e.g., 3 2 1
    {
        sa(a);
        rra(a);
    }
    else if (x > y && y < z && x > z) // e.g., 2 3 1
        ra(a);
    else if (x < y && y > z && x < z) // e.g., 1 3 2
    {
        sa(a);
        ra(a);
    }
    else if (x < y && y > z && x > z) // e.g., 2 1 3
        rra(a);
}

Sorting 5 Elements (`sort_five`)

For five elements, the strategy is to push the two smallest elements from stack a to stack b, sort the remaining three elements in a, and then push the elements back from b to a. The get_min_pos function helps locate the smallest elements efficiently.


void    sort_five(t_stack **a, t_stack **b)
{
    int size;
    int min_pos;

    size = stack_size(*a);
    while (size > 3)
    {
        min_pos = get_min_pos(*a); // Find position of the smallest element
        // Rotate stack 'a' to bring the smallest element to the top
        while (min_pos > 0 && min_pos <= size / 2)
        {
            ra(a);
            min_pos--;
        }
        while (min_pos > size / 2)
        {
            rra(a);
            min_pos++;
            if (min_pos >= size)
                break ;
        }
        pb(a, b); // Push the smallest element to stack 'b'
        size = stack_size(*a);
    }
    sort_three(a); // Sort the remaining three elements in stack 'a'
    while (*b)
        pa(a, b); // Push elements back from 'b' to 'a'
}

Radix Sort Implementation

For larger stacks (more than 5 elements), push_swap utilizes a modified Radix Sort algorithm. This approach is efficient because it leverages bitwise operations, which translate well to the allowed push_swap operations.

Assigning Indices

Before sorting, the raw integer values are converted into a set of 0-based indices. This normalization is crucial because Radix Sort works best with non-negative integers within a known range. The smallest number gets index 0, the next smallest gets index 1, and so on.


t_stack *assign_indices(t_stack *stack)
{
    int     index;
    t_stack *runner;
    t_stack *current;

    current = stack;
    while (current)
    {
        index = 0;
        runner = stack;
        while (runner)
        {
            if (runner->value < current->value)
                index++;
            runner = runner->next;
        }
        current->index = index; // Assign the calculated index
        current = current->next;
    }
    return (stack);
}

Bitwise Sorting Passes

The core of the Radix Sort involves iterating through the bits of these assigned indices. For each bit position (from least significant to most significant):

Iterate through stack a for size times.
If the current element's index has a 0 at the current bit position, push it to stack b (pb).
If the current element's index has a 1 at the current bit position, rotate stack a (ra).
After processing all elements for a given bit, all elements in stack b (those with a 0 at the current bit) are pushed back to stack a (pa).

This process effectively sorts the numbers based on the current bit, maintaining the relative order of numbers that had the same bit value in previous passes.


void    process_bit_pass(t_stack **a, t_stack **b, int bit, int size)
{
    int i;

    i = 0;
    while (i < size)
    {
        // Check the 'bit' position of the current element's index
        if ((((*a)->index >> bit) & 1) == 0)
            pb(a, b); // If bit is 0, push to stack 'b'
        else
            ra(a); // If bit is 1, rotate stack 'a'
        i++;
        if (!*a) // Handle cases where stack 'a' becomes empty during the pass
            break ;
    }
    while (*b)
        pa(a, b); // Push all elements from stack 'b' back to stack 'a'
}

void    radix_sort(t_stack **a, t_stack **b)
{
    int size;
    int max_bits;
    int bit;

    if (!a || !*a || is_sorted(*a))
        return ;

    size = stack_size(*a);
    assign_indices(*a); // Ensure indices are assigned
    max_bits = get_max_bits(size); // Determine how many bits are needed for the largest index

    bit = 0;
    while (bit < max_bits)
    {
        process_bit_pass(a, b, bit, size);
        bit++;
    }
}

Usage Examples

Here are some examples demonstrating how to use the push_swap program and its expected behavior.

Basic Sorting

Sort a small set of numbers:


./push_swap 3 1 2

Expected Output:


sa
ra

Sorting a Larger Set

Sort a more complex sequence of numbers. The output will be a longer sequence of operations:


./push_swap 6 3 8 1 9 2 5 7 4

Expected Output (example, actual output may vary slightly based on optimization):


pb
pb
ra
pb
ra
pb
ra
pb
ra
ra
pb
ra
ra
ra
pa
pa
pa
pa
pa
pa
pa
pa
pa

(Note: The actual output for a larger set will be much longer and specific to the Radix Sort implementation.)

Handling Duplicates

The program validates input to ensure no duplicate numbers are provided. If duplicates are found, it will print an error and exit.


./push_swap 1 2 2

Expected Output:


Error

Invalid Input

The program also checks for non-numeric or malformed inputs, printing an error and exiting if found.


./push_swap "hello world"

Expected Output:


Error


./push_swap 1 "  " 3

Expected Output:


Error

Scripts and Commands

The Makefile provides several convenient commands for building and managing the push_swap project.

make all:
- Compiles the libft library.
- Compiles all push_swap source files.
- Links them to create the push_swap executable.
- This is the default target and what you'll typically use to build the project.
make clean:
- Removes all object files (.o) generated during compilation from both the push_swap and libft directories.
- Keeps the push_swap executable.
make fclean:
- Performs make clean.
- Removes the push_swap executable itself.
- Removes the libft.a library file.
- This command leaves the directory in a clean state, as if nothing was ever compiled.
make re:
- Performs make fclean (full clean).
- Then performs make all (rebuilds everything from scratch).
- Useful for ensuring a fresh build after making significant changes or if you encounter unexpected compilation issues.

Loading Project....

push_swap

sortingstacksalgorithmCradix sort42 project

📚 Building libft... ✅ libft compiled successfully! 🔗 Linking push_swap... ✅ push_swap successfully compiled! ________o8A888888o_ _o888888888888K_1888888o ~~~+8888888888o ~8888888888 o88888888888 o8888888888888 _8888888888888888 o888888888888888888_ o88888888888888888888_ _8888888888888888888888_ 888888888888888888888888_ 8888888888888888888888888 88888888888888888888888888 88888888888888888888888888 888888888888888888888888888 ~88888888888888888888888888_ 488888888888888888888888888 888888888888888888888888888 888888888888888888888888888_ ~8888888888888888888888888888 +88888888888888888888~~~~~ ~=888888888888888888o _=oooooooo888888888888888888 _o88=8888==~88888888===8888 ~ =~~ _o88888888= ~~~ ~ o8=~88=~ 🐧 TioElvis says: Great job! Your program is ready! 🐧

. ├── Makefile ├── main.c └── src/ ├── args_validation.c ├── free_memory.c ├── init_stack.c ├── libft/ │ ├── ft_atoi.c │ ├── ft_bzero.c │ ├── ... (many other libft files) │ ├── ft_printf/ │ │ ├── ft_printf.c │ │ └── ... │ ├── get_next_line/ │ │ ├── get_next_line.c │ │ └── ... │ └── libft.h ├── push_operations.c ├── push_swap.h ├── radix_sort.c ├── reverse_rotate_operations.c ├── rotate_operations.c ├── sort_stack.c ├── stack_utils.c ├── swap_operations.c └── utils.c

typedef struct s_stack { int value; // The integer value stored in the node int index; // A normalized index used for sorting (especially Radix Sort) struct s_stack *next; // Pointer to the next node in the stack } t_stack;

The push_swap problem defines a specific set of operations that can be performed on the two stacks, a and b. Each operation prints its name to standard output.

Swap Operations

sa: Swap the first two elements of stack a. (Does nothing if a has less than two elements).
sb: Swap the first two elements of stack b. (Does nothing if b has less than two elements).
ss: sa and sb at the same time.

Push Operations

pa: Push the top element of stack b onto stack a. (Does nothing if b is empty).
pb: Push the top element of stack a onto stack b. (Does nothing if a is empty).

Rotate Operations

ra: Shift all elements of stack a up by one. The first element becomes the last.
rb: Shift all elements of stack b up by one. The first element becomes the last.
rr: ra and rb at the same time.

Reverse Rotate Operations

rra: Shift all elements of stack a down by one. The last element becomes the first.
rrb: Shift all elements of stack b down by one. The last element becomes the first.
rrr: rra and rrb at the same time.

void sort_three(t_stack **a) { int x; int y; int z; x = (*a)->value; y = (*a)->next->value; z = (*a)->next->next->value; if (x > y && y < z && x < z) // e.g., 3 1 2 sa(a); else if (x > y && y > z) // e.g., 3 2 1 { sa(a); rra(a); } else if (x > y && y < z && x > z) // e.g., 2 3 1 ra(a); else if (x < y && y > z && x < z) // e.g., 1 3 2 { sa(a); ra(a); } else if (x < y && y > z && x > z) // e.g., 2 1 3 rra(a); }

void sort_five(t_stack **a, t_stack **b) { int size; int min_pos; size = stack_size(*a); while (size > 3) { min_pos = get_min_pos(*a); // Find position of the smallest element // Rotate stack 'a' to bring the smallest element to the top while (min_pos > 0 && min_pos <= size / 2) { ra(a); min_pos--; } while (min_pos > size / 2) { rra(a); min_pos++; if (min_pos >= size) break ; } pb(a, b); // Push the smallest element to stack 'b' size = stack_size(*a); } sort_three(a); // Sort the remaining three elements in stack 'a' while (*b) pa(a, b); // Push elements back from 'b' to 'a' }

t_stack *assign_indices(t_stack *stack) { int index; t_stack *runner; t_stack *current; current = stack; while (current) { index = 0; runner = stack; while (runner) { if (runner->value < current->value) index++; runner = runner->next; } current->index = index; // Assign the calculated index current = current->next; } return (stack); }

void process_bit_pass(t_stack **a, t_stack **b, int bit, int size) { int i; i = 0; while (i < size) { // Check the 'bit' position of the current element's index if ((((*a)->index >> bit) & 1) == 0) pb(a, b); // If bit is 0, push to stack 'b' else ra(a); // If bit is 1, rotate stack 'a' i++; if (!*a) // Handle cases where stack 'a' becomes empty during the pass break ; } while (*b) pa(a, b); // Push all elements from stack 'b' back to stack 'a' } void radix_sort(t_stack **a, t_stack **b) { int size; int max_bits; int bit; if (!a || !*a || is_sorted(*a)) return ; size = stack_size(*a); assign_indices(*a); // Ensure indices are assigned max_bits = get_max_bits(size); // Determine how many bits are needed for the largest index bit = 0; while (bit < max_bits) { process_bit_pass(a, b, bit, size); bit++; } }

Prerequisites

Getting Started

Cloning the Repository

Building the Project

Running the Program

Project Structure

Core Concepts

Data Structure: `t_stack`

Allowed Operations

Swap Operations

Push Operations

Rotate Operations

Reverse Rotate Operations

Sorting Algorithms

Small Stack Sorts

Sorting 2 Elements (sort_two)

Sorting 3 Elements (sort_three)

Sorting 5 Elements (sort_five)

Radix Sort Implementation

Assigning Indices

Bitwise Sorting Passes

Usage Examples

Basic Sorting

Sorting a Larger Set

Handling Duplicates

Invalid Input

Scripts and Commands

Prerequisites

Getting Started

Cloning the Repository

Building the Project

Running the Program

Project Structure

Core Concepts

Data Structure: `t_stack`

Allowed Operations

Swap Operations

Push Operations

Rotate Operations

Reverse Rotate Operations

Sorting Algorithms

Small Stack Sorts

Sorting 2 Elements (sort_two)

Sorting 3 Elements (sort_three)

Sorting 5 Elements (sort_five)

Radix Sort Implementation

Assigning Indices

Bitwise Sorting Passes

Usage Examples

Basic Sorting

Sorting a Larger Set

Handling Duplicates

Invalid Input

Scripts and Commands

Sorting 2 Elements (`sort_two`)

Sorting 3 Elements (`sort_three`)

Sorting 5 Elements (`sort_five`)

Sorting 2 Elements (`sort_two`)

Sorting 3 Elements (`sort_three`)

Sorting 5 Elements (`sort_five`)