Sorting algorithm written in C using 2 stacks. Sort numbers using the 2 stacks and return the sorted numbers in the first stack.
- You have 2 stacks named A and B.
- 500 random numbers, there should be no more than 5500 operations on average.
- The stack A contains a random amount of negative and/or positive numbers which cannot be duplicated.
- The stack B is empty.
- The goal is to sort in ascending order numbers into stack A with the minimum amount of operations.
- 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 stack B and put it at the top of stack A. Do nothing if stack B is empty.
- pb (push b): Take the first element at the top of stack A and put it at the top of stack 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.
- Group the numbers from smallest to largest into stack B, providing a rough initial sorting
- Split stack B in half. If a specified number is above the split, use rr/ra/rb else use rrr/rra/rrb
- Determin the number of operations to move any number from stack B into the correct position in stack A
- Determin the least number of operations from step 3 above
- Execute the operation
- Repeat step 3 until stack B is empty
- Rotate stack A until it is in the correct position from smallest to largest numbers
- Create the sorting algorithm based on the rules above.
- Create the 2 stacks, you can use arrays, linked list or any data structures.
- Create the operations required, ie. pa,pb,sa,sb... etc to manipulate your stacks in step 2 above.
- Take as a command line argument the numbers to use for sorting.
- Verify the command line arguments (numbers to sort), no duplicate numbers are allowed and they must be valid numbers.
- There can be no memory leaks or segmentation faults.
- The program will produce as an output the operations, pa,pb,sa,sb... etc.
- Create a checker that takes the output from step 7 and verifies stack A is sorted.
- You are not allowed to use the system printf, you must create and use your own.
- You are not allowed to use any libc function libraries, such as strlen, isdigit... etc. You must create your own.
- You must create a makefile that compiles your libc and printf as a library.
- You must create a makefile for your program and link your libraries from step 11 above.
- for loops, macros and global variables are forbidden
- Functions can only be 25 lines maximum and 80 columns long.
- Each .c file must only contain a maximum of 4 functions.
- All .h files must include guards and can only include prototypes.
In the root of the project, Compile the main program and checker
make all
Compile the checker
make bonus
Recompile the main program and checker
make re
Clean all object files
make clean
Clean all object files and programs executables
make fclean