Skip to content

42 Project about sorting algorithms. 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.

Notifications You must be signed in to change notification settings

liz753/push_swap

Folders and files

NameName
Last commit message
Last commit date

Latest commit

1fe1f64 · Jun 15, 2023

History

11 Commits
Mar 7, 2023
May 1, 2023
Jun 15, 2023
May 1, 2023
May 1, 2023
May 1, 2023
May 1, 2023
May 1, 2023
May 1, 2023
May 1, 2023
May 1, 2023
May 1, 2023
May 1, 2023
May 1, 2023
May 1, 2023
May 1, 2023
May 1, 2023

Repository files navigation

push_swap with Radix Sort

42 Project about sorting algorithms.

Table of Contents

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:

5swap (1)

With 100 numbers:

swap100 (1)

With 500 numbers:
swap500 (1) (1)

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.

About

42 Project about sorting algorithms. 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.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published