push_swap with Radix Sort

42 Project about sorting algorithms.

Table of Contents

• How to use the program
• Project Overview
• To-Do
• Result
• Tips for 42 students
• What I learned

How to use the program

Git clone the repository and use make to compile.

Then run it with ./push_swap followed by different numbers, positive or negative. For example:

./push_swap -2147483648 100 75 3 2147483647 0

If the arguments are valid, the program will output the most efficient list of actions to sort the list.

Project Overview

The program, called push_swap, takes a list of integers and sorts it using a set of predefined operations on two stacks. Another program, called checker, verifies the correctness of the sorting by executing the instructions generated by push_swap on the stack A.

The predefined operations are the following:

Operation	Description
sa	swaps the first two elements of stack A
sb	swaps the first two elements of stack B
ss	sa and sb at the same time
pa	pops the first elememt of B and puts it on top of A
pb	pops the first elememt of A and puts it on top of B
ra	rotates stack A up by one, the first element becomes the last one
rb	rotates stack B up by one, the first element becomes the last one
rr	rotates both A and B up by one
rra	rotates stack A down by one, the last element becomes the first one
rrb	rotates stack B down by one, the last element becomes the first one
rrr	rotates both A and B down by one

To Do

1. Research

• stack in C
• difference and advantages of using an array or simply, doubly and doubly circular linked list
• different sorting algorithms
• Big O Notation

2. Code Structure

• creating a Makefile that doesn't relink
• creating a header file

3. Parsing

• receive the arguments via ft_split Check if the following requirements of the arguments are fullfilled:
• handles "1 2 3" as well as 1 2 3 as input
• error management
  • only numbers and spaces
  • no doubles
  • numbers between INT_MIN and INT_MAX
  • edge cases: think about what to do with "-0", "--", "1-2" and ""
  • the subject specifies that in case of error you need to send "Error\n" on the standard error. However, I entered customized error messages because it's easier to debug in case sth doesn't work. I deleted them in the end for the evaluation.
• convert the arguments from string to int

4. Implementation

• creation of the linked list
• create the functions for push, rotate and swap, then create the respective function for all the operations
• handle the already sorted numbers, just return in this case
• function for two numbers
• function for three numbers (only 6 possibilites)
• function for four and five numbers - I divide my list and check whether the smallest number is in the first half or the second one, then I push this part in stack_b, sort them and put them back together
• function for more than five numbers - here I use Radix Sort: a sorting algorithm that doesn't compare the numbers, but sort them by distributing them in buckets according to their radix (base or unique digits, e.g. 0 through 9 in the decimal system or 0 and 1 in the binary numeral system)
  • adding an index to the nodes, this is necessary with Radix Sort since it's only working with positive numbers
  • coding a while in a while, adding the binary comparison to it and sending all the numbers where the result after the comparison with 1 is 0 to the stack_b and rotate the others in stack_a, after having seen all the numbers, putting back the nodes from stack_b to stack_a, after the while the same operation will take place with the second unique digit, thus bit_pos *= 2;, exit condition is the sorted list
• free the allocated memory before the exits

Result

Examples with push swap visualizer

With 5 numbers:

With 100 numbers:

With 500 numbers:

Big O Notation of Radix Sort is O(k * (b + n)), where k stands for the digits of the biggest number, b for the base and n for the amount of numbers. Overall, it has a very good performance because the algorithm is only called k times

Tips for 42 students

• this project is perfect if you want to deepen your understanding about linked lists, if you want to refresh your knowledge about linked lists, I recommand this video from the CS50 cours
• during my research, I found this beautiful video on youtube which is gold for the general introduction to sorting algorithms (https://www.youtube.com/watch?v=WaNLJf8xzC4), although they don't cover Radix Sort and Divide and Conquer
• if you want to generate random numbers to test your code, you can use the cmd jot -r 100 -100 100 or the string version jot -r -s " " 100 -100 100 in the terminal

What I learned

The "push_swap" project was an excellent opportunity for me to learn about different sorting algorithms, data structures, and the importance of optimizing code for efficiency. Between the different sorting algorithms, I opted for the radix sort, because I have never heard of it before and I was intrigued to understand how it works. Its performance characteristics are lower than another popular algorithm, which is a combination of quick and merge sort, but it sorts in an interesting way. I simply found the algorithm neat.

Additionally, the "push_swap" project emphasized the significance of selecting the appropriate data structure for a given problem. As stated in the subject, I had to implement two stacks and I chose to do so using two simply linked lists because I found it to be the most logical option since we only have the limited set of operations mentioned above.