median of median : 피벗을 중앙의 중앙값을 선택한다.
Quick sort, selection을 할 때 pivot을 선택하는 전략을 찾아보면 꽤 많이 나온다는 것을 알 수 있습니다. 이번 시간에는 median of median을 해 보도록 하겠습니다. 중간값의 중간값? sort 구현체를 찾아보면 Median of Median으로 하는 거 같지 않은데, 이건 또 왜 그럴까요? 중앙값부터 보겠습니다. [5, 3, 6, 4, 7]의 중앙값은 무엇인가요? 5입니다. 왜냐하면, 이것을 sort를 하면 [3, 4, 5, 6, 7]입니다. 5가 딱 중간에 있기 때문입니다. 크기가 n인 배열을 생각해 보겠습니다. 이것을 우리는 5등분을 하겠습니다. 예를 들어, 배열이 [2, 5, 3, 2, 7, 2, 7, 3, 6, 4, 7, 5, 7, 2, 3, 6, 6, 4, 35, ..
자료알고/알고리즘
2020. 7. 9. 21:44
최근댓글