From project's Subject: "Introduction: The Push swap project is a very simple and a highly straightforward algorithm project: data must be sorted. You have at your disposal a set of integer values, 2 stacks, and a set of instructions to manipulate both stacks. Your goal? Write a program in C called push_swap which calculates and displays on the standard output the smallest program, made of Push swap language instructions, that sorts the integers received as arguments. Easy? We’ll see... Objectives: Writing a sorting algorithm is always a very important step in a developer’s journey. It is often the first encounter with the concept of complexity. Sorting algorithms and their complexity are part of the classic questions discussed during job interviews. It’s probably a good time to look at these concepts since you’ll have to face them at some point. The learning objectives of this project are rigor, use of C, and use of basic algorithms. Especially focusing on their complexity. Sorting values is simple. To sort them the fastest way possible is less simple. Especially because from one integers configuration to another, the most efficient sorting solution... "
Group project by Ani Mema and Jacopo Cardinaux.
The Push Swap project is a sorting algorithm challenge designed for the 42 school. The goal is to sort a list of integers using a limited set of operations and two stacks. This project involves creating an efficient sorting algorithm, often used in competitive programming to optimize sorting operations.
- Introduction
- Authors
- Files and Directories
- Compilation and Execution
- Program Logic
- Usage
- Operations
- Algorithm Explanation
- Managing Stacks
a
andb
- Bonus
- Testing and Debugging
- Conclusion
- Makefile: Script for compiling the project.
- push_swap.c: Main entry point for the push_swap program.
- push_swap.h: Header file containing declarations and macros.
- init_b.c, list_init.c, listutils.c, ok_input.c: Initialization and utility functions.
- order_3n5.c: Logic for sorting small sets of numbers.
- workutils.c: Additional utility functions.
- algoritm/: Directory containing the main algorithm implementation.
- best_move.c, inst_reader.c: Functions to calculate the best moves and read instructions.
- bonus/: Directory containing the bonus checker program.
- checker.c, checker.h: Source code and header for the checker.
- ft_printf/: Directory containing a custom printf implementation.
- Makefile, ft_printf.c, ft_printf.h: Source and header files for ft_printf.
- gnl/: Directory containing the get_next_line implementation.
- get_next_line.c, get_next_line.h: Source and header files for get_next_line.
- libft/: Directory containing standard library functions.
- **Makefile, .c, .h: Source and header files for libft.
- moves/: Directory containing the push_swap operations.
- moves_p.c, moves_r.c, moves_rr.c, moves_s.c: Push, rotate, reverse rotate, and swap operations.
To compile the project, simply run the following command in the root directory:
make
This will generate an executable named push_swap
.
To run the push_swap
program with a list of integers:
./push_swap [list_of_integers]
Example:
./push_swap 3 2 1
- Input Validation: The program first validates the input to ensure all arguments are integers and within the valid range.
- List Initialization: Initializes the stacks
a
andb
using the provided list of integers.
The core logic involves repeatedly choosing the best operation to move elements from stack a
to stack b
and then back to stack a
in sorted order.
After sorting, the program frees all allocated memory to avoid memory leaks.
The push_swap
program generates a sequence of operations to sort the stack:
- sa: Swap the first two elements at the top of stack
a
. - sb: Swap the first two elements at the top of stack
b
. - ss:
sa
andsb
at the same time. - pa: Push the top element of
b
ontoa
. - pb: Push the top element of
a
ontob
. - ra: Rotate stack
a
(shift up all elements by 1). - rb: Rotate stack
b
(shift up all elements by 1). - rr:
ra
andrb
at the same time. - rra: Reverse rotate stack
a
(shift down all elements by 1). - rrb: Reverse rotate stack
b
(shift down all elements by 1). - rrr:
rra
andrrb
at the same time.
For sets of 3 to 5 elements, specific predefined sequences are used to sort efficiently.
- Chunking: Divide the list into manageable chunks.
- Sorting: Use a combination of operations to push the smallest elements to stack
b
and then push them back to stacka
in sorted order. - Optimization: Calculate the best move using cost analysis to minimize the number of operations.
- best_move.c: Implements the logic to determine the most efficient move at each step.
- inst_reader.c: Reads and interprets the instructions for operations.
The push_swap
algorithm utilizes two stacks, a
and b
, to sort a list of integers. The main goal is to move elements between these stacks using a limited set of operations to achieve a sorted order in stack a
.
- Input Parsing: The program reads a list of integers from the command line and stores them in stack
a
. Stackb
is initially empty. - Validation: The input is validated to ensure all elements are integers and there are no duplicates.
The algorithm uses a series of predefined operations to manipulate the stacks:
-
Push Operations:
pa
: Push the top element of stackb
onto stacka
.pb
: Push the top element of stacka
onto stackb
.
-
Swap Operations:
sa
: Swap the first two elements at the top of stacka
.sb
: Swap the first two elements at the top of stackb
.ss
: Performsa
andsb
simultaneously.
-
Rotate Operations:
ra
: Rotate stacka
(shift all elements up by 1, the first element becomes the last).rb
: Rotate stackb
(shift all elements up by 1, the first element becomes the last).rr
: Performra
andrb
simultaneously.
-
Reverse Rotate Operations:
rra
: Reverse rotate stacka
(shift all elements down by 1, the last element becomes the first).rrb
: Reverse rotate stackb
(shift all elements down by 1, the last element becomes the first).rrr
: Performrra
andrrb
simultaneously.
- Chunking: The list in stack
a
is divided into smaller chunks. This helps in managing smaller subsets of the list, making it easier to sort. - Pushing to Stack
b
: Elements are moved from stacka
to stackb
in a way that allows easier sorting. The smallest elements are pushed first. - Sorting Stack
b
: Once stackb
has all elements, it is sorted in descending order. This allows the elements to be pushed back to stacka
in ascending order. - Pushing Back to Stack
a
: The sorted elements in stackb
are moved back to stacka
.
Below is a diagram illustrating the push_swap
process:
Initial State:
Stack a: [4, 3, 2, 1]
Stack b: []
Step 1: pb (push 4 from a to b)
Stack a: [3, 2, 1]
Stack b: [4]
Step 2: pb (push 3 from a to b)
Stack a: [2, 1]
Stack b: [3, 4]
Step 3: sa (swap the first two elements in a)
Stack a: [1, 2]
Stack b: [3, 4]
Step 4: pb (push 1 from a to b)
Stack a: [2]
Stack b: [1, 3, 4]
Step 5: pb (push 2 from a to b)
Stack a: []
Stack b: [2, 1, 3, 4]
Step 6: pa (push 2 from b to a)
Stack a: [2]
Stack b: [1, 3, 4]
Step 7: pa (push 1 from b to a)
Stack a: [1, 2]
Stack b: [3, 4]
Step 8: ra (rotate stack a)
Stack a: [2, 1]
Stack b: [3, 4]
Step 9: pa (push 3 from b to a)
Stack a: [3, 2, 1]
Stack b: [4]
Step 10: pa (push 4 from b to a)
Stack a: [4, 3, 2, 1]
Stack b: []
Final State:
Stack a: [1, 2, 3, 4]
Stack b: []
The bonus
directory contains a checker
program that verifies the correctness of the sequence of operations generated by push_swap
.
To compile the checker program, run:
make bonus
The push_swap
algorithm is an intricate process that involves using two stacks to sort a list of integers through a series of push, swap, rotate, and reverse rotate operations. By strategically moving elements between the stacks, the algorithm aims to minimize the number of operations needed to sort the list efficiently.