• Quicksort 퀵정렬

  • A[p..r]를 정렬하는 과정

    • Partition을 이용해 나눈다.

      • 파티션함수는 pivot을 정하고 pivot을 기준으로 pivot보다 작거나 같은 값을 1번째 구간에, pivot보다 큰 값을 2번째 구간에 정렬하고 다 정렬했으면, 이 두 구간사이에 pivot이 위치하게 된다.

      

      • unrestricted 구간은 아직 정렬이 되지 않은 구간이다.

      • 파티션 함수 내용

        

        • A[r] = x 을 pivot으로 설정하고, j가 맨처음 인덱스부터 시작하여 비교하면서 x보다 작거나 같으면 i를 증가시키고, j와 바꿈 / 만약 더 크다면 j만 증가시킴
          • 반복이 다끝난 후, x를 구간 사이에 위치시킴

      • Loop invariant 루프 불변속성

        

      • 파티션의 시간복잡도 : O(n)

        • worst case : 언밸런스하게 sub array(구간)이 나뉘어 졌을때(0/n-1처럼) (한쪽 루프를 더 깊게(n만큼) 들어가기 때문에) ⇒ n *Θ(n) = Θ(n^2)

        • best case : 밸런스하게 나뉘어졌을때 n/2, n/2+1 처럼

        • 일반적인 케이스의 계산

          • 밸런싱된 파티셔닝

          

          

        비율이 100:0 만 아니면, height가 logn형식으로 나오기때문에

        시간복잡도는 O(nlgn)이 된다.

        • pivot을 맨처음값, 랜덤한 위치에 있는 값으로 해도 시간복잡도는 O(nlgn)이 된다.

• Q&A

5번같이 T(n/2)앞에 2^n이 달려있는 것과 같이 우리에게 친숙하지 않은 형태라면, 양변을 2^n으로 나눠주고 2^-n T(n) 을 다른 새로운 함수 T’(n)으로 치환해서 풀어준다

• 우리에게 친숙한 형태이기에 마스터이론으로 풀 수 있다!

7번은 다음과 같이 바꿀 수 있음

n이 커질수록 상황을 봐야함 → cos은 -1과 1 사이의 값이므로 작은 상수값으로 치부해도 됌

• pivot은 왼쪽으로는 자기보다 작고, 오른쪽으론 자기보다 다 커야됌!!!!!!