push_swap 최적화

quick_sort의 처음 호출 시에 rrr미실행

rrr을 하는 이유는 기존에 스택에 들어있는 값들 때문에 실행을 하게 되는데 처음 quick sort호출 시에는 기존에 스택에 들어있는 값이 없기때문에 rrr을 실행하지 않아도 된다 단 이때는 정렬순서가 달라지기때문에 pivoting후 스택을 div하는 과정에서 위치가 달라져야한다
stack_b->top : 중앙값
stack_b->bottom : 가장 작은 값

명령어 목록 최적화

push_swap과제에서 사용할수 있는 명령어 중에는 stack_A와 stack_B를 동시에 조작할 수 있는 명령어들이 있다 이를 사용하면 명령어 갯수를 최적화 시킬 수 있다
1. 명령어들을 바로 출력시키지 않고 연결리스트에 저장해둔다
2. 정렬이 완전히 종료 된 후 연결리스트를 순회하면서 sa sb가 연달아 연결되있는 등 최적화를 할수 있는 부분들을 찾아 ss같이 최적화시켜준다

특정 size이하 일 경우 하드코딩으로 수동정렬

퀵 정렬의 특성상 size가 줄어들게 되면 정렬횟수가 늘어나게 된다 이때 해당하는 size를 하드코딩해주면 명령어 갯수가 유의미하게 줄어나는 모습을 볼 수 있다 단 특정 값 이상이 되었을 경우 quick sort를 사용하는 것이 더 적은 명령어 갯수를 출력하는 것을 볼 수 있다