퀵정렬

• Divide and Conquer paradigm 사용
  • Partitioning

    어떤 pivot이라고 하는 element를 기준으로

    왼쪽은 작거나 같은것 오른쪽은 같거나 큰것

    이것을 재귀로 호출

• 퀵 정렬은 pivot을 어떻게 잡느냐에 따라 성능에 영향을 미침.
• Soudo code

  QuickSort(A,p,r)

  If p<r // 배열의 크기가 2보다 큰동안 1이되면 종료

  q=Partion(A,p,r)

  QuickSort(A,p,q-1) //재귀

  QuickSotr(A,q+1,r) //재귀

     

• 퀵소트 수행시간
  • Θ(n) //파티셔닝은 몇번하느냐에 따라 성능 달라짐
  • 크게 두가지 경우
    • balanced 파티셔닝 : 각 하위 문제의 크기가 절반정도가 될 경우

      O(nlgn)

    • unbalanced 파티셔닝 :
• 최악의 시간
  • Subtitution

     

• 최악의 경우를 피하기 위해 배열에서 pivot을 무작위로 선택