Taking baby-developer steps

22.05.04.push_swap - 정렬 알고리즘 최적화-4 본문

Logs/학습 log

22.05.04.push_swap - 정렬 알고리즘 최적화-4

Surin Lee 2022. 5. 4. 10:55

100개의 청크를 또 다시 구간을 나눠 정렬하는 것이 최적화에 도움이 되는 지를 보기 위해 sort_a_chunk함수(하나의 청크를 다시 구간 나누어 정렬하는 함수)를 구현하고 있다.

(좌) a_stack의 상태 (우)b_stack의 상태

먼저, 100개(100이상 200미만) 중 절반을 b스택의 top과 bottom으로 구간을 나누어 보냈다.

위 상태에서, sort_a_stack 함수를 이용해 a_stack에 있는 150~200까지를 오름차순으로 정렬했다.

sort_mid()함수를 변형해, 125~149까지를 b_stack에서 a_stack으로 가져오면서 정렬했다.

다시한번 sort_mid()변형 함수(앞으로 sort_mid_1이라고 하겠다.)로 101~124까지를 a_stack에 정렬했다.

ㄴ구간을 a_stack에 정렬 하기까지 1478개의 명령어를 사용했다.

switch_cunk 함수를 만들어 ㄱ(0~100), ㄴ구간(101~200까지 a_스택 기준, 오름차순 정렬된 구간)의 자리를 바꾸었고, 자리를 바꾸는데 410개의 명령어가 사용됬고, 현재까지 사용한 명령어 수는 1880이다.

이 상태에서 ㄱ구간을 sort_a_chunk(ㄱ구간은 더 작은 구간들로 나누어 정렬) 함수 호출을 통해 정렬하려고 했으나, sigfault가 발생했다. 

일단 sigfault가 발생하는 부분이 발생하지 않게끔 해당 함수들의 이름 뒤에 _temp 이름을 붙여 임시 함수들을 만들어 가면서, 일단 명령어의 소요량을 먼저 확인하기로 한다.

Comments