-
Notifications
You must be signed in to change notification settings - Fork 0
/
insertion_sort.c
127 lines (119 loc) · 2.68 KB
/
insertion_sort.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* insertion_sort.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: akhossan <[email protected]> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/12/03 21:51:04 by akhossan #+# #+# */
/* Updated: 2019/12/03 21:51:16 by akhossan ### ########.fr */
/* */
/* ************************************************************************** */
#include "push_swap.h"
void get_min_value(t_stack *a, int *min, int *pos)
{
int i;
*min = INT_MAX;
i = 0;
while (a)
{
if (a->nbr < *min)
{
*min = a->nbr;
*pos = i;
}
a = a->next;
i++;
}
}
int invert_sort(t_checker *arg)
{
t_stack **a;
t_stack **b;
int i;
a = &(arg->a);
b = &(arg->b);
push(b, pop(a)->nbr);
disp_stack(*arg);printf("\n");
i = 0;
while (*a)
{
push(b, pop(a)->nbr);
rotate(b);
i += 2;
}
disp_stack(*arg);printf("\n");
while (*b)
{
push(a, pop(b)->nbr);
i++;
}
disp_stack(*arg);printf("\n");
return (i);
}
void insertion(t_checker *arg, int size)
{
int min;
int i;
int pos;
int b_items;
int j;
int actions;
t_stack **a;
t_stack **b;
int is_sort;
a = &(arg->a);
b = &(arg->b);
//Trivial fucking shit method *_*
i = 0;
pos = 0;
b_items = 0;
printf("size: %d\n", size);
actions = 0;
is_sort = is_sorted(*a);
if (!is_sort)
while (*a && size - 3 > 0)
{
get_min_value(*a, &min, &pos);
printf("min: %d\n", min);
printf("pos: %d\n", pos);
j = -1;
if (pos > (size - b_items) / 2)
while (++j < size - pos && ++actions)
rrotate(a);
else
while (++j < pos && ++actions)
rotate(a);
//printf("nbr: %d\n", (*a)->nbr);
//exit(1);
push(b, pop(a)->nbr);
++actions;
size--;
i++;
disp_stack(*arg);
printf("\n");
}
else if (is_sort == -1)
{
printf("inverted\n");
actions += invert_sort(arg);
}
else
return ;
printf("before pushing back to A\n");
/*
** simple insertion sort of 3 integers;
*/
if ((*a)->next->nbr < (*a)->nbr && ++actions)
ft_swap(*a);
int cmp = (*a)->next->next->nbr;
if (cmp < (*a)->next->nbr && ++actions)
{
ft_swap((*a)->next);
if (cmp < (*a)->nbr && ++actions)
ft_swap(*a);
}
while (*b && ++actions)
push(a, pop(b)->nbr);
printf("actions: %d\n", actions);
}