진행도
2022.02.22
- 개요
-
stack
스택을 구현하고 그것을 운영하는 함수들을 만들어야 하는 프로젝트로 보인다.
-
content
스택의 각 원소들은 int 형 컨텐츠와 이전 원소의 주소, 다음 원소의 주소를 보관하는 양방향 링크드 리스트 구조로 설계해야겠다.
이렇게 하면 스택과 원소를 분리할 수 없게 된다는 단점이 있다. 즉 하나의 원소를 여러개의 스택에 등록시키는 것이 불가능해진다.
-
iterator
스택위에서 움직이는 iterator을 만들어야 겠다. 진행방향 (reverse or straight)을 저장하고, 현재 원소 주소를 저장하는 구성이다.
iterator는 개념적으로 어떤 원소를 가르키고 있지 않고 원소와 원소 사이에 존재하는 개념이다. iterator의 now는 없고, before 과 next 만 존재한다.
예를 들어 next 의 index가 2일 경우 before 의 index는 1을 가리키고 있는 상태이고, iterator가 존재하는 위치는 1과 2 사이이다.iterator가 대상 stack의 종점에 도달한 뒤 next를 청구할 경우 NULL을 반환하도록 했다.
iterator에 정보를 청구할 때 iterator->version 대상 stack->version 을 비교하고 일치하지 않을 경우 NULL을 반환하도록 했다.
-
- 진행 상황 정리
- 각원소, 스택, iterator을 디자인하고 구현했다.
- iterator을 만들어 반환하는 함수 get_iterator_mind_null()을 구현했다.
- 여기서 mind_null은 반환값에 null이 올 수 있다는 의미이며, null일 경우 호출 함수에서 비상종료동작이 필요하다.
2022.02.27
- 구성개요
- utils.c
-
emergency_exit()을 만들었다.
해당 함수는 내부적으로 exit(1)을 실행하는 함수로 여러가지 에러 상황에 동적할당을 모두 해제하고 종료해주는 역할을 수행할 것이다.
-
check_input()을 계획중이다.
해당 함수는 main함수에 전달된 입력값의 유효성 검사에 사용될 함수이다.
-
- iterator_manipulation.c
-
iter_next_content()을 만들었다.
iterator을 인자로 받아 대상 스택의 다음 content를 반환해주는 함수이다. 또한 iterator의 표시 위치를 1 증가시킨다.
-
iter_retreat_content()을 만들었다.
iterator을 인자로 받아 대상 스택의 이전 content를 반환해주는 함수이다.
또한 iterator의 표시 위치를 1 거슬러 올라가게 한다.
-
- stack_push_pop.c
-
stack_pop_content()을 만들었다.
스택을 전달 받아 스택의 top에 있는 content를 인출해준다.
-
stack_pop_back_content()을 만들었다.
스택을 전달 받아 스택의 bottom에 있는 content를 인출해준다.
-
stack_push_content()를 만들었다.
스택과 원소를 전달 받아 스택의 top에 전달받은 원소를 등록해준다.
-
stack_push_back_content()를 만들었다.
스택과 원소를 전달 받아 스택의 bottom에 전달받은 원소를 등록해준다.
-
- utils.c
- 진행 상황 정리
- 각원소, 스택, iterator의 디자인을 일부 변경했다.
(version 기능 추가 등.) -
iterator을 만들어 반환하는 함수 get_iterator_mind_null()을 구현했다.
_mind_null의 기능이 exit()을 사용할 수 있게 되어 필요 없어졌다. 따라서 삭제했다. - emergency_exit()을 구현하고, stack의 push, push_back, pop, pop_back 함수를 구현했다.
- iterator 조작 함수를 구현했다.
- 각원소, 스택, iterator의 디자인을 일부 변경했다.
2022.02.28
- 진행개요
-
parse_input()을 디자인하고 있다.
위 함수의 기능은 main 함수에 들어오는 인풋을 해석하여 오류 여부를 판별하고, (오류면 emergency_exit()실행)
오류가 아니라면 입력들로 content를 만들고 stack에 먼저번 입력부터 push back하여 첫번째 입력이 top에 오도록 stack을 만들어 반환한다.
기능이 많아 parse_input_subsidiary() 를 하위함수로 두려고 한다. (static 함수) -
sorting 알고리즘 을 제외한 모든 기능의 구현을 완료했다.
-
2022.03.01
-
진행개요
끝냈다.
-
sorting 알고리즘은 merge sort 의 방식을 선택했다.
사용할 수 있는 자료공간이 2개의 스텍으로 제한되는 점을 고려해서 다들 quick sort를 선택하는 것 같은데 왠지 나는 다르게 하고싶고 나만의 방식으로 직접 모두 고민하고 부딪히고 싶어 merge sort를 고집했다.
머리가 깨질뻔했다. 알고리즘 아이디어 자체는 어렵지 않은데 두개의 스텍을 번갈아 오가며 정렬하는 실재를 구현하는게 상당히 복잡했다. (적어도 내가 생각하기엔…)여러번 segfault를 거치어 뼈대를 만들고 실행 명령 수를 줄이는 과정에 꼬박 10시간이 걸렸다.
아쉽게도 목표인 500개 입력을 5500개의 명령 이하로 통과하는 코드를 짜는 것은 오늘은 무리인것 같다.최적화도 여러군데에서 여러번 진행했다.
첫 번째 버전: 500개 6700회
두 번째 버전: 500개 6500회
세 번째 버전: 500개 6300회또한 오늘의 마지막인 네 번째 버전은 첫번째 배치 사이즈인 4개의 입력 이하의 입력에서 극도로 비효율적인 퍼포먼스를 보이는 것을 해결하고, 4개 5개 6개 까지의 입력에 대해 최적의 성능을 보일 수 있도록 수정하였다.
마무리는 눈에 넣어도 안 아플 내 새꾸 영상 
-
2022.03.03
- 진행개요
-
어제 평가에서 fail이 나왔다. 5개의 데이터가 입력되었을 때 명령어 12개 이하를 사용하는 일관된 퍼포먼스가 나오지 않아서이다.
이 부분에 대해 추가적인 하드코딩 작업을 하였다.
-
- 5개 입력에 대한 처리
- 5개의 입력이 들어 있는 stack 을 넘겨 받아 2번째로 작은 수를 찾아 반환하는 함수를 만들었다. (하단 function design 참고)
- 입력된 5개의 숫자 중 2번째로 작은 수를 찾는다. (명령실행 횟수 0)
- 2번째로 작은 수 보다 같거나 작은 수 (가장 작은수, 2번째로 작은 수) 2개를 RA를 수행하며 A를 회전시키며 찾는다. (명령 실행 횟수 +2~5)
발견시 PB 로 B stack으로 넘겨준다. - 위 동작이 끝난 후 A stack에 남은 3개의 숫자를 3개를 정렬하는데 특화된 함수를 사용해 정렬한다. (명령 실행 횟수 +0~2)
- B stack에 있는 2개의 숫자를 (top에서부터)내림차순이 되게끔 RB 를 사용한다. (명령 실행 횟수 +0~1)
- 이후 PA 2회 시행하면 A stack에 5개의 숫자가 오름차순 정렬 상태가 된다. (명령 실행 횟수 +2)
실행결과
실행결과 과제 요구사항에 맞는 12회 미만의 명령 사용을 보여준다.
- 5개의 입력이 들어 있는 stack 을 넘겨 받아 2번째로 작은 수를 찾아 반환하는 함수를 만들었다. (하단 function design 참고)
Design
Data Structures
typedef struct s_content
{
int content;
struct s_content *before;
struct s_content *next;
} t_content;
typedef struct s_stack
{
int quantity;
int version;
t_content *top;
t_content *bottom;
} t_stack;
typedef struct s_iterator
{
int direction;
int stack_version;
int next_index;
t_stack *stack;
t_content *next;
} t_iterator;
stack_push_content()
Code
t_stack *stack_push_content(t_stack *stack, t_content *content)
{
if (!stack || !content)
return (stack);
if (!(stack->bottom))
stack->bottom = content;
else
stack->top->next = content;
(stack->quantity)++;
(stack->version)++;
content->before = stack->top;
stack->top = content;
return (stack);
}
- 기능
- 세부
- 비어있는 stack을 전달받을 경우 stack->bottom에 content를 등록
- 비어있지 않은 stack을 전달 받은 경우 push 전 stack->top->next에 신규 content를 등록
- (공통) stack->quantity 1 증가
- 자매품
담을 stack과 content 1개를 인수로 받아 stack의 맨 위에 등록.
stack->version 1증가
content->before에 stack->top 을 등록
stack->top 에 content 등록
stack 반환
stack_push_back_content()
t_stack *stack_push_back_content(t_stack *stack, t_content *content)
{
if (!stack || !content)
return (stack);
if (!(stack->top))
stack->top = content;
else
stack->bottom->before = content;
(stack->quantity)++;
(stack->version)++;
content->next = stack->bottom;
stack->bottom = content;
return (stack);
}
stack_pop_content()
Code
t_content *stack_pop_content(t_stack *stack)
{
t_content *ret;
if (!stack->top)
return (NULL);
ret = stack->top;
stack->top = ret->before;
ret->before = NULL;
ret->next = NULL;
stack->quantity--;
(stack->version)++;
if (stack->before == NULL)
stack->bottom = NULL;
else
stack->top->next = NULL;
return (ret);
}
- 기능
- 세부
- 비어있는 stack을 전달받을 경우
- 비어있지 않은 stack을 전달 받을 경우
- stack->top 을 _ret_ 지역변수에 저장.
- stack->quantity 1감소
- stack->version 1증가
- stack->top 을 ret->before 으로 교체
- 새로운 stack->top == NULL 일 경우
- 새로운 stack->top != NULL 일 경우
- (공통)
- 자매품
content 를 추출할 stack을 인수로 받아 stack의 top 에 있는 content를 뽑아 반환.
NULL 을 반환
종료
stack->bottom 을 NULL 으로 변경
stack->top->next 을 NULL 으로 변경
ret->before 을 NULL 으로 초기화
ret 반환
stack_push_back_content()
t_content *stack_pop_back_content(t_stack *stack)
{
t_content *ret;
if (!stack->bottom)
return (NULL);
ret = stack->bottom;
stack->quantity--;
(stack->version)++;
stack->bottom = ret->next;
if (stack->bottom == NULL)
stack->top = NULL;
else
stack->bottom->before = NULL;
ret->next = NULL;
return (ret);
}
parse_input()
Code
t_stack *parse_input(int argc, char **argv)
{
char **arg_arr_2d;
int arr_2d_index;
long long parsed_integer;
t_stack *ret;
if (argc < 2)
exit(1);
ret = make_stack();
while (--argc > 0)
{
arr_2d_index = -1;
arg_arr_2d = ft_split(*(++argv), ' ');
while (arg_arr_2d[++arr_2d_index])
{
parsed_integer = ft_atoll(arg_arr_2d[arr_2d_index]);
if (parsed_integer == TYPE_PARSE_ERROR
|| !verify_unique(parsed_integer, ret))
emergency_exit();
stack_push_back_content(ret, make_content((int)parsed_integer));
}
clear_all_static(&arg_arr_2d);
}
return (ret);
}
부속 함수
static int verify_unique(int num, t_stack *stack)
{
t_content *cmp;
cmp = stack->top;
while (cmp)
{
if (num == cmp->content)
{
free_stack(&stack);
emergency_exit();
}
cmp = cmp->before;
}
return (1);
}
static void clear_all_static(char ***arr)
{
int index_out;
if (!arr || !(*arr))
return ;
index_out = -1;
while ((*arr)[++index_out])
free((*arr)[index_out]);
free(*arr);
*arr = NULL;
}
ft_split.c
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* ft_split_custom.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: chanhale <chanhale@student.42seoul.kr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2021/12/20 13:10:29 by chanhale #+# #+# */
/* Updated: 2022/03/03 22:10:36 by chanhale ### ########.fr */
/* */
/* ************************************************************************** */
#include "push_swap.h"
static size_t get_arr_size(char const *s, char c);
static char *make_elements(char const **s, char c);
static void emergency_exit_static(char **p, char **iter_p);
char **ft_split(char const *s, char c)
{
char **result;
char **iter_result;
char *element;
size_t arr_size;
if (s == NULL)
return (NULL);
arr_size = get_arr_size(s, c);
result = (char **)malloc(sizeof(char *) * arr_size);
if (result == NULL)
return (NULL);
iter_result = result;
while (--arr_size)
{
element = make_elements(&s, c);
if (element == NULL)
emergency_exit_static(result, iter_result);
if (element == NULL)
emergency_exit();
*(iter_result++) = element;
}
*iter_result = NULL;
return (result);
}
static size_t get_arr_size(char const *s, char c)
{
size_t result;
int flag;
result = 1;
flag = 0;
while (*s)
{
if (*s == c)
{
if (flag)
{
result++;
flag = 0;
}
}
else
flag = 1;
s++;
}
if (flag)
result++;
return (result);
}
static char *make_elements(char const **s, char c)
{
size_t size;
char *result;
char const *iter_s;
char *iter_result;
size = 1;
while (**s == c)
(*s)++;
iter_s = *s;
while (**s != c && **s != '\0' && size++)
(*s)++;
result = (char *)malloc(sizeof(char) * size);
if (result == NULL)
return (NULL);
iter_result = result;
while (*iter_s != c && *iter_s != '\0')
*(iter_result++) = *(iter_s++);
*iter_result = '\0';
return (result);
}
static void emergency_exit_static(char **p, char **iter_p)
{
if (*iter_p != NULL)
free(*iter_p);
if (*p == *iter_p)
{
free (p);
return ;
}
while ((*p) != --(*iter_p))
if (*iter_p != NULL)
free(*iter_p);
if (*iter_p != NULL)
free(*iter_p);
free (p);
}
ft_atoll.c
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* ft_atoll_custom.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: chanhale <chanhale@student.42seoul.kr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2021/12/29 10:41:01 by chanhale #+# #+# */
/* Updated: 2022/03/03 22:12:08 by chanhale ### ########.fr */
/* */
/* ************************************************************************** */
#include "push_swap.h"
static char *removespace(char *s);
long long ft_atoll(char *str)
{
long long counter;
long long minuscounter;
long long result;
result = 0;
counter = 0;
minuscounter = (long long) 1;
str = removespace(str);
if (str[counter] != '\0' && (str[counter] == '-'
|| str[counter] == '+'))
if (str[counter++] == '-')
minuscounter = (long long) -1;
while (str[counter] != '\0')
{
if (str[counter] < '0' || str[counter] > '9')
return (TYPE_PARSE_ERROR);
result *= (long long) 10;
result += (long long)((str[counter] - '0') * (minuscounter));
counter++;
if (2147483647 < result || result < -2147483648)
return (TYPE_PARSE_ERROR);
}
return (result);
}
static char *removespace(char *s)
{
int c;
c = 0;
while ((s[c] == '\t' || s[c] == '\n' || s[c] == '\v'
|| s[c] == '\f' || s[c] == '\r' || s[c] == ' ')
&& s[c] != '\0')
c++;
return (s + c);
}
- 기능
- 세부
- argc가 2 이상인지 확인 false -> exit(1)
- argv[1~]에 해당하는 문자열들 중 ascii '0' ~ '9' 또는 ' ' 가 아닌 입력이 있는지 확인 false -> emergency_exit()
- argv[1~]부터 모든 문자열을 ' '을 구분자로 ft_split()을 실행하여 2차원 배열을 생성.
- split된 문자열들을 atoll(atoi의 변형)함수를 통해 long long integer화 시킨다. atoll의 실행 중 범위 벗어난 입력을 확인시 -> TYPE_PARSE_ERROR(오류값) 반환
- atoll의 결과로 반환된 long long integer이 오류값이 아닐 경우 content 에 담고, stack에 push back atoll의 반환값이 TYPE_PARSE_ERROR일 경우 -> emergency_exit()
- 모든 입력이 parsing될 때까지 4, 5 실행.
- 완성된 stack 반환.
argc와 argv를 main 으로부터 전달받아 입력의 오류여부 판단, 입력을 contents로 만들고 stack에 push back하여 반환
iterator
Code
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* iterator_manipulation.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: chanhale <chanhale@student.42seoul.kr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2022/02/27 14:48:39 by chanhale #+# #+# */
/* Updated: 2022/03/01 22:51:22 by chanhale ### ########.fr */
/* */
/* ************************************************************************** */
#include "push_swap.h"
t_content *iter_next_content(t_iterator *iterator)
{
t_content *ret;
if (!iterator || iterator->stack_version != iterator->stack->version
|| iterator->next_index >= iterator->stack->quantity)
return (NULL);
ret = iterator->next;
(iterator->next_index)++;
if (iterator->direction == TYPE_STRAIGHT)
iterator->next = ret->before;
else
iterator->next = ret->next;
return (ret);
}
t_content *iter_retreat_content(t_iterator *iterator)
{
t_content *ret;
if (!iterator || iterator->stack_version != iterator->stack->version
|| iterator->next_index <= 0)
return (NULL);
(iterator->next_index)--;
if (iterator->direction == TYPE_STRAIGHT)
ret = iterator->next->next;
else
ret = iterator->next->before;
iterator->next = ret;
return (ret);
}
void free_iterator(t_iterator **iterator)
{
if (!iterator)
return ;
free(*iterator);
*iterator = NULL;
}
- 기능
- 상세
iterator의 기능은 다들 알 것이다.
iterator는 대상 stack이 변조되었을 경우 작동하는 것이 적절하지 않다.
따라서 이를 방지하기 위해 iterator 생성시 stack의 versioin을 저장하고
stack의 변조가 일어나는 push(back), pop(back) 연산시 stack의 version을 증가시키어
iterator에 정보를 청구할 때마다 stack의 version이 iter의 version과 동일한지 확인하는 절차를 거친다.
Merge Sort
Code
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* algorithm_merge.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: chanhale <chanhale@student.42seoul.kr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2022/02/28 16:08:09 by chanhale #+# #+# */
/* Updated: 2022/03/02 12:41:30 by chanhale ### ########.fr */
/* */
/* ************************************************************************** */
#include "push_swap.h"
static void merge_seq_b(t_stack *stack_a,
t_stack *stack_b, int n_a, int n_b);
static void merge_seq_no_rev(t_stack *stack_a, t_stack *stack_b);
static void merge_first_sequence(t_stack *stack_a, t_stack *stack_b)
{
int counter;
if (sort_tiny_case(stack_a, stack_b))
return ;
counter = stack_a->quantity / 4;
while (counter--)
{
if (stack_a->top->content < stack_a->top->before->content)
operator(stack_a, stack_b, TYPE_OP_SA);
operator(stack_a, stack_b, TYPE_OP_PB);
operator(stack_a, stack_b, TYPE_OP_PB);
if (counter % 2)
merge_seq_no_rev(stack_a, stack_b);
else
{
if (stack_a->top->content > stack_a->top->before->content)
operator(stack_a, stack_b, TYPE_OP_SA);
merge_seq_a(stack_a, stack_b, 2, 2);
}
}
if (stack_a->quantity % 2)
operator(stack_a, stack_b, TYPE_OP_PB);
if (stack_a->top->content > stack_a->top->before->content)
operator(stack_a, stack_b, TYPE_OP_SA);
merge_seq_b(stack_a, stack_b, stack_a->quantity % 4, stack_b->quantity % 4);
}
static void merge_seq_no_rev(t_stack *stack_a, t_stack *stack_b)
{
if (stack_a->top->content < stack_a->top->before->content)
operator(stack_a, stack_b, TYPE_OP_SA);
if (stack_a->top->content < stack_b->top->content)
{
operator(stack_a, stack_b, TYPE_OP_PB);
operator(stack_a, stack_b, TYPE_OP_PB);
return ;
}
operator(stack_a, stack_b, TYPE_OP_RB);
operator(stack_a, stack_b, TYPE_OP_PB);
if (stack_b->top->content > stack_b->top->before->content)
operator(stack_a, stack_b, TYPE_OP_SB);
if (stack_a->top->content < stack_b->bottom->content)
{
operator(stack_a, stack_b, TYPE_OP_RRB);
operator(stack_a, stack_b, TYPE_OP_PB);
}
else
{
operator(stack_a, stack_b, TYPE_OP_PB);
if (stack_b->top->content > stack_b->top->before->content)
operator(stack_a, stack_b, TYPE_OP_SB);
operator(stack_a, stack_b, TYPE_OP_RRB);
}
}
void merge_seq_a(t_stack *stack_a, t_stack *stack_b, int n_a, int n_b)
{
while (n_a && n_b)
{
if (stack_a->top->content > stack_b->top->content)
{
operator(stack_a, stack_b, TYPE_OP_PA);
operator(stack_a, stack_b, TYPE_OP_RA);
n_b--;
}
else
{
operator(stack_a, stack_b, TYPE_OP_RA);
n_a--;
}
}
while (n_a-- > 0)
operator(stack_a, stack_b, TYPE_OP_RA);
while (n_b-- > 0)
{
operator(stack_a, stack_b, TYPE_OP_PA);
operator(stack_a, stack_b, TYPE_OP_RA);
}
}
static void merge_seq_b(t_stack *stack_a,
t_stack *stack_b, int n_a, int n_b)
{
while (n_a && n_b)
{
if (stack_b->top->content > stack_a->top->content)
{
operator(stack_a, stack_b, TYPE_OP_PB);
operator(stack_a, stack_b, TYPE_OP_RB);
n_a--;
}
else
{
operator(stack_a, stack_b, TYPE_OP_RB);
n_b--;
}
}
while (n_b-- > 0)
operator(stack_a, stack_b, TYPE_OP_RB);
while (n_a-- > 0)
{
operator(stack_a, stack_b, TYPE_OP_PB);
operator(stack_a, stack_b, TYPE_OP_RB);
}
}
void merge_sort(t_stack *stack_a, t_stack *stack_b)
{
int block_size;
int seq_counter;
int total_quantity;
block_size = 2;
total_quantity = stack_a->quantity;
merge_first_sequence(stack_a, stack_b);
while (stack_b->quantity)
{
block_size *= 2;
seq_counter = total_quantity / (block_size * 2);
while (seq_counter-- > 0)
{
merge_seq_a(stack_a, stack_b, block_size, block_size);
if (seq_counter-- > 0)
merge_seq_b(stack_a, stack_b, block_size, block_size);
}
if ((total_quantity / (block_size * 2)) % 2)
merge_seq_b(stack_a, stack_b, stack_a->quantity
% (block_size * 2), stack_b->quantity % (block_size * 2));
else
merge_seq_a(stack_a, stack_b, stack_a->quantity
% (block_size * 2), stack_b->quantity % (block_size * 2));
}
}
Merge Util
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* algorithm_util.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: chanhale <chanhale@student.42seoul.kr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2022/03/01 01:29:21 by chanhale #+# #+# */
/* Updated: 2022/03/03 13:28:18 by chanhale ### ########.fr */
/* */
/* ************************************************************************** */
#include "push_swap.h"
static void sort_tiny_case_four(t_stack *stack_a, t_stack *stack_b);
static void sort_tiny_case_six(t_stack *stack_a, t_stack *stack_b);
int check_sorted(t_stack *stack, int is_it_reverse)
{
t_iterator *iter;
int former_content;
if (stack->quantity <= 1)
return (1);
if (is_it_reverse == TYPE_STRAIGHT)
iter = get_iterator(stack, TYPE_STRAIGHT);
else
iter = get_iterator(stack, TYPE_REVERSE);
former_content = iter_next_content(iter)->content;
while (iter->next)
{
if (former_content > iter->next->content)
{
free_iterator(&iter);
return (0);
}
former_content = iter_next_content(iter)->content;
}
free_iterator(&iter);
return (1);
}
int sort_tiny_case(t_stack *stack_a, t_stack *stack_b)
{
if (check_sorted(stack_a, TYPE_STRAIGHT))
return (1);
if (stack_a->quantity < 7)
{
if (stack_a->quantity == 2)
operator(stack_a, stack_b, TYPE_OP_SA);
else if (stack_a->quantity == 3)
sort_tiny_case_three(stack_a, stack_b);
else if (stack_a->quantity == 4)
sort_tiny_case_four(stack_a, stack_b);
else if (stack_a->quantity == 5)
sort_tiny_case_five(stack_a, stack_b);
else
{
while (stack_a->quantity > 3)
operator(stack_a, stack_b, TYPE_OP_PB);
sort_tiny_case_six(stack_a, stack_b);
}
return (1);
}
return (0);
}
void sort_tiny_case_three(t_stack *stack_a, t_stack *stack_b)
{
if (stack_a->top->content > stack_a->top->before->content)
{
if (!(stack_a->top->content > stack_a->bottom->content)
|| !(stack_a->top->before->content < stack_a->bottom->content))
{
operator(stack_a, stack_b, TYPE_OP_SA);
if (!check_sorted(stack_a, TYPE_STRAIGHT))
operator(stack_a, stack_b, TYPE_OP_RRA);
return ;
}
operator(stack_a, stack_b, TYPE_OP_RA);
return ;
}
else
{
operator(stack_a, stack_b, TYPE_OP_RRA);
if (stack_a->top->content > stack_a->top->before->content)
operator(stack_a, stack_b, TYPE_OP_SA);
}
}
static void sort_tiny_case_four(t_stack *stack_a, t_stack *stack_b)
{
while (stack_a->quantity > 3)
operator(stack_a, stack_b, TYPE_OP_PB);
if (!check_sorted(stack_a, TYPE_STRAIGHT))
sort_tiny_case_three(stack_a, stack_b);
operator(stack_a, stack_b, TYPE_OP_PA);
if (stack_a->top->content > stack_a->bottom->content)
operator(stack_a, stack_b, TYPE_OP_RA);
else
{
if (stack_a->top->content > stack_a->top->before->content)
operator(stack_a, stack_b, TYPE_OP_SA);
if (!check_sorted(stack_a, TYPE_STRAIGHT))
{
operator(stack_a, stack_b, TYPE_OP_RA);
operator(stack_a, stack_b, TYPE_OP_SA);
operator(stack_a, stack_b, TYPE_OP_RA);
operator(stack_a, stack_b, TYPE_OP_RA);
operator(stack_a, stack_b, TYPE_OP_RA);
}
}
}
static int sf_find_second_min(t_stack *stack)
{
int min;
int ret;
t_content *now;
now = stack->top;
min = now->content;
while (now->before)
{
if (min > now->before->content)
min = now->before->content;
now = now->before;
}
now = stack->top;
ret = now->content;
if (ret == min)
ret = now->before->content;
while (now->before)
{
if (ret > now->before->content && min < now->before->content)
ret = now->before->content;
now = now->before;
}
return (ret);
}
void sort_tiny_case_five(t_stack *stack_a, t_stack *stack_b)
{
int pivot;
pivot = sf_find_second_min(stack_a);
while (stack_a->quantity > 3)
{
if (stack_a->top->content <= pivot)
{
operator(stack_a, stack_b, TYPE_OP_PB);
}
else
operator(stack_a, stack_b, TYPE_OP_RA);
}
if (stack_b->top->content < stack_b->top->before->content)
operator(stack_a, stack_b, TYPE_OP_SB);
if (!check_sorted(stack_a, TYPE_STRAIGHT))
sort_tiny_case_three(stack_a, stack_b);
operator(stack_a, stack_b, TYPE_OP_PA);
operator(stack_a, stack_b, TYPE_OP_PA);
}
static void sort_tiny_case_six(t_stack *stack_a, t_stack *stack_b)
{
if (!check_sorted(stack_a, TYPE_STRAIGHT))
sort_tiny_case_three(stack_a, stack_b);
if (!check_sorted(stack_b, TYPE_STRAIGHT))
{
if (stack_b->top->content > stack_b->top->before->content)
{
if (!(stack_b->top->content > stack_b->bottom->content)
|| !(stack_b->top->before->content < stack_b->bottom->content))
{
operator(stack_a, stack_b, TYPE_OP_SB);
if (!check_sorted(stack_b, TYPE_STRAIGHT))
operator(stack_a, stack_b, TYPE_OP_RRB);
return ;
}
operator(stack_a, stack_b, TYPE_OP_RB);
return ;
}
else
{
operator(stack_a, stack_b, TYPE_OP_RRB);
if (stack_b->top->content > stack_b->top->before->content)
operator(stack_a, stack_b, TYPE_OP_SB);
}
}
merge_seq_a(stack_a, stack_b, 3, 3);
}
- 기능
- 상세
- stack_a에 들어있는 원소의 갯수를 확인하고 7개 미만의 경우 sort_tiny_case()를 호출하여 정렬하고 종료한다.
- 7개 이상의 원소가 있는 경우 merge sort를 시작한다.
- 첫번째 batch size 는 4이다.
1에서부터 시작할 경우 연산의 효율성이 좋지 않아 조정하였다. - stack_a와 stack_b에 각 배치사이즈 단위로 전체 배치개수의 절반가량을 넣어주고, 홀수개의 배치가 있거나 자투리가 있을 경우엔 관련 효율적인 연산이 이루어지도록 조율하는 알고리즘의 판단에 따라 대처한다.
- 배치 정렬및 분배의 시퀀스가 끝났다면 배치 사이즈를 2배로 증가시키고 각 stack top에 있는 정렬된 배치를 대상으로 merge를 실행한다. (당연히 merge의 과정은 정렬을 포함한다.)
- 상기 시퀀스에서 merge된 신생 배치의 삽입은 항상 stack_a에 먼저 행해진다. 이후 stack_b -> stack_a에 번갈아 삽입한다.
- 이렇게 배치의 크기가 전체 원소 갯수보다 많아질 때 stack_a에 모든 데이터가 정렬된상태로 들어있게되고 stack_b에는 아무 원소도 남아있지 않게된다.
정렬되지 않은 stack_a 와 비어있는 stack_b를 받아서 stack_a에 들어있는 데이터를 정렬하는 기능을 수행한다.
There are currently no comments on this article
Please be the first to add one below :)
내용에 대한 의견, 블로그 UI 개선, 잡담까지 모든 종류의 댓글 환영합니다!!