퀵정렬 검색 결과

해당 글 3건
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
퀵 정렬 평균 시간 복잡도 : 왜 O(nlogn)일까?

평균적으로 퀵 정렬은 머지보다, 빠른 것으로 알려져 있습니다. 물론 최악의 경우에, skew만 계속 일어나면, 별로 좋지는 않겠지만요. 이건 왜 그럴까요? 머지에 비해서 Quick은 추가적인 공간을 쓰지 않기 때문에 그렇습니다. 사실, 이게 제일 큰 요인입니다. 이것이 어떻게 동작하는지 이해가 가지 않으시다면, 관련 글을 보고 오시는 것도 좋겠습니다. [관련글] 퀵 정렬에 대해서 알아봅시다. 그러면 평균 복잡도는 왜 O(nlogn)일까요? 몇 가지 가정을 해 봅시다. partition이 일어날 때, arr[0]을 pivot으로 잡습니다. 이 때, 정렬을 할 데이터의 갯수가 n개라고 하면, arr[i]보다 작은 것의 갯수가 0개, 1개, 2개, ... , n-1개인 경우가 있을 거에요. 그러한 확률이 모두..
자료알고/알고리즘 2019. 8. 20. 16:18
퀵 정렬 : bad partition이 발생할 경우 문제가 된다.

퀵 정렬 알고리즘은 간단하게 언급만 하고 넘어가겠습니다. 사실, ps에서 그리 많이 쓰이는 정렬 방법은 아니기 때문입니다. 다만, 평균적으로는 병합 정렬보다는 빠른데, 그 이유는 다음 시간에 평균 복잡도를 분석하면서, 언급하도록 하겠습니다. 먼저 퀵 정렬은 피봇을 잡는 것부터 시작합니다. arr의 [s,e] 구간을 정렬한다고 하면, pivot을 선택해서, 그 피벗이 있는 위치와 arr[s]의 값을 교환합니다. 이는, 피봇을 선택하는 함수와, 그걸 토대로 divide 하는 것을 별개로 생각하기 위해서입니다. 여기서 저는 pivot을 5로 잡았습니다. 그리고, 우리는 2개의 포인터를 잡을 겁니다. 이는 각각 le와 ri 포인터입니다. 어떤 식으로 교환이 일어나는지만 보시면 되는데요. 우리는 ri 포인터가 s..
자료알고/알고리즘 2019. 8. 15. 12:12