> For the complete documentation index, see [llms.txt](https://42-guide.gitbook.io/42-guide/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://42-guide.gitbook.io/42-guide/core-curriculum/rank-02/push-swap/algorithms.md). # Algorithms ### Best Algorithm for Push Swap For the **Push Swap** project, **Radix Sort** is typically the most efficient choice for large stacks (e.g., 100–500 elements) because it ensures (O(n \log n)) performance even for large data sets. It works by splitting the sorting process into smaller operations (sorting bits), which are more manageable and efficient than sorting the entire stack all at once. For smaller stacks (e.g., 3–5 elements), **Bubble Sort** or **Insertion Sort** are good choices due to their simplicity and low overhead. ### Algorithm Summary | Algorithm | Best Case | Worst Case | Average Case | Complexity for Push Swap | | ------------------ | ------------- | ------------- | ------------- | ------------------------ | | **Bubble Sort** | (O(n)) | (O(n^2)) | (O(n^2)) | Small stacks (3-5) | | **Insertion Sort** | (O(n)) | (O(n^2)) | (O(n^2)) | Small stacks (5-10) | | **Quick Sort** | (O(n \log n)) | (O(n^2)) | (O(n \log n)) | Medium stacks (100) | | **Radix Sort** | (O(n \log n)) | (O(n \log n)) | (O(n \log n)) | Large stacks (100-500) | | **Selection Sort** | (O(n^2)) | (O(n^2)) | (O(n^2)) | Small stacks (3-5) | | **Merge Sort** | (O(n \log n)) | (O(n \log n)) | (O(n \log n)) | Medium stacks (100) | ## Best Algorithms for Push Swap In the **Push Swap** project, the goal is to sort a stack of integers with the minimum number of operations. There are different strategies and algorithms that can be used to achieve this, with varying degrees of efficiency. Below are some of the best algorithms used in the project, along with their associated time complexities: ### 1. Bubble Sort (for small stacks) * **Algorithm**: Bubble sort is an intuitive sorting algorithm where you repeatedly swap adjacent elements if they are in the wrong order. This continues until the stack is sorted. * **Time Complexity**: * Best case: (O(n)) (already sorted) * Worst case: (O(n^2)) * **Usage**: This algorithm works well for very small stacks (3–5 elements), where the number of elements is so small that the simplicity of bubble sort is sufficient. ### 2. Insertion Sort * **Algorithm**: Insertion sort works by taking each element from the unsorted portion of the stack and inserting it into the correct position in the sorted portion. * **Time Complexity**: * Best case: (O(n)) (already sorted) * Worst case: (O(n^2)) * **Usage**: It's efficient for stacks with a small number of elements (e.g., 5–10), as it minimizes the number of operations needed. ### 3. Quick Sort (for medium-sized stacks) * **Algorithm**: Quick sort is a divide-and-conquer algorithm where you select a "pivot" element, then partition the stack into two sub-stacks (one smaller than the pivot and one larger), and recursively sort the sub-stacks. * **Time Complexity**: * Best case: (O(n \log n)) * Worst case: (O(n^2)) (if the pivot is poorly chosen) * **Usage**: This algorithm is often used for stacks of moderate size (e.g., 100 elements) because it has better average-case performance compared to bubble sort or insertion sort. It can be implemented using the allowed operations in Push Swap. ### 4. Radix Sort (for large stacks) * **Algorithm**: Radix sort works by sorting numbers digit by digit. In Push Swap, it sorts the stack by processing each bit of the binary representation of the numbers and uses a combination of push and rotate operations to move elements between stacks. * **Time Complexity**: * Best case: (O(n \log n)) * Worst case: (O(n \log n)) (Radix sort's time complexity is typically dominated by the number of digits or bits) * **Usage**: This is the most efficient algorithm for large stacks (e.g., 100–500 elements). It is very efficient because it reduces the complexity of sorting large stacks by sorting based on individual digits or bits rather than the entire set of values. ### 5. Selection Sort (for small stacks) * **Algorithm**: Selection sort works by repeatedly finding the minimum element from the unsorted portion of the stack and moving it to the sorted portion. * **Time Complexity**: * Best case: (O(n^2)) * Worst case: (O(n^2)) * **Usage**: This is not ideal for large stacks due to its quadratic time complexity, but for small stacks (3–5 elements), it can be an acceptable solution because it only requires a few operations. ### 6. Merge Sort (for medium-sized stacks) * **Algorithm**: Merge sort is a divide-and-conquer algorithm that splits the stack into halves, sorts each half, and then merges them back together in sorted order. * **Time Complexity**: * Best case: (O(n \log n)) * Worst case: (O(n \log n)) * **Usage**: Merge sort provides (O(n \log n)) time complexity and is effective when you need to guarantee a stable and consistent runtime, but it is more complex to implement using the allowed operations compared to other algorithms. --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://42-guide.gitbook.io/42-guide/core-curriculum/rank-02/push-swap/algorithms.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.