Intro
Push_swap is a highly efficient coding project, part of the 42 School curriculum. The project aims to sort data on a stack, with a limited set of instructions, using the lowest possible number of actions. The challenge is to devise an algorithm that can efficiently sort the data under these constraints. It's a fantastic exercise in problem-solving and algorithmic thinking.
Conditions and moves
The 42 push_swap project is all about sorting numbers using a set of specific rules. Here's what you need to know:
Sorting Objective: The main goal is to sort a bunch of numbers in ascending order.
Duplicated Numbers: You'll be dealing with numbers that can be repeated, making the sorting a bit trickier.
Limited Moves: You can only use a few moves to sort the numbers: sa (swap stack A), sb (swap stack B), ra (rotate stack A), rb (rotate stack B), rra (reverse rotate stack A), rrb (reverse rotate stack B), rr (rotate A & B), rrr (reverse rotate A & B), and ss (swap A & B).
Efficiency Matters: The fewer moves you use to sort the numbers, the better.
Code Rules: You have to follow the rules of the 42 school's coding standards. It's about writing clean and organized code.
Input Handling: Your program needs to be able to handle different kinds of input, like invalid numbers or weird characters.
Error Messages: If something goes wrong, your program should let the user know what's up.
Output Format: When the sorting is done, your program should tell the user what moves to make to get the numbers sorted.
Documenting Your Code: It's a good idea to explain how your code works so others can understand it easily.
Testing Your Code: You should try out your program with different sets of numbers to make sure it sorts them correctly.
Meeting Deadlines: You've got a deadline to finish the project, so managing your time well is important.
Individual Work: While you can talk to others about the project, you have to write your own code.
No Copying: Copying someone else's work is a big no-no. You've got to come up with your own solution.
Improving Efficiency: If you can find a way to sort the numbers faster, go for it!
Learning Opportunity: This project is a chance to learn more about sorting algorithms and coding in general.
Algo
To solve this, I have used Best move algorithm to sort the Stack A,
Calcul the average:
in this part you have calcul the average of the numbers in stack A, and if the number at the top of stack A less or equals the average push it to stack B, else rotate A
// Calcul the average
double cal_average(t_node *st)
{
double sum;
double i;
sum = 0;
i = 0;
while (st)
{
sum += st->val.nbr;
i++;
st = st->next;
}
return (sum / i);
}
// nbr <= avg ? (pb) : (ra)
void ft_algo1st(t_node **st_a, t_node **st_b)
{
double avg;
while (*st_a && (list_size(*st_a) > 5))
{
avg = cal_average(*st_a);
if ((double)((*st_a)->val.nbr) <= avg)
_push(st_b, st_a, "pb\n");
else
_rotate(st_a, "ra\n");
}
ft_sort5(st_a, st_b);
}
Find the number in Stack B, and its best friend in Stack A:
this is the most important part of the algorithm, you have to find the best closest 2 numbers from stack A and B, starting with the top number at stack B (top_b), and its friend in stack A should be greater, that's why we assume that this number it the max one in stack A (max_a), then try to find if there's any other less this max_a,
if all numbers are less than top_b, the tack the smallest number in A (min_a)
t_movedata find_mvs(t_node *a, t_node *b, int nbr) { t_movedata mvs; int mx; t_node *tmp; int tp; mx = find_maxnbr(a); tmp = a; ft_bzero(&mvs, sizeof(t_movedata)); mvs.moves_b = nbr; if (mx < nbr) { mvs.moves_a = find_minnbr(a); return (get_mvdata(&mvs, a, b), mvs); } while (tmp) { tp = tmp->val.nbr; if (tp > nbr && tp < mx) mx = tp; tmp = tmp->next; } mvs.moves_a = mx; return (get_mvdata(&mvs, a, b), mvs); }Calcul the move cost:
now we have to calculate the cost to put the 2 numbers at the top of the stacks to identify the best move and whether we will move those numbers or others, and to do this we need to know the index of each number and the size of each stack,
// calcul number of move to put number at the top of the stack
int _mv2topcost(int nbr, int n, t_node *st, t_movedata *m)
{
int i;
int size;
size = list_size(st);
i = 0;
while (st)
{
if (st->val.nbr == nbr)
{
i = st->val.index;
if (n == 1)
m->a_idx = i;
else
m->b_idx = i;
break ;
}
st = st->next;
}
if (i <= (size / 2))
return (i);
return (size - i);
}
void get_mvdata(t_movedata *mv, t_node *a, t_node *b)
{
set_index(a, b);
mv->cost = _mv2topcost(mv->moves_a, 1, a, mv);
mv->cost += _mv2topcost(mv->moves_b, 0, b, mv);
}
// ...
t_movedata cal_cost(t_node *a, t_node *b)
{
t_movedata mv;
t_movedata tmp;
t_node *tt;
mv = find_mvs(a, b, b->val.nbr);
tt = b;
while (b)
{
tmp = find_mvs(a, tt, b->val.nbr);
if (mv.cost > tmp.cost)
mv = tmp;
b = b->next;
}
return (mv);
}
Put numbers at the top
now all we need is to put the numbers at the top of its stack, then push the number from stack B to the top of stack A,
void putnbrs_up(t_node **a, t_node **b)
{
t_movedata mv;
mv = cal_cost(*a, *b);
set_sizes(*a, *b, &mv);
if (mv.a_idx <= (mv.a_size / 2) && mv.b_idx <= (mv.b_size / 2))
while (mv.a_idx != (*a)->val.index && mv.b_idx != (*b)->val.index)
_rr(a, b, false, "rr\n");
else if (mv.a_idx > (mv.a_size / 2) && mv.b_idx > (mv.b_size / 2))
while (mv.a_idx != (*a)->val.index && mv.b_idx != (*b)->val.index)
_rr(a, b, true, "rrr\n");
while (mv.a_idx != (*a)->val.index)
{
if (mv.a_idx <= (mv.a_size / 2))
_rotate(a, "ra\n");
else
_revrotate(a, "rra\n");
}
while (mv.b_idx != (*b)->val.index)
{
if (mv.b_idx <= (mv.b_size / 2))
_rotate(b, "rb\n");
else
_revrotate(b, "rrb\n");
}
_push(a, b, "pa\n");
}
you will keep doing this until stack B becomes empty, at this point all you need is to reverse-rotate A or rotate it to become sorted,
void _fsort(t_node **a)
{
int mx_i;
int size;
mx_i = get_max_index(*a);
size = list_size(*a);
while (!is_sorted(*a))
{
if (mx_i <= size / 2)
_rotate(a, "ra\n");
else
_revrotate(a, "rra\n");
}
}