This project involves sorting data on a stack, with a limited set of instructions, and the smallest number of moves. To make this happen, you will have to manipulate various sorting algorithms and choose the most appropriate solution(s) for optimized data sorting.
The 42 curriculum asks us to code according to the Norme
, this standard forbids us certain control structures (like do while
, for
, ...), a limit of 25 lines and 5 variables per function, 5 function max per .c
and and other constraints.
This project has been coded according to the NormeV3
standard.
NormeV3 PDF used in this projetc
typedef struct s_stack
{
//stack a
int *a;
//stack b
int *b;
//actual used space
int len_a;
int len_b;
} t_stack;
typedef struct s_data
{
//stack struct
t_stack stack;
//array with all arg
int *set;
//array with all the arg sovle
int *solve;
//tmp ptr for special case
void *tmp;
//copy of `ac` arg of main
int ac;
} t_data;
-
Store input
- alloc
struct.set
sizeof(int) * av - char to int
- check if av[x] ≥
INT_MAX
|| ≤INT_MIN
- check if there is no repetition
- alloc
-
Solve
struct.set
- copy
struct.set
instruct.solve
- use sort algorithms depend the case
- solve
struct.solve
- copy
-
Init stack
a
b
struct.stack
alloc sizeof(int) * (av * 2)- use
struct.solve
index to hashstruct.set
ina
struct.sep
= first index ofb
struct.len
=av
struct.set [12][4][-4][12312][-44444] struct.solve [-44444][-4][4][12][12312] index [0] [1] [2][3] [4] struct.stack [3][2][1][4][0] [ ][ ][ ][ ][ ] ^-----------^ ^-----------^ [ a ] | [ b ] [ Sep ]
-
NB
How to read arrow.
[Turn]-----: v v .----------: :---> [End] ^ | | [Start] :----------:
sa : swap a
- intervertit les 2 premiers éléments au sommet de la pile a. Ne fait rien s’il n’y en a qu’un ou aucun.
[ A ] | [ A ] :>[1].: | [2] :.[2]<: | [1] [3] | [3]
sb : swap b
- intervertit les 2 premiers éléments au sommet de la pile b. Ne fait rien s’il n’y en a qu’un ou aucun.
[ B ] | [ B ] :>[A].: | [B] :.[B]<: | [A] [C] | [C]
ss : sa et sb en même temps.
[ A ] [ B ] | [ A ] [ B ] :>[1].: :>[A].: | [2] [B] :.[2]<: :.[B]<: | [1] [A] [3] [C] | [3] [C]
pa : push a
- prend le premier élément au sommet de b et le met sur a. Ne fait rien si b est vide.
[ A ] [ B ] | [ A ] [ B ] [ ]<---.[A] | [A] [B] [ ] [B] | [ ] [C] [ ] [C] | [ ] [ ]
pb : push b
- prend le premier élément au sommet de a et le met sur b. Ne fait rien si a est vide.
[ A ] [ B ] | [ A ] [ B ] [1].--->[ ] | [2] [1] [2] [ ] | [3] [ ] [3] [ ] | [ ] [ ]
ra : rotate a
- décale d’une position vers le haut tous les élements de la pile a. Le premier élément devient le dernier.
[ A ] | [ A ] :--.[1]<: | [2] | :>[2].: | [3] | :.[3]<: | [4] | :>[4].: | [5] | :.[5]<: | [6] :-->[6].: | [1]
rb : rotate b
- décale d’une position vers le haut tous les élements de la pile b. Le premier élément devient le dernier.
[ B ] | [ B ] :--.[A]<: | [B] | :>[B].: | [C] | :.[C] | [D] :-->[D] | [A] [ ] | [ ] [ ] | [ ]
rr : ra et rb en même temps.
[ A ] [ B ] | [ A ] [ B ] :--.[1]<: :--.[A]<: | [2] [B] | :>[2].: | :>[B].: | [3] [C] | :.[3]<: | :.[C] | [4] [D] | :>[4].: :-->[D] | [5] [A] | :.[5]<: [ ] | [6] [ ] :-->[6].: [ ] | [1] [ ]
rra : reverse rotate a
- décale d’une position vers le bas tous les élements de la pile a. Le dernier élément devient le premier.
[ A ] | [ A ] :-->[1].: | [6] | :.[2]<: | [1] | :>[3].: | [2] | :.[4]<: | [3] | :>[5].: | [4] :--.[6]<: | [5]
rrb : reverse rotate b
- décale d’une position vers le bas tous les élements de la pile b. Le dernier élément devient le premier.
[ B ] | [ B ] :-->[A].: | [D] | :.[B]<: | [A] | :>[C] | [B] :--.[D] | [C] [ ] | [ ] [ ] | [ ]
rrr : rra et rrb en même temps.
[ A ] [ B ] | [ A ] [ B ] :-->[1].: :-->[A].: | [6] [D] | :.[2]<: | :.[B]<: | [1] [A] | :>[3].: | :>[C] | [2] [B] | :.[4]<: :--.[D] | [3] [C] | :>[5].: [ ] | [4] [ ] :--.[6]<: [ ] | [5] [ ]
I will push the first element in [a]
.
After i will find the preview index of data->b.mem[0]
.
#include <stdio.h>
#define PS_DEBUG 1
int get_pre_index(int index, int max)
{
if (index < 0 || index > max)
if (PS_DEBUG)
{
printf("get_pre_index(): Negatif index or > max !\n");
return (-1);
}
if (!index)
return (max - 1);
else
return (index - 1);
}
int main(void)
{
int ac = 12;
while (ac != 13)
{
printf("[%d]\n", ac);
ac = get_pre_index(ac, 24);
}
return (0);
}
When i have the index that i shearch, i will calculate how mutch ra
or rra
i need to put the shearch index at the firt place.
Then i push to B
.
This work is published under the terms of 42 Unlicense.