Overview Testing Push Swap is crucial to ensure correctness and efficiency. The program must:
Correctly sort all valid inputsMinimize operations to achieve good performance scoresHandle edge cases without errors or crashesManage memory properly with no leaks
Basic Testing Manual Testing Test the program with simple inputs:
# Test with 3 numbers ./push_swap 2 1 3 # Test with 5 numbers ./push_swap 5 4 3 2 1 # Test with quoted string input ./push_swap "3 2 1"
Verifying Output To verify that the operations actually sort the stack, you’ll need a checker program. The typical approach:
# Generate operations and pipe to checker ARG = "4 67 3 87 23" ; ./push_swap $ARG | ./checker $ARG
The checker program is typically provided separately by 42 School or needs to be implemented as a bonus. It reads operations from stdin and verifies they sort the stack correctly.
Test Categories Small Stack Tests (2-3 elements)
Test with 2 elements
./push_swap 2 1 # Expected output: sa ./push_swap 1 2 # Expected: no output (already sorted)
Test with 3 elements
# All permutations of 3 elements ./push_swap 1 2 3 # Already sorted ./push_swap 1 3 2 # Should output: sa ra ./push_swap 2 1 3 # Should output: sa ./push_swap 2 3 1 # Should output: rra ./push_swap 3 1 2 # Should output: ra ./push_swap 3 2 1 # Should output: sa rra
The algorithm uses a specialized sort_three() function for optimal 3-element sorting. Medium Stack Tests (5-100 elements) # Test with 5 random numbers ./push_swap 5 2 8 1 9 # Test with larger set ./push_swap $( seq 1 100 | shuf | tr '\n' ' ' )
For 5 elements, you should aim for ≤12 operations. The algorithm uses the turk algorithm for stacks larger than 3.
Large Stack Tests (100-500 elements) # Test with 100 numbers ARG = $( seq 1 100 | shuf | tr '\n' ' ' ) ./push_swap $ARG | wc -l # Test with 500 numbers ARG = $( seq 1 500 | shuf | tr '\n' ' ' ) ./push_swap $ARG | wc -l
Performance benchmarks:
100 elements : Less than 700 operations (5 points), less than 900 (4 points), less than 1100 (3 points)500 elements : Less than 5500 operations (5 points), less than 7000 (4 points), less than 8500 (3 points)
Edge Cases No Arguments
Empty String
Single Number
./push_swap # Expected: no output, exit cleanly
./push_swap 1 2 3 4 5 # Expected: no output (already sorted)
The program checks is_stack_sorted() before attempting to sort.
# Worst case scenario ./push_swap 100 99 98 97 96 95 94 93 92 91
This tests the algorithm’s worst-case performance.
Duplicate Numbers ./push_swap 1 2 3 2 4 # Expected: "Error" (duplicates not allowed)
The program detects duplicates via error_repetition() in ft_error_exit.c:72.
Invalid Syntax Non-numeric Input
Integer Overflow
Invalid Signs
./push_swap 1 2 abc 4 # Expected: "Error"
Syntax validation is handled by error_syntax() in ft_error_exit.c:54.
Automated Testing Create a script to test operation counts:
#!/bin/bash # Test 100 random stacks of size 100 echo "Testing 100 elements (500 iterations):" sum = 0 for i in { 1..500} ; do ARG = $( seq 1 100 | shuf | tr '\n' ' ' ) count = $( ./push_swap $ARG | wc -l ) sum = $(( sum + count )) done avg = $(( sum / 500 )) echo "Average operations: $avg " # Test 500 elements echo "\nTesting 500 elements (100 iterations):" sum = 0 for i in { 1..100} ; do ARG = $( seq 1 500 | shuf | tr '\n' ' ' ) count = $( ./push_swap $ARG | wc -l ) sum = $(( sum + count )) done avg = $(( sum / 100 )) echo "Average operations: $avg "
Run with:
chmod +x test_performance.sh ./test_performance.sh
Correctness Testing Script #!/bin/bash errors = 0 tests = 0 # Test with checker for i in { 1..100} ; do ARG = $( seq 1 100 | shuf | tr '\n' ' ' ) result = $( ./push_swap $ARG | ./checker $ARG ) tests = $(( tests + 1 )) if [ " $result " != "OK" ]; then errors = $(( errors + 1 )) echo "FAIL: Test $i " fi done echo "\nResults: $(( tests - errors))/ $tests tests passed"
Memory Leak Testing Use Valgrind to check for memory leaks:
# Install valgrind (if needed) sudo apt-get install valgrind # Ubuntu/Debian brew install valgrind # macOS (may require special setup) # Test for memory leaks valgrind --leak-check=full --show-leak-kinds=all ./push_swap 4 2 7 1 3
Expected Valgrind Output ==12345== HEAP SUMMARY: ==12345== in use at exit: 0 bytes in 0 blocks ==12345== total heap usage: X allocs, X frees, Y bytes allocated ==12345== ==12345== All heap blocks were freed -- no leaks are possible
The program properly frees memory in free_stack() (ft_error_exit.c:16) and free_split() (ft_error_exit.c:33), ensuring no leaks even on error conditions.
Test with Different Ranges # Negative numbers ./push_swap -5 -2 -8 -1 0 3 # Mixed positive and negative ./push_swap -100 0 100 -50 50 # Maximum integer values ./push_swap 2147483647 -2147483648 0
Consider using visualizers to watch the sorting process:
push_swap_visualizer : GUI tool showing stack operationspush_swap_tester : Comprehensive testing framework
These tools help understand how the algorithm works and identify inefficiencies.
Testing Checklist Debugging Tips Add Debug Output Modify operations functions to print stack state:
// Temporary debug code (remove before submission) void print_stacks (t_list * a , t_list * b ) { printf ( "Stack A: " ); while (a) { printf ( " %d " , a -> nbr ); a = a -> next ; } printf ( " \n Stack B: " ); while (b) { printf ( " %d " , b -> nbr ); b = b -> next ; } printf ( " \n\n " ); }
Test Specific Cases If a test fails, isolate the exact input:
# Save failing input echo "4 67 3 87 23" > failing_test.txt # Test repeatedly ./push_swap $( cat failing_test.txt )
Next Steps 