diff options
Diffstat (limited to 'sorting.c')
| -rw-r--r-- | sorting.c | 225 |
1 files changed, 111 insertions, 114 deletions
@@ -6,144 +6,141 @@ /* By: dkaiser <dkaiser@student.42heilbronn.de +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2024/04/13 15:04:19 by dkaiser #+# #+# */ -/* Updated: 2024/04/17 15:48:53 by dkaiser ### ########.fr */ +/* Updated: 2024/04/24 10:58:02 by dkaiser ### ########.fr */ /* */ /* ************************************************************************** */ #include "libft/ft_printf.h" #include "push_swap.h" -static void presort(t_psdata *data) +static void presort(t_psdata *data) { - int size; - int pivot; - int max; + int size; + int pivot; + int max; - size = data->a->size; - pivot = size / 2; - max = data->a->stack[0]; - while (size--) - { - if (data->a->stack[0] < max) - { - run_command(data, PB); - if (data->b->stack[0] < pivot) - run_command(data, RB); - } - else - { - max = data->a->stack[0]; - run_command(data, RA); - } - } + size = data->a->size; + pivot = size / 2; + max = data->a->stack[0]; + while (size--) + { + if (data->a->stack[0] < max) + { + run_command(data, PB); + if (data->b->stack[0] < pivot) + run_command(data, RB); + } + else + { + max = data->a->stack[0]; + run_command(data, RA); + } + } } -static int calculate_score(t_psdata *data, int pos) +static int calculate_score(t_psdata *data, int pos) { - int moves_to_top; - int moves_to_spot; - int i; + int moves_to_top; + int moves_to_spot; + int i; - if (pos < (data->b->size + 1) / 2) - moves_to_top = pos; - else - moves_to_top = data->b->size - pos; - i = 0; - while (i < data->a->size && data->a->stack[i] > data->b->stack[pos]) - i++; - if (i < (data->a->size + 1) / 2) - moves_to_spot = 2 * i + 1; - else - moves_to_spot = 2 * ((data->a->size - i) + 1); - return moves_to_top + moves_to_spot; + if (pos < (data->b->size + 1) / 2) + moves_to_top = pos; + else + moves_to_top = data->b->size - pos; + i = 0; + while (i < data->a->size && data->a->stack[i] > data->b->stack[pos]) + i++; + if (i < (data->a->size + 1) / 2) + moves_to_spot = 2 * i + 1; + else + moves_to_spot = 2 * ((data->a->size - i) + 1); + return (moves_to_top + moves_to_spot); } - - -static void move_to_top(t_psdata *data, int idx) +static void move_to_top(t_psdata *data, int idx) { - if (idx < (data->b->size + 1) / 2) - { - while (--idx > 0) - run_command(data, RB); - } - else - { - idx = data->b->size - idx; - while (idx--) - run_command(data, RRB); - } + if (idx < (data->b->size + 1) / 2) + { + while (--idx > 0) + run_command(data, RB); + } + else + { + idx = data->b->size - idx; + while (idx--) + run_command(data, RRB); + } } -static void move_to_spot(t_psdata *data, int idx) +static void move_to_spot(t_psdata *data, int idx) { - int pos; - int i; + int pos; + int i; - pos = 0; - while (pos < data->a->size && data->b->stack[0] > data->a->stack[pos]) - pos++; - if (pos >= data->a->size) - { - move_to_top(data, idx); - run_command(data, PA); - run_command(data, RA); - } - else if (pos < (data->a->size + 1) / 2) - { - i = pos; - while (i--) - run_command(data, RA); - move_to_top(data, idx); - run_command(data, PA); - i = pos; - while (i--) - run_command(data, RRA); - } - else - { - i = data->a->size - pos; - while (i--) - run_command(data, RRA); - move_to_top(data, idx); - run_command(data, PA); - i = data->a->size - pos; - while (i--) - run_command(data, RA); - } + pos = 0; + while (pos < data->a->size && data->b->stack[0] > data->a->stack[pos]) + pos++; + if (pos >= data->a->size) + { + move_to_top(data, idx); + run_command(data, PA); + run_command(data, RA); + } + else if (pos < (data->a->size + 1) / 2) + { + i = pos; + while (i--) + run_command(data, RA); + move_to_top(data, idx); + run_command(data, PA); + i = pos; + while (i--) + run_command(data, RRA); + } + else + { + i = data->a->size - pos; + while (i--) + run_command(data, RRA); + move_to_top(data, idx); + run_command(data, PA); + i = data->a->size - pos; + while (i--) + run_command(data, RA); + } } -static void scoresort(t_psdata *data) +static void scoresort(t_psdata *data) { - int *scores; - int i; - int min_score; - - scores = malloc(sizeof(int) * data->b->size); - // Error if allocation fails - i = 0; - while (i < data->b->size) - { - scores[i] = calculate_score(data, i); - i++; - } - i = 0; - min_score = 0; - while (i < data->b->size) - { - if (scores[i] < scores[min_score]) - min_score = i; - i++; - } - move_to_spot(data, min_score); + int *scores; + int i; + int min_score; - free(scores); - if (data->b->size > 0) - scoresort(data); + scores = malloc(sizeof(int) * data->b->size); + // Error if allocation fails + i = 0; + while (i < data->b->size) + { + scores[i] = calculate_score(data, i); + i++; + } + i = 0; + min_score = 0; + while (i < data->b->size) + { + if (scores[i] < scores[min_score]) + min_score = i; + i++; + } + move_to_spot(data, min_score); + free(scores); + if (data->b->size > 0) + scoresort(data); } -void stack_sort(t_psdata *data) +void stack_sort(t_psdata *data) { - presort(data); - scoresort(data); + presort(data); + scoresort(data); } |