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
|
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* sort.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/19 09:12:02 by cacharle #+# #+# */
/* Updated: 2020/01/22 08:55:55 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
#include "push_swap.h"
void stack_print(t_stack *stack)
{
printf("%s> ", stack->tag == STACK_A ? "A" : "B");
for (int i = 0; i <= stack->top; i++)
printf("%2d | ", stack->elements[i]);
printf("\n");
}
static int frame_length(t_stack *st, int frame_index)
{
return stack_length(st) - frame_index;
}
/*
** main : stack to sort
** tmp : temporary stack used to store pivot > values
** main_frame : main current sorting frame index
** (ignore values beyond a certain index,
** which bellong to previous recursions)
**
** store pivot value
** hide it at the bottom of the stack
** iterate over the current frame
** if < pivot, push it to tmp stack
** else, hide it with the pivot
** put all hidden elements on the top of the stack
** these form the new frame
**
** we have splitted the elements of the frame in upper and lower partition
** each of those will be sorted in the next recursion
*/
static void push_swap_qsort_partition(t_stack *main, t_stack *tmp, int main_frame)
{
int pivot;
int hidden_count;
int frame_len;
pivot = stack_peek(main);
stack_rotate_print(main);
hidden_count = 1;
frame_len = frame_length(main, main_frame) - 1;
while (frame_len > 0)
{
if (main->tag == STACK_A ? (stack_peek(main) < pivot) : (stack_peek(main) > pivot))
stack_push_to_print(main, tmp);
else
{
stack_rotate_print(main);
hidden_count++;
}
frame_len--;
}
while (hidden_count-- > 0)
stack_reverse_rotate_print(main);
}
/*
** main : final stack where all sorted values will be stored
** tmp : temporary stack use to during partitionning
** main_frame : main stack sorting frame
** tmp_frame : tmp stack sorting frame
**
** base condition : the current main frame contain 0 or 1 element
** sort current partition and get new main frame
** according to the new frame:
** sort the new partition
** sort the tmp stack
** push all elements of tmp on main
*/
static void push_swap_qsort_rec(t_stack *main, t_stack *tmp, int main_frame, int tmp_frame)
{
if (frame_length(main, main_frame) < 2)
return ;
push_swap_qsort_partition(main, tmp, main_frame);
push_swap_qsort_rec(tmp, main, tmp_frame, stack_length(main));
stack_push_to_print(main, tmp);
push_swap_qsort_rec(main, tmp, main_frame, stack_length(tmp));
stack_push_to_print(tmp, main);
int tmp_frame_len = frame_length(tmp, tmp_frame);
while (tmp_frame_len != 0)
{
stack_push_to_print(tmp, main);
tmp_frame_len--;
}
}
/*
** wrapper for push_swap_qsort_rec
*/
void push_swap_qsort(t_stack *a, t_stack *b)
{
push_swap_qsort_rec(a, b, 0, 0);
}
|
