push_swap

✅ Completed: Mandatory + Bonus
🏅 Score: 125/100

push_swap is a project from 42 School that challenges you to sort data using a limited set of operations. In this project, you will implement an efficient algorithm that sorts a stack of integers using two stacks (A and B) and a predefined set of instructions. The main objective is to minimize the number of operations needed to achieve a sorted stack.

Table of Contents

• Description
• Features
• Requirements
• Installation
• Usage
• How It Works
• Testing

Description

The push_swap project involves creating a program that sorts a list of integers using two stacks and a restricted set of operations. The project typically consists of two components:

• push_swap: Generates a sequence of operations that, when applied to the initial stack, will sort the numbers.
• checker (optional): Takes a list of operations and verifies if applying them to the initial stack results in a sorted stack.

The allowed operations are:

• sa (swap a): Swap the first two elements at the top of stack A.
• sb (swap b): Swap the first two elements at the top of stack B.
• ss: Perform sa and sb simultaneously.
• pa (push a): Move the top element of stack B to the top of stack A.
• pb (push b): Move the top element of stack A to the top of stack B.
• ra (rotate a): Shift all elements of stack A upward by one (the first element becomes the last).
• rb (rotate b): Shift all elements of stack B upward by one.
• rr: Perform ra and rb simultaneously.
• rra (reverse rotate a): Shift all elements of stack A downward by one (the last element becomes the first).
• rrb (reverse rotate b): Shift all elements of stack B downward by one.
• rrr: Perform rra and rrb simultaneously.

Features

• Efficient Sorting: Design an algorithm that sorts integers with a minimal number of operations.
• Operation Optimization: Focus on reducing the total count of moves required.
• Two-Stack Approach: Leverage stack A and stack B to implement the sorting process.
• Optional Checker: Validate the correctness of the operations sequence using the checker program.

Requirements

• C Compiler (e.g., gcc)
• Make (for building the project)
• Unix-based Operating System (Linux, macOS)

Installation

1. Clone the repository:

   git clone https://github.com/yourusername/push_swap.git

2. Navigate to the project directory:

   cd push_swap

3. Compile the project using Make:

   make

   This will compile the push_swap executable and, if implemented, the checker executable.

Usage

Running push_swap

Provide a list of integers as arguments to sort:

./push_swap 3 2 1 6 5 8

The program will output a sequence of operations that will sort the input numbers.

Running checker (Optional)

If you have implemented the checker program, you can pipe the operations from push_swap into checker to verify the result:

./push_swap 3 2 1 6 5 8 | ./checker 3 2 1 6 5 8

The checker will output OK if the sequence sorts the stack correctly, or KO if it does not.

How It Works

1. Input Parsing: The program validates and parses the list of integers provided as command-line arguments.
2. Sorting Algorithm: Using two stacks (A and B), the algorithm computes an optimized sequence of operations that sorts the numbers.
3. Operation Execution: Each operation manipulates the stacks, gradually moving the elements into sorted order.
4. Output Generation: The sequence of operations is printed to standard output.
5. Validation: (Optional) The checker program can simulate the operations to verify that the final stack is sorted.

Testing

This repository includes several test scripts to ensure that push_swap works correctly, efficiently, and without memory leaks. One of the main testing scripts is tester.sh, which automates the execution of all test cases.

How tester.sh works

• Functional Tests:
  The script begins by running a series of functional tests using checker_linux. These tests validate that the sequence of operations generated by push_swap successfully sorts the input numbers.

  • Valid Inputs: When correct data is provided, checker_linux should output OK.
  • Invalid Inputs: For incorrect or malformed input (e.g., non-numeric values, duplicates, out-of-range numbers), the script expects an Error message.

• Empty Input Tests:
  The script checks how push_swap behaves when no arguments are provided. It verifies:

  • That the program returns the expected error message (e.g., Error: no arguments).
  • Using Valgrind, it confirms that no memory errors or leaks occur with empty input.

• Sorted Input Tests:
  When the input is already sorted, push_swap should not output any operations. The script:

  • Confirms that no operations are printed.
  • Runs memory tests via Valgrind to ensure that even in these cases, no memory errors or leaks occur.

• Memory Tests:
  Two key memory-related checks are performed:

  • Memory Errors Test: Using Valgrind (with leak-check disabled), the script ensures that no memory errors are present during the execution of push_swap.
  • Memory Leaks Test: The script compares the number of memory allocations to the number of frees. A mismatch would indicate a memory leak.

• Randomized Tests:
  To simulate various real-world scenarios, the script runs multiple tests with random inputs:

  • It generates unique random numbers within the valid integer range.
  • Each random test checks the correctness of the sorting (using checker_linux) and counts the number of operations performed.
  • This phase also serves as a performance benchmark for your algorithm.

Running the Tests

To run all tests, execute the following command from the project directory:

./tester.sh

The script will automatically go through all phases, display detailed results for each test case (indicating passes and failures), and finally provide a summary showing the total number of errors detected.

This comprehensive testing suite helps ensure that your push_swap implementation is robust, efficient, and free of memory-related issues.

Operation Analysis with check.awk

In addition to the main testing script (tester.sh), this repository includes an AWK script called check.awk that analyzes the sequence of operations produced by push_swap. This script provides detailed statistics about the operations executed during the sorting process.

How check.awk Works

check.awk processes the operations output from push_swap line by line. It performs the following analyses:

• Total Operations Count:
  Counts and prints the total number of operations executed.

• Individual Operation Counts:
  Provides a breakdown for each operation (sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr).

• Merge Operations:
  Detects pairs of operations that can be merged, such as:

  • ra and rb (in any order) can be merged into rr
  • rra and rrb (in any order) can be merged into rrr
  • sa and sb (in any order) can be merged into ss

• Cancel Operations:
  Identifies pairs of operations that cancel each other out, including:

  • ra with rra
  • rb with rrb
  • Duplicate swap operations (e.g., sa followed by sa)
  • pa with pb
  • rr with rrr

At the end of its execution, check.awk prints a summary with:

• The total number of operations.
• The counts for each individual operation.
• The counts for potential merge and cancel operations.

How to Use

To use check.awk, simply pipe the output of push_swap into it. For example:

./push_swap 3 2 1 | ./check.awk

Ensure that check.awk has execute permissions. If necessary, set the permission using:

chmod +x check.awk

This awk-code helps you analyze the efficiency of your push_swap solution by revealing:

• The overall number of operations performed.
• A detailed count of each type of operation.
• Potential areas where operations can be merged or canceled for further optimization.