22.04.26. push_swap - 정렬부 구현-5, a_stack 오름차순 정렬하기-3=> 정렬 알고리즘 검토, b_stack 내림차순 정렬하기

정렬 알고리즘을 검토할 차례였지만 번아웃이 와서 한동안 과제에 손을 대지 않았다. 대신 협업도구 jira툴 다루는 법, 산업현장에서 원하는 개발자 커리어 관리 등의 현직 개발자 분들이 해주시는 특강을 들으며 다시 열심히 해야지 하는 마음만 다지며 그동안 의욕엔 불탔지만 제대로 쉬지 않았던 지난날을 돌아보았다.

라이브로 멘토님과 함께 실습하며 진행되었던 jira 특강 / 앞으로의 프로젝트, 과제에서 열심히 적용해 봐야겠다.

하루에 과제하는 시간을 조금 제한하고, 대신 그 시간에 내게 필요한, 좀더 재밌게 할 수 있는 공부들을 해나갈 필요성을 깨달았다. 아침 일찍 클러스터에 나와 출퇴근 하듯이 하루 일과를 보내보려 한다. 평소 아침에 하던 운동도 저녁에 하는 걸로...!

지난 포스팅에서, 정렬이 제대로 이루어 지지 않고 있다는 것을 알게 되었고, 해당 부분을 디버깅 하기 시작했다.

먼저, 아직 정렬되지 않은 부분에 원래 위치해야하는 수(middle)가 이미 존재하는 경우, 아무 일도 하지 않고 넘기기 위해,

curr->index 값이 middle인 경우, unsorted된 덱값의 시작 index(덱)의 값을 1증가 시키고, 찾을 값인 middle 값도 1 증가 시킨이후에 정렬 작업을 반복 할수 있게 continue 명령을 내렸다.

오름차순 정렬이 되지 않던 stack_a

오름차순 정렬이 완료 된 stack_a

원인은 104 line의 if문안에서, 이미 k개 만큼의 숫자(이미 정렬된 부분)을 b스택으로 넘긴 상태에서 a_stack->count_nums에 접근해 다시 k개 만큼 뺀 값을 사용했기 때문이었고, 해당 부분을 logic에 맞게 다시 수정하였다.

 

중간에 한번 최적화를 하기 위해서, unsorted된 부분이 2개일 때, 좀더 명령어를 덜 쓸 수 있는 방법을 써보려고 한다.

위와 같은 경우, p_stack 관련 함수의 호출 수가 많아지기 때문이다.

unsorted 된 부분이 2개 남은 것을 k 값을 이용해서 알아내고, 이 경우에 약간의 하드코딩을 통해, 11개의 명령어에서 5개의 명령어 호출로 줄일 수 있었다.

다양한 갯수의 Input 값에 대하여, sort_astack 함수에 의해 스택 a가 오름차순 정렬되었음을 확인.

위와 유사하게 뒤에 많은 수가 남아있지 않은경우에 좀더 최적화(명령어 호출 수 최소화)를 할 수 있을 것 같다.

끝부분에 3개만 남았을 때, 4개, 5개에 대해서도 최적화를 진행 할 수 있을 것 같은데, 일단은 b_stack에서의 내림차순 정렬부터 구현하고, input 값에 따른 명령어 수를  확인 한 후, 필요에 따라 최적화 해보기로 한다.

 

먼저 b_stack을 내림차순 정렬하기에 앞서, a_stack을 모두 정렬하고 나서 b_stack을 정렬 할지, 둘을 동시에 정렬할지 결정해야 했다. 초기에 push_swap을 구상 할 때는 a_stack과 b_stack을 한번씩 번갈아가면서 정렬해서, 후에 명령어를 합치는 방법으로 최적화를 하려고 하였으나, a_stack을 정렬하면서 pb등과 같은 b_stack으로의 이동이 들어갔고 도중에 명령어를 버퍼에 저장하는 방식에서 그냥 바로 출력하는 방식으로 바꾸었기 때문에, a_stack을 모두 정렬한 후에 b_stack을 정렬하는것이 낫다는 생각이 들었다. 일단, a_stack 정렬이 끝난후 b_stack으로의 정렬을 시작하는 것으로 구현 하고, 최적화를 해도 과제에서 요구하는 명령어 호출 최소 수준을 만족할 수 없다면 그때 명령어를 저장해둘 버퍼 및 한번씩 번갈아 가며 정렬하는 것을 하려 한다.

 

b_stack 내림차순 정렬은 매우 간단하게 구현 할 수 있었다.

(좌) 내림차순 정렬전 b_stack / (우) 내림차순 정렬 후 b_stack

애초에 sort_astack 함수를 구현 할 때, middle값에서 1씩 늘려가면서 찾고 unsorted 노드 위치로 가져왔기 때문에, 동일한 logic 내에서 할 일은 명령어에 들어갈 스택 이름을 b스택으로 바꾸는 것과, middle값은 1씩 감소해가면서 정렬을 진행하는 것 밖에 없었다.

 

b_stack까지 정렬이 완료 되었다면, pa 명령어를 b_stack->counts 만큼 호출해, input으로 들어왔던 값들을 정렬된 상태대로 a_stack에 옮기는 것이다.

50개의 input이 a_stack에 모두 정렬된 모습

이로써 정렬은 완료 되었음을 확인 했다. 

이제 input으로 들어온 숫자의 갯수에 따라 사용한 명령어의 수를 토대로 최적화를 진행할 차례이다.