22.05.06.push_swap - 정렬 알고리즘 최적화-6

지난 포스팅에서 deapart_chunk 함수를 만들어, ㄷ 구간을 a_stack으로 분리해내었다. 

depart 이후 a,b 스택의 각각 일부

depart하는 함수 내에서 대략적으로 ㄷ을 정렬할 때 나눌 구간을 미리 나눠두면 명령어를 더 절약할 수도 있을 것 같다는 생각이 들었지만, 일단 sort_a_chunk 함수를 재활용 하기 위해 해당 작업은 하지 않았다. 후에 명령어를 다시 줄여야 한다면 그때 작업하기로 한다.

일단 depart까지 사용된 명령어는 3270개 이다. (이 단계에서 301개 명령어 소요)--------

 

다시 한번 sort_a_chunk 함수로 a_stack에 있는 ㄷ 구간을 정렬했다.

a_top이 201인것을 의도 했으나 의도한 바대로 가진 않았다. 일단은 정렬의 효율성을 보는것이 중요하므로

해당 부분을 체크해두고 넘어가도록 한다.

ㄷ구간의 정렬 까지는 4097개 명령어가 쓰였고, 정렬단계에서는 827개 명령어가 소요되었다.----

 

이제 정렬된 ㄷ 구간을 b스택으로, ㄹ~ㅁ구간을 a스택으로 보내는 swith_2 함수를 구현했다.

이 단계 까지 4594개의 명령어가 사용 되었고, 이 단계에서는 493개가 소요되었다 ----

 

이제 ㅁ구간은 다시 b_stack으로 옮기고, ㄹ 구간만 a스택에 남겨서 정렬하는것이 원래의 계획인데, 여기서 sort_a_stack을 써보면 어떨까 싶은 생각이 들어 먼저 시도해 봤다.

정렬은 잘 수행 되었고, 이 단계까지 9758개의 명령어가 사용되었다. --- 이 단계에서 명령어 5164개 소요 ---

역시나 명령어가 너무 많이 소요 되므로, 다시 분할해서 정렬을 해본다.

 

위에서, ㄹ~ㅁ구간을 모두 a스택으로 보내는 것 보다, 당장 정렬할 ㄹ구간만 보내는게 낫겠다는 판단이 들었다.

이에 따라 switch_2 함수를 수정했고,

위와 같이 보내려했는데, 오히려 ㅁ구간을 a스택으로 먼저 보내고, ㅁ구간은 명령어 사용이 더 적은 sort_b_stack으로 정렬하는것이 낫겠다는 아이디어가 떠올랐다.

ㅁ을 pa하는 과정까지 4494개 명령어가 소요되었다.

ㅁ구간을 a_stack에서 정렬하던 중 sort_mid  함수의 문제점을 발견했다.