1  /* ************************************************************************** */
 2  /*                                                                            */
 3  /*                                                        :::      ::::::::   */
 4  /*   so_greedy_sort.c                                   :+:      :+:    :+:   */
 5  /*                                                    +:+ +:+         +:+     */
 6  /*   By: gychoi <gychoi@student.42seoul.kr>         +#+  +:+       +#+        */
 7  /*                                                +#+#+#+#+#+   +#+           */
 8  /*   Created: 2022/11/20 16:09:43 by gychoi            #+#    #+#             */
 9  /*   Updated: 2022/12/08 16:29:31 by gychoi           ###   ########.fr       */
10  /*                                                                            */
11  /* ************************************************************************** */
12  
13  #include "push_swap.h"
14  
15  static void	rotate_both(t_deque *deque_a, t_deque *deque_b, int *ia, int *ib)
16  {
17  	while (*ia > 0 && *ib > 0)
18  	{
19  		rr(deque_a, deque_b);
20  		*ia = *ia - 1;
21  		*ib = *ib - 1;
22  	}
23  	while (*ia < 0 && *ib < 0)
24  	{
25  		rrr(deque_a, deque_b);
26  		*ia = *ia + 1;
27  		*ib = *ib + 1;
28  	}
29  }
30  
31  static void	rotate_deque_a(t_deque *deque_a, int index)
32  {
33  	if (index > 0)
34  	{
35  		while (index--)
36  			ra(deque_a);
37  	}
38  	else
39  	{
40  		index *= -1;
41  		while (index--)
42  			rra(deque_a);
43  	}
44  }
45  
46  static void	rotate_deque_b(t_deque *deque_b, int index)
47  {
48  	if (index > 0)
49  	{
50  		while (index--)
51  			rb(deque_b);
52  	}
53  	else
54  	{
55  		index *= -1;
56  		while (index--)
57  			rrb(deque_b);
58  	}
59  }
60  
61  void	greedy_sort(t_deque *deque_a, t_deque *deque_b)
62  {
63  	int	ia;
64  	int	ib;
65  
66  	while (deque_b->size)
67  	{
68  		ia = 0;
69  		ib = 0;
70  		find_index(deque_a, deque_b, &ia, &ib);
71  		rotate_both(deque_a, deque_b, &ia, &ib);
72  		rotate_deque_a(deque_a, ia);
73  		rotate_deque_b(deque_b, ib);
74  		pa(deque_a, deque_b);
75  	}
76  }
77  
78  void	sort(int *array, t_deque *deque_a, t_deque *deque_b)
79  {
80  	int	size;
81  	int	p_a;
82  	int	p_b;
83  
84  	size = deque_a->size;
85  	array_sort(array, size);
86  	p_a = array[size * 1 / 3];
87  	p_b = array[size * 2 / 3];
88  	if (size <= 5)
89  		sort_small(deque_a, deque_b, size);
90  	else
91  	{
92  		deque_partition(deque_a, deque_b, p_a, p_b);
93  		greedy_sort(deque_a, deque_b);
94  		sort_finalize(deque_a);
95  	}
96  }