반응형
PIVOT
-
알고리즘: Divide and conquer를 이용한 quick sort 구현 (feat. c++)알고리즘 2020. 9. 27. 11:27
이름은 빠른 정렬이지만 사실상 가장빠른 정렬 알고리즘이라고 할 수는 없다. 차라리 분할교환정렬(partition exchange sort)라고 하는게 더 정확하다. 이번 포스팅은 quick sort를 분할 정복으로 구현한다. 사실상 quick sort 분할정복구현에는 가중치가 분할 > 정복이다. 즉 정복에는 별거 없다. 하지만 분할과정이 까다롭다. quick sort를 분할 정복으로 다음과 같이 나눈다. 배열의 원소 중 하나를 pivot으로 잡는다. (어떤 값을 pivot으로 잡든 상관 없다. 단지 기준을 만들어주기 위함이다) 주로 배열의 가장 끝값이나 처음 값을 기준으로 잡는다. 예를 들어 다음과 같은 배열이 있다. array = { 6, 2, 5, 3, 7, 10..