Implementing a sorting algorithm in C using stack data structure.
The goal of this project is to sort data on a stack, with a limited set of instructions, using the lowest possible number of actions. To succeed you'll have to manipulate various types of algorithms and choose the one (of many) most appropriate solution for an optimized data sorting.
- push_swap - calculates and displays on the standard output the smallest progam using
push_swapinstruction language that sorts integer arguments received.
push_swap is a solo project but we decided to work together to create our own algorithm.
But the implementation of the algorithm was done individually.
We acheived 125/100 on this project.
You can check both of our implementations here:
We thought creating our own algorithm to sort data would be a fun challenge. After a lot of trial and error we finally came up with a solution that works. The final verson of the algorithm is a many many iterations of the initial idea. We learned a lot about how to optimize code and how to use the stack data structure. This project helped us to improve our problem-solving skills, our ability to work in a team and algorithmical thinking.
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- 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. 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- 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- rra and rrb at the same time.
| Number of elements | Average result | Best result | Visual |
|---|---|---|---|
| 100 | 615 | 570 |  |
| 500 | 5100 | 4800 |  |
The algorithm is based on the idea of sorting the data in chunks. The size of the chunks is calculated based on the size of the stack.
Dividing of the stack for chunks :
| Size of stack | Chunksize | Number of chunks | Remaining nodes on stack A |
|---|---|---|---|
| 100 | 12 | 8 | 4 |
| 500 | 35 | 14 | 10 |
Remaining nodes on stack A: <10 nodes left to be sorted differently
For the rest of the other sizes of stack we use the following formula:
number of chunks = 10 % of stacksize
chunksize = stacksize / number of chunks
Sorting 3 numbers :
Only few combinations of possibilities exist for sorting 3 numbers.
We needed to sort any combination of 3 numbers in 2 moves.
Pseudo code for sorting 3 numbers:
if stack if size 2:
swap top two elements
else if first element is max:
rotate stack
else if second element is max:
reverse rotate stack
if first element is greater than second element:
swap top two elements
Sorting 5 numbers :
We needed to sort any combination of 5 numbers in 12 moves at most.
Pseudo code for sorting 5 numbers:
Find the smallest number and push it to stack B
Find the second smallest number and push it to stack B
Sort the stack A using the sorting algorithm for 3 numbers
Push the second smallest number to stack A
Push the smallest number to stack A
The algorithm is divided into two parts:
Sending chunks to stack B
Starting from the smallest chunk pair, APS tries to find lowest cost for the nodes of those chunks. APS makes three comparisons for the nodes of the chunks:
1. The cost of the node nearest to the top edge and the node nearest to the bottom edge for the first chunk.
2. The same for the second chunk.
3. The comparision between the least costly nodes from both chunks.
Now, APS has the least costly node to send to the stack B.
Based on the proximity of the node form either edge (North or South), APS either does
ra or rra to the node until it is at the top of stack A and can be pushed to stack B.
If in any of those cases it is possible to use the rr instruction, APS uses it.
APS repeats the above steps for each chunk pair until the last one.
For the last two chunks APS splits the chunks into two halves and sends the smaller numbers to the bottom of stack B and keeps larger numbers at the top.
Stack A has <10 numbers which are sorted using the sort 3 and sort 5 algorithms.
Now, APS has all the numbers in stack B chunked and is ready to send it back to stack A.
Sending nodes back to stack A
Sending back to stack A relies on the similar idea of the direction, cost and proximity of the nodes to the edge.
But with a key difference, the difference being that APS is now calculating the cost and the direction for the
biggest and the second biggest values in the stack B.
APS keeps track of the last sent node to stack A
- APS - Almighty Push Swap
- Stack - A stack of numbers.
- Node - A number in the stack.
- Stack A - The stack that contains the numbers to be sorted.
- Stack B - The stack that is used to sort the numbers.
- Chunk - A group of numbers that are sorted in ascending order.
- Chunk pair - Two chunks that are consecutively.
- Chunksize - The size of the chunk.
- Number of chunks - The number of chunks in the stack.
- Edges - The first and the last nodes of the stack being the edge.
- Direction - From the middle if the node is closer to the top, its North else its South.
- Cost - The cost of sending a node to the top of the stack and to the other stack.
- Clone the repo
git clone- Run make in the root directory
make- Run the program
./push_swap 1 2 3 4 5