This project has been created as part of the 42 curriculum by eel-kerc, zqian.

• Description
• Team Collaboration
• Operations
• Concepts
• Project Structure
• Algorithm Justification
• Adaptive Strategy
• Instructions
  • Installation
  • Compilation
  • Execution
• Resources
  • AI Usage

Push Swap is a sorting project where the goal is to sort data on a stack using a limited set of instructions and the fewest possible operations. It introduces the concepts of sorting algorithms and their complexity.

Top ↑ | Next ↓

This project was developed in partnership, with responsibilities divided as follows:

The goal is to sort numbers into stack a in ascending order. Below is a summary of the 11 available operations:

Top ↑ | Next ↓

Top ↑ | Next ↓

Top ↑ | Next ↓

The sorting strategy is adaptively selected based on the number of elements and the complexity requirements.

Top ↑ | Next ↓

Our final implementation features a Custom Adaptive Algorithm that dynamically selects the best sorting method based on the input's Disorder Metric.

• Code Logic: The code calculates a disorder score (0 to 1) upon initialization. An adaptive router then evaluates this score against predefined thresholds and calls the most suitable function (min_extraction, chunk_sort, or merge_sort) to handle the specific stack configuration.

• Low Disorder (< 0.2): When the stack is nearly sorted, complex partitioning is counterproductive. We use a linear or near-linear approach to minimize operation overhead.
• Medium Disorder (0.2 - 0.5): Standard data distribution. The chunking method (5 chunks for $n \le 100$, 11 for $n \le 500$) provides the best performance.
• High Disorder (≥ 0.5): For highly reversed stacks, we pivot to advanced partitioning (Merge Sort or high-density chunking) to respect the $O(n \log n)$ complexity.

Our checker must be compile with the rule bonus of the makefile to be used. Here is his algorithm :

• Code Logic: The intialisation of the stacks work as the same of the original push_swap, as well as the error raises. When the stacks is initialized, it read from the stdout read(0) with get_next_line and check if the operation is valid.

• Check Value: After the press of Ctrl + D, the code stop doing the operations. It check if the stacks is well sorted and if the stack b is empty (the stack = NULL).

• Return Value: It can return four different value :

  • Nothing, if there is no argument is given.
  • Error\n, if there is wrong argument, int_max, dupplicate values - wrong operations given.
  • KO\n, if there is good parsing and operations but it doesn't sort the stack a or stack b is not empty.
  • OK\n, if there is good parsing, good operations and both stack a sorted and stack b empty.

Top ↑ | Next ↓

Designed for Linux systems. Ensure you have a C compiler (gcc/clang) and make installed.

git clone GIT push_swap
cd push_swap

The project includes a Makefile with the following standard rules:

# To build the mandatory part:
make

# To build the checker (bonus):
make bonus

The push_swap program takes a list of integers as arguments and outputs the shortest sequence of instructions to sort them.

# Using separate arguments
./push_swap 2 1 3 6 5 8

# Using a single quoted string
./push_swap "2 1 3 6 5 8"

For small datasets, the algorithm is optimized to reach peak efficiency, consistently staying within the limits for a perfect score.

3 Elements (Total: 6 Permutations)

# Example with 3 numbers:
./push_swap --simple 3 1 2

5 Elements (Total: 120 Permutations)

# Example with 5 numbers:
./push_swap --simple 5 2 4 1 3

The checker program verifies if the sequence of operations generated by push_swap correctly sorts the stack. You can pipe the output of push_swap into checker:

ARG="4 67 3 87 23"; ./push_swap $ARG | ./checker $ARG

Expected Outputs:

You can use the shuf utility (available on most Linux systems) to generate random datasets for testing performance:

# Test with 50 random numbers
shuf -i 0-9999 -n 50 > args.txt ; ./push_swap $(cat args.txt)

# Test with 100 random numbers
shuf -i 0-9999 -n 100 > args.txt ; ./push_swap $(cat args.txt)

# Test with 500 random numbers
shuf -i 0-9999 -n 500 > args.txt ; ./push_swap $(cat args.txt)

The program includes a built-in benchmark mode to analyze sorting performance, including disorder metrics and operation breakdowns. Benchmark data is sent to stderr (file descriptor 2).

Run with benchmark enabled:

shuf -i 0-9999 -n 500 > args.txt ; ./push_swap --bench $(cat args.txt) 2> bench.txt | ./checker $(cat args.txt)
cat bench.txt

Example Benchmark Output:

[bench] disorder:  49.93%
[bench] strategy:  Adaptive / O(n√n)
[bench] total_ops: 7997
[bench] sa:  0 sb:  0 ss:  0 pa:  500 pb:  500
[bench] ra:  4840 rb:  1098 rr:  0 rra:  0 rrb:  1059 rrr:  0

Pipe operations to checker while saving benchmark:

ARG="4 67 3 87 23"; ./push_swap --bench --adaptive $ARG 2> bench.txt | ./checker $ARG

The program handles invalid inputs gracefully, displaying Error to standard error:

./push_swap --adaptive 0 one 2 3
# Output: Error

./push_swap --simple 3 2 3
# Output: Error (duplicate detected)

Top ↑ | Next ↓

• 42 Cursus Guide - Push Swap
• Push Swap Project Overview - Ayo Gun
• Step-by-Step Implementation Guide

• Nerd For Tech: Push Swap Tutorial
• Programiz: Radix Sort Algorithm
• W3Schools: Radix Sort DS & Algo

• Push Swap In-Depth Video Guide
• Sorting Visualizer & Algorithm Explanation
• Radix Sort Visualization
• Insertion Sort Explained
• Selection Sort Explained
• Bubble Sort Explained

• Hqndler/42-push_swap
• yatsuZ/Push_swap
• arommers/push_swap
• skyheis/42_push_swap (CodeSandbox)

• Koor.fr: C Expressions Tutorial
• C Operators Reference Guide
• Logical vs. Bitwise Operators in C

Top ↑

As part of the project requirements, here is a summary of how AI (ChatGPT) was utilized during development:

• Documentation & Structure: AI was used to organize and structure this README.md to ensure clarity and professional presentation.
• Performance Testing: AI assisted in designing and executing comprehensive tests for small datasets (3 and 5 elements) to ensure peak efficiency.
• Technical Topics Explored:
  1. Algorithm Selection & Optimization: Researching efficient sorting strategies based on input size.
  2. Chunk-Based Sorting Logic: Understanding the conceptual mechanics and performance impact of chunk boundaries.
  3. Stack Structure Design: Designing robust data structures in C (e.g., doubly linked lists with metadata).
  4. Memory Management: Ensuring proper malloc and free handling within complex structs.
  5. Operation Logic: Sequencing stack operations (sa, ra, pb, etc.) for maximum efficiency.

You may notice the ```bash tags in the instructions above. Here is a quick breakdown of the difference:

• Shell: A generic term for any program that provides a command-line interface to the operating system (e.g., the terminal window). It acts as a "shell" around the OS kernel.
• Bash (Bourne Again SHell): A specific implementation of a shell. It is the default on most Linux distributions.
• The Difference: Think of Shell as the category "Smartphone" and Bash as a specific model like "iPhone". Other shells include Zsh (default on macOS), Dash, and Fish. For this project, most commands will work identically across any modern shell.

Top ↑