Skip to content

an algorithm that sorts random numbers with a limited set of instructions

Notifications You must be signed in to change notification settings

idleira/push_swap

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

32 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

push_swap - @42Wolfsburg

"because swap_push isn’t as natural."

description

push_swap is a very simple and a highly straightforward algorithm project where we sort data.

we have at our disposal a set of integer values, 2 stacks, and a set of instructions to manipulate both stacks.

our gois to write a program in c called push_swap which calculates and displays on the standard output the smallest program that sorts the integers received as arguments.

this program is made up of solely push swap language instructions.

here are some resources i used:

sorting algorithms

push swap — a journey to find most efficient sorting algorithm

push_swap: the least amount of moves with two stacks

push_swap instructions

key instruction action
sa swap a swap the top two elements of stack a. if 1 or no elements - no action
sb swap b swap the top two elements of stack b. if 1 or no elements - no action
ss swap a & swap b sa and sb at the same time.
pa push a move the top element of stack b to the top of a. if b is empty - no action
pb push b move the top element of stack a to the top of b. if a is empty - no action
ra rotate a shift all elements of a up by 1, first element becomes the last
rb rotate b shift all elements of b up by 1, first element becomes the last
rr rotate a & rotate b ra and rb at the same time.
rra reverse rotate a shift all elements of a down by 1, last element becomes the first
rrb reverse rotate b shift all elements of b down by 1, last element becomes the first
rrr reverse rotate a + reverse rotate b rra and rrb at the same time

performance

i used a positional sorting algorithm, it sorts by index and position.

this algorithm is very efficient: its results are well below the limits that the push_swap evaluation imposes.

here you can see how it performs, thanks to this visualiser by Niimphu. push_swap 50 values

• to get full 5 points when working with 100 values, the list of instructions must be less than 700 (mine ranges from 550 to 640): push_swap 100 values

• to get full 5 points when working with 500 values, the list of instructions must be less than 5500 (mine ranges from 4500 to 5000): push_swap 500 values

usage

  1. clone this repository: git clone git@github.com:idleira/push_swap.git push_swap && cd push_swap

  2. compile the project with make

  3. give the algorithm a random amount of negative and/or positive numbers, which cannot be duplicated:

    ./push_swap 2 9 6 10 67

    → the output will look like this: pb pb ra pa rra pa, to visualize these operations use the visualizer (duh).

my final grade

push_swap grade 100/100

About

an algorithm that sorts random numbers with a limited set of instructions

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published