push_swap: the algorithmic challenge of sorting
I didn't know it would be so much fun writing a sorting algorithm.
Since the start of my journey at 42, I started reading a book called Grokking Algorithms, to get to know different algorithms, understand a little bit better how they work and how fast (or slow 🤦♂️) they can be.
The book might seem silly because of its illustrations, but it is actually very technical. Here's my recommendation 😉:
The project
The idea of the project push_swap is to simply sort a stack. We start with two stacks: stack a with the numbers to be sorted and stack b starts empty. The challenge is that you can only perform some specific operations:
sa (swap a) Swap the first 2 elements at the top of stack a.sb (swap b) Swap the first 2 elements at the top of stack b.ss Consists of two swaps. 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.pb (push b) Take the first element at the top of a and put it at the top of b.
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 Consists of two rotations. 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 Consists of two reverse rotations. rra and rrb at the same time.
That limits a lot the algorithms we can use, we have to use one that allow these operations. While searching and talking with my colleagues, I discovered an algorithm that was idealized by a 42 student called A. Yigit Ogun, and he affectionately named it Turk Algorithm 😆. If you want to know more about it, check its article by clicking here.
So I started coding. I decided that working with a linked list would make it more simple. In that case, I wouldn't have a stack a and stack b. I would have only the stack a and when I need to push a node to the stack b, I could only cut the link between that node and the rest of the linked list and voilá: now we have two stacks. Here's a simple implementation of the structure of the linked list:
typedef struct s_stack
{
int val;
int index;
struct s_stack *next;
struct s_stack *prev;
} t_stack;In my algorithm I added some extra variables to help me.
To score 80 on your grade on this project your program has to be able to sort 100 numbers in less than 700 steps.
And to score 100, your program has to sort 500 numbers in less than 5500 steps.
My program has an average of 560 steps when dealing with 100 numbers, and an average of 5100 steps when dealing with 500 numbers.
What I learned
Each project makes me more comfortable with C, its pointers and memory management, I no longer wait to the end of the project to check for memory leaks, just to encounter hundreds of errors in Valgrind. It's getting easier to identify situations that I know will cause memory problems, and I fix them right away.
This project was also extremely helpful on my comprehension of linked lists and performing operations between nodes: changing their position, swapping them, moving to another list, and etc.
Make sure to check the code on the repository below:
marcioflaviob