Because Swap_push isn’t as natural
This project will make you sort data on a stack, with a limited set of moves, 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.
For more detailed information, look at the push_swap.subject.pdf
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:saandsbat 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:raandrbat 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:rraandrrbat the same time.
At the end, stack b must empty empty and all integers must be in stack a, sorted in ascending order.
The quicksort algorithm is a sorting algorithm that sorts a collection by choosing a pivot point, and partitioning the collection around the pivot, so that elements smaller than the pivot are before it, and elements larger than the pivot are after it. It recursively choose a pivot point and break down the collection until single-element lists, before combing them back together to form one sorted list.
Suppose we split the input into two “sections”, sorted and unsorted. The sorted section is initially empty. For each element in the unsorted section, we insert it into the sorted section, in its proper, sorted, position.
For example, you have the following array: var items = [5, 2, 6, 1, 3, 9];
To start, the 5 is placed into the sorted section. The 2 then becomes the value to place. Since 5 is greater than 2, the 5 shifts over to the right one spot, overwriting the 2. This frees up a new spot at the beginning of the sorted section into which the 2 can be placed. See the figure below for a visualization of this process (boxes in yellow are part of the sorted section, boxes in white are unsorted).
- Clone this repository:
https://github.com/linhtng/push_swap.git- Go to the project folder:
cd push_swap- To compile:
make- After compilation just run
push_swapwith your parameters. - Example of executing
push_swap:
./push_swap 8 13 20 17 19- Example of executing
checkerwith instructions received frompush_swap:
ARG="8 13 20 17 19"; ./push_swap $ARG | ./checker_Mac $ARGThis project was tested using push_swap_tester.
My push_swap algorithm in action visualized by O-reo's push_swap visualizer.