Repository files navigation

The "push_swap" project at 42 is a programming challenge that involves sorting a stack of integers using a limited set of instructions. The goal is to develop an efficient algorithm that can transform an unsorted stack into a sorted one, using only a predefined set of operations like pushing and swapping elements between two stacks. It requires to choose the most optimized algorithm data sorting solution. It's a test of both algorithmic problem-solving and coding skills.

The project aims to introduce developers to sorting algorithms and their complexities. It emphasizes the importance of understanding algorithmic complexity and the challenges of optimizing sorting for different configurations of integers.

Two stacks named 'a' and 'b' are provided. Stack 'a' contains random integers, while stack 'b' is empty. The goal is to sort the numbers in stack 'a' using specific operations like swap, push, rotate, etc

• You have 2 stacks nameda andb.
• At the beginning:
  • The stacka contains a random amount of negative and/or positive numberswhich cannot be duplicated.
  • The stackb is empty.
• The goal is to sort in ascending order numbers into stacka. To do so you have thefollowing operations at your disposal:
  • sa (swap a): Swap the first 2 elements at the top of stacka. Do nothing if there is only one or no elements.
  • sb (swap b): Swap the first 2 elements at the top of stackb. Do nothing if there is only one or no elements.
  • ss :sa andsb at the same time.
  • pa (push a): Take the first element at the top ofb and put it at the top ofa. Do nothing if b is empty.
  • pb (push b): Take the first element at the top ofa and put it at the top ofb. Do nothing if a is empty.
  • ra (rotate a): Shift up all elements of stack a by 1. The first element becomes the last one.
  • rb (rotate b): Shift up all elements of stack b by 1. The first element becomes the last one.
  • rr :ra andrb at the same time.
  • rra (reverse rotate a): Shift down all elements of stack a by 1. The last element becomes the first one.
  • rrb (reverse rotate b): Shift down all elements of stack b by 1. The last element becomes the first one.
  • rrr :rra andrrb at the same time

The algorithm is a variation of a divide-and-conquer sorting method designed specifically for two stacks. The approach combines concepts from selection sort, insertion sort, and merge sort.

Algorithm approach: The algorithm takes a divide-and-conquer approach for stacks larger than three. It divides stack_a into smaller chunks and pushes these chunks to stack_b. It then sorts the remaining elements in stack_a and gradually pushes back elements from stack_b to stack_a in a sorted manner.

Stack structure: The stack structure (t_stack) is assumed to have at least two members: value, which is the integer value of the element, and index, which is the initial position or index of the element in the unsorted stack_a. The stack is implemented as a singly linked list, given the presence of the next pointer

1. Given a list of numbers in Stack A
2. Determine the size of Stack A. The `ft_sort`` function first checks the size of the stack.
3. The function then checks:

• If the size is 2, it callsft_sort_two.
• If the size is 3, it callsft_sort_three.
• For sizes larger than 3, it callshandle_large_sort and continue to the next step..

Calculation: Determine the size of stack_a.

size=ft_stack_size(*stack_a);

Purpose: To understand which sorting method to use. Smaller sizes can use simple methods, while larger ones need a more intricate approach.

• Based on the size of Stack A, choose a partitioning criterion. This criterion is often based on pivots or ranges of numbers. and partitioned into third
• Push a fraction of numbers from Stack A to Stack B based on the chosen partitioning criterion. The goal is to leave only a small chunk (say, 3 numbers) in Stack A.

Calculation: Compute size-based partitions (or pivots) ofstack_a.

size=ft_stack_size(*stack_a) /3

gives an indication of how many elements to move fromstack_a tostack_b in each pass.

Purpose: By creating size-based partitions, the algorithm can manage a controlled number of elements, ensuring that only a small, easily sortable number of elements remain in stack_a.

Inhandle_large_sort, the functionft_divide_and_move is called.

ft_divide_and_move(stack_a,stack_b);

This function will repeatedly partitionstack_a and push some elements tostack_b untilstack_a has only 3 elements left.

Calculation: Within theft_partition_and_move function, the algorithm determines whether the current element should be moved tostack_b based on its index and the pivot value. If an element's index is less than the pivot value, it's a candidate to be moved tostack_b.

Purpose: To distribute elements between the stacks based on their relative values, preparing for the merging phase.

With only a few numbers left in Stack A, use simple comparison-based methods to sort them. This is done withft_sort_three in the provided code.

ft_sort_three(stack_a);

Calculation: For a chunk of three numbers in stack_a, the algorithm calculates their relative order using comparison operations in thehandle_sorting_cases function.

Purpose: This is a straightforward sorting of a small number of elements, ensuring that they're in the correct order before the merging phase

Gradually move numbers back from Stack B to Stack A, ensuring they're inserted in the correct order.

Follow these steps to get started with the Push Swap project:

1. Clone the repository:

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

2. Compile the project:

make

3. Run the program with your input:

./push_swap 3 2 1

4. Test the program:

./push_swap 3 2 1| ./checker 3 2 1

Replace321 with your own input numbers for testing.View the detailed usage instructions and available options in the project documentation.

Algorithmic problem-solving steps:

1. Understanding the problem
2. Deciding on computational means, exact versus approximate solving, data structures and algorithm design technique
3. Design an algorithm
4. Prove accuracy
5. Analyze the algorithm
6. Code the algorithm

Computational thinking: A set of techniques for solving complex problems

1. Decomposition: Break a problem into parts
2. Pattern recognition:
   • Interpreting patterns and models
   • (Looking for similarities and trends)
3. Abstraction:
   • Focusing on what is important and ignoring what is unnecessary
   • Organizing data logically
4. Algorithm design: step by step instructions for solving the problem
   • Designing and implementing algorithms
5. Debugging: Fixing errors within the algorithm
6. Generalization: Extending a solution for a particular problemto other kinds of problems