퀵정렬

[익명(211.234)]

도대체 퀵소트에서 왼쪽이 더 깊은 경우가 왜 worst case인거예요... Heapify는 두 자식 중 큰 쪽으로 내려가는 연산이고, 내려가는 경로가 길수록 비교와 swap을 더 많이 하니까, 더 깊은 서브트리로 내려가는 게 최악이라는데 오른쪽도 깊으면 그게 더 worst case아닌가요...

[ㅆㅇㅆ(124.216)]

퀵소트는 왼쪽이 깊다가 아니라 한쪽에 몰릴수록 존나 느린거임

[ㅆㅇㅆ(124.216)]

즉 정당하게 배분될수록 빠르지만, 한쪽 배분이 더 많고, 한쪽이 적은 구조일경우 비효율적인거

[익명(211.234)]

정신나가서 헷갈렸네요.. 힙정렬입니당

[ㅆㅇㅆ(124.216)]

힙은 트리가 거의 균형이라 왼쪽이 더 깊고 이런 개념이 없음 Heapify는 그냥 큰 자식 따라 내려가는데 끝까지 내려가면 그게 worst임 방향이 아니라 얼마큼 내려가냐 문제 엘리베이터 생각해라

[루도그담당(211.246)]

덤으로 힙 정렬은 각 노드간의 분포가 주소 공간에서 재각각이라 공간 지역성 고려가 안되서 노드가 존나 많을수록 다른 정렬보다 쬐깐 느림

[익명(211.234)]

교수님께서 왼쪽이 깊은경우가 worst case라고 하시면서 리프노드 제외한 노드의 갯수가 (2^k) - 1 이 나오고 왼쪽이 깊어 나머지 리프 노드가 (2^k)/2 나오게 되면서 모든 노드의 갯수는 n이 되므로 k(level) = 2n/3이 나온다고 하셨던 것 같습니다...

[루도그담당(211.246)]

악 씨발 존나 어려워