2022.04.19. push_swap - 정렬부 구현-4, a_stack 오름차순 정렬하기-2 => 정렬 알고리즘 검토

지난 포스팅에서 최종 정렬 결과 출력을 통해, 설계한 알고리즘이 의도한 정렬에 맞지 않는 다는 것을 확인했다.

더불어, 명령어 출력 최소화를 위해서, 불필요한 명령어를 줄이는 작업도 함께 진행 해보려고 한다.

현재 알고리즘에서는 middle 값이 t_node형 포인터인 unsorted가 가리키는 노드의 index 값인 경우에도, 이미 정렬 된 부분을 잠시 bstack에 넘기기 때문에, pb, pa 라는 2번의 명령어 사용이 발생하고, 이는 줄일 수 있는 비용이다.

이를 위해, 사용한 index i가 0이 아닌 경우 k번(sorted 된 원소의 갯수 만큼) pstack(pb)을 시행한다.

다시 pa가 될때도 동일하게 처리 했는데, 이때 이전에 null 노드가 do_* 관련 함수에 들어올 일 이 없게끔 설계하지 않았는데도 관련 예외처리를 해주지 않았을 때 sigfault가 발생했던 일이 생각났다.

그래서 혹시 이번 i =0인 인덱스 때문인가 하고 봤더니, n_times_pstack에 넘겨주는 index는 k 이므로, unsorted 노드의 index 이고, middle 값이 k와 얼마나 떨어져 있는지를 나타내는 sort_a_stack 함수에서의 index와는 별개 였다는 것을 확실히 알 수 있었다. 그래서 i == 0 일 경우 retrun 을 넣어줄 필요는 굳이 없어 보인다. 따라서 31, 32 라인은 다시 삭제 했다.

middle 값이 7일때 명령어를 출력하지 않는 모습(실제로 스택에도 아무 일 없이 k++ 된다)