구현 알고리즘
- 배열에있는 값중 중간값을 찾아 피봇으로 사용하는 퀵소트를 구현
- 값들의 이동을 위한 명령어는 바로 출력되지않고 최적화를 위해 별도 저장공간에 저장됨
순서
- 중간값을 찾기위해 임의의 리스트에 정렬할 숫자들을 복사하고 임의로 정렬하여 중간값을 추출
- a스택에서 중간값을 기준으로 작은값은 a스택, 크거나 같은 값들은 b스택으로 보내주는 atob() 호출
- 정렬해야할 값이 2개 이하가 될 때 까지 atob를 재귀로 호출
- 정렬해야할 값이 2개 이하라면 atob재귀를 멈추고 해당 값을 정렬하고 함수를 나오며 btoa() 호출
- b스택에서 중간값을 기준으로 작은값은 a스택, 크거나 같은 값들은 b스택으로 보내줌 (btoa())
- 더이상 정렬할 값이 없을때까지 다시 2부터 반복
구현
int start_sort(t_deque *deq_a, t_deque *deq_b, t_deque *deq_str)
{
if (deq_a->first == deq_a->last)
return (0);
if (is_sorted(deq_a))
return (0);
else if (deq_a->size == 2)
do_sa(deq_a, deq_str);
else if (deq_a->size == 3)
sort_3(deq_a, deq_str);
else if (deq_a->size == 4)
sort_4(deq_a, deq_b, deq_str);
else if (deq_a->size == 5)
sort_5(deq_a, deq_b, deq_str);
else
atob(deq_a, deq_b, deq_str, deq_a->size);
return (0);
}
atob(a스택, b스택, 명령어를 저장할 스택, 정렬할 값의 갯수)
void atob(t_deque *deq_a , t_deque *deq_b, t_deque *deq_str, int r)
{
t_param param;
set_param(¶m);
if (r == 1)
do_ra(deq_a, deq_str);
else if (r == 2)
atob_2(deq_a, deq_str);
else
{
param.pivot = get_pivot(deq_a, r);
while (++param.i < r)
{
param.curr = deq_a->first;
if (param.curr->num < param.pivot)
param.ra += do_ra(deq_a, deq_str);
else
param.pb += do_pb(deq_a, deq_b, deq_str);
}
param.i = -1;
while (++param.i != param.ra && deq_a->do_first != 1)
do_rra(deq_a, deq_str);
deq_a->do_first = 0;
atob(deq_a, deq_b, deq_str, param.ra);
btoa(deq_a, deq_b, deq_str, param.pb);
}
}
void atob_2(t_deque *deq_a, t_deque *deq_str)
{
if (deq_a->first->num > deq_a->first->next->num)
do_sa(deq_a, deq_str);
do_ra(deq_a, deq_str);
do_ra(deq_a, deq_str);
}
btoa(a스택, b스택, 명령어를 저장할 스택, 정렬할 값의 수)
void btoa(t_deque *deq_a, t_deque *deq_b, t_deque *deq_str, int r)
{
t_param param;
set_param(¶m);
if (r == 1)
do_pa(deq_a, deq_b, deq_str);
else if (r == 2)
btoa_2(deq_a, deq_b, deq_str);
else
{
param.pivot = get_pivot(deq_b, r);
while (++param.i < r)
{
param.curr = deq_b->first;
if (param.curr->num >= param.pivot)
param.rb += do_rb(deq_b, deq_str);
else
param.pa += do_pa(deq_a, deq_b, deq_str);
}
param.i = -1;
while (++param.i != param.rb)
do_rrb(deq_b, deq_str);
atob(deq_a, deq_b, deq_str, param.pa);
btoa(deq_a, deq_b, deq_str, param.rb);
}
}
void btoa_2(t_deque *deq_a, t_deque *deq_b, t_deque *deq_str)
{
if (deq_b->first->num > deq_b->first->next->num)
do_sb(deq_b, deq_str);
do_pa(deq_a, deq_b, deq_str);
do_ra(deq_a, deq_str);
do_pa(deq_a, deq_b, deq_str);
do_ra(deq_a, deq_str);
}