ayogun/push_swap

This project will make you sort data on a stack, with a limited set of instructions, using the lowest possible number of actions. To succeed you’ll have to manipulate various types of algorithms and choose the most appropriate solution (out of many) for an optimized data sorting.

Push_Swap

First of all, I strongly suggest you to read my blog post. If you are as lazy as I am and looking for 125 score, you are in right place.

Content

1. Challenge
2. Project
3. Pseudo Code
4. Flow Chart
5. Visualizer
6. Checker
7. Resources

Challenge

Sort a random list of integers using the smallest number of moves, 2 stacks and a limited set of operations.

You start with two empty stacks: a and b. You are given a random list of integers via command line arguments.

Only these moves are allowed:

• sa : swap a - swap the first 2 elements at the top of stack a. Do nothing if there is only one or no elements).
• sb : swap b - swap the first 2 elements at the top of stack b. Do nothing if there is only one or no elements).
• ss : sa and sb at the same time.
• pa : push a - take the first element at the top of b and put it at the top of a. Do nothing if b is empty.
• pb : push b - take the first element at the top of a and put it at the top of b. 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 and rb 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 and rrb at the same time.

At the end, stack b must empty empty and all integers must be in stack a, sorted in ascending order.

The Project

Create two programs: checker and push_swap.

The checker program reads a random list of integers from the stdin, stores them, and checks to see if they are sorted.

The push_swap program calculates the moves to sort the integers – pushing, popping, swapping and rotating them between stack a and stack b – and displays those directions on the stdout.

You can pipe push_swap into checker, and checker will verify that push_swap's instructions were successful.

Both programs must mandatorily parse input for errors, including empty strings, no parameters, non-numeric parameters, duplicates, and invalid/non-existent instructions.

Push_Swap must conform to the 42 Norm.
Using normal libc functions is strictly forbidden. Students are however, allowed to use: write, read, malloc, free, exit. It must not have any memory leaks. Errors must be handled carefully.
In no way can it quit in an unexpected manner (segmentation fault, bus error, double free, etc).

Psuedo Code

1. In order to start sorting, my code pushes first two elements from top of the stack_a to the stack_b. By this way, we are creating one smallest number and one biggest number in stack_b. This is the prerequisites of my code. Because before pushing a number from stack_a to stack_b, one of the major thing the algorithm does is; comparing the number being pushed with the smallest number of stack_b and the biggest number of stack_b.

2. At this step, algorithm checks every number in stack_a. It searches the number which requires the minimum amount of operations in order to be placed at stack_b in correct spot.

3. After that, algorithm decides which number should be pushed, it calculates how many times it should rotate stack_a and how many times it should rotate the stack_b. Whicehever has the smallest number, algorithm rotates both of the stacks as the smallest number indicates. And it completes the rest of the rotates in the one single stack which ever stack required more rotate operation. You can watch how this step works in action here.

4. After this, algorithm pushed the number from the top of the stack_a to top of the stack_b. Every time this spot at stack_b is correct spot for the number thanks to the previous calculations.This pushing loop continues until only three elements are left in stack_a.

5. Algorithm quickly sorts the left three members in the stack_a.

6. Every members in stack_b one by one are being pushed to the stack_a from top to the bottom. However, it checks everytime before the elements are being pushed. This continues until the stack_b is emptied.

7. Finally, last time required amount of rotation is being applied in order to bring the smallest number on to the top of the stack_a.

Flowchart

You can take a closer look at it.

Don't forget to open the image in new_tab in order to make zoom in.

Visualizer

Checker

For furhter detail about checker program, click here.

Resources

I wrote an article about how the algorithm works. I strongly recommend you to read the article to grasp the idea:

Push Swap — A journey to find most efficient sorting algorithm

push_swap's Issues

It requires version update

This is the older version. I am looking for the updated one, lol. Hence, there can be errors. Please, double check.

Gardaş buası çalışmıyor

İndirdim çalışmadı vallahi

Wrong evaluation sheet

Awesome work with this project. Just to point out that the evaluation sheet is for the so_long project, no push_swap.

Big thanks to Ayogun for this idea and suggestion for other people doing this project

I did this project. I read your approach and copied it. I did not look at your code (maybe a little bit, but not enough to understand something and not to copy something).

Also my strong recommendation for anybody else who wants to follow this approach, do not look at the code. You have the blog explaining how it works. Write your own algorithm. If you are stuck, printf is your friend. You should get it to work over some way with only that, even if it's not sorting correctly yet. If it's not sorting correctly, use the visualizer. Very, very useful. Take small samples, like only 5 numbers, maybe 10 or 20 depending on the problem, but in a range that you can still manually follow what it does.

So with the visualizer, if I saw that at some point it was moving elements in a way that should not happen, I used the stack size to print the information I needed only for that part. I got it to work, just had too many moves for 500 numbers.
That was the first time that I downloaded this repo and used the visualizer on both to compare them step by step. Mine was doing pretty much the exact same thing. And then there were steps where mine was taking longer moves. Helped me to check what the moves were at that point and why it was taking them (wrong if condition of course...)

So now I have my own version of this algo, I think mine is even a little bit better. Definitely faster. I think because of checking duplicates. Wrote me a test script to run the program like 100 times with 500 random numbers and calculated the average amount of moves, giving me the max and min amount and the time it took to run all of them.

Still have to do some refactoring in the following days to match the norm tho. Also, my project has the same small issue that it is possible to go over 5500 moves for 500 numbers, same as this repo does. I have some ideas that could possibly solve that. One harder than the other. Don't know if that is worth the effort since my average is like 5100 operations. One might not be that hard, maybe I give it a try.

If anybody still wants to look at the code, even tho I strongly discourage you if you still plan on doing the project yourself, here is my repo

Memory Leak When Handling Error with a Single Argument