250503 6일차

어제 완성 못한 퀵 솔트를 다 지우고 다시 기억하면서 구현해보았다

조건
1. 양끝, 리스트 중앙 값을 정렬하고 양끝, 피봇도 끝에 배치
2. 양쪽부터 피봇기준 왼쪽은 작은값, 오른쪽은 큰값으로 스왑
3. 포인터가 서로 교차시 피봇보다 큰값 leftPointer 와 피봇과 스왑
4. 피봇 기준 양쪽을 스택에 푸시
5. 반복
+피봇

조건이 정리되자 
하나하나 안보이던것이 보였다
3개 정렬한것중 큰값도 가장크다는것을 보장 못하잖아??
피봇을 최우측에 두고 lp rp pivot 순으로 배치하여 제작하니 훨신 쉬웠다.
분명 책에서는 피봇이 맨끝 -1값에 있었는데 왜 rp를 최우측에 뒀는지 모르겠다
그러다 보기가 너무힘들어서  디버그용 출력 함수를 만들고 단계를 보면서 구현하였다
그러다보니 위에서 2개 이하일때를 따로 처리해줘야할것같아서 추가했다.

n Log n에 근접한 모습  
상수값이 1.3~ 이라던데 아무래도 비교횟수만 측정해서 낮게 나온듯하다

병합정렬 
재귀방식은 그래도 1시간정도걸린것같은데
재귀없이하려니까 총 6시간걸림
그래도 퀵솔트는 이해가 갔는데
병합정렬은 알듯말듯 이해가 안되버리니까 미쳐버리겠다..
연산횟수는 적어보이는데 100만번으로 하면 퀵소트보다 속도가 느리다. (복사오버헤드)

힙정렬

시간이 늦어서 간단히 이론만 복기함


1. 최대힙 만들기
2. 최대노드 끝과 스왑
3. 나머지 다시 최대힙

 

내일도 코딩위주로 해볼예정. 병합처음부터 다시해보는것도 좋을듯