컴퓨터알고리즘#9

LeeMir, 14 April 2021

퀵 정렬


퀵 정렬
  • 분할통치법에 기초한 정렬 알고리즘
    • 기준 원소 p(pivot, 보통 마지막 원소)를 택해 리스트를 p보다 작은(LT), p와 같은(EQ), p보다 큰(GT) 부분으로 분할
    • 분할 후 각 분할된 집합을 정렬, 그리고 합병
  • 기준원소 선택
    • 결정적이며 쉬운 방법
      • 맨 앞, 맨 뒤, 중간
    • 결정적이며 조금 복잡한 방법
      • 맨 앞, 중간, 맨 뒤 위치의 세 원소의 중앙값
      • 0/4, 1/4, 2/4, 3/4, 4/4 위치 다섯 원소의 중앙값
      • 전체 원소의 중앙값
    • 기준원소의 선택에 따라 분할 결과 및 퀵 정렬 수행 성능에 영향을 미침
  • 퀵 정렬 트리
  • 시간복잡도
    • 최악의 경우
      • pivot을 고를 때마다 유일한 최댓값 / 최솟값일 경우
      • O(n^2)
    • LT와 GT의 크기가 모두 전체의 3/4보다 작은 것이 좋은 호출임
      • O(n log n)
무작위 퀵 정렬
  • 퀵 정렬의 결정적 버전에서는 pivot을 마지막 원소를 선택했음
  • 새로운 규칙 : 무작위 원소를 선택
제자리 퀵 정렬
  • pivot 선택 후 포인터 두 개를 리스트의 양쪽 끝에 생성
  • 왼쪽 포인터는 오른쪽으로, 오른쪽 포인터는 왼쪽으로 이동
  • 왼쪽 포인터는 pivot보다 큰 값을 만나면 그 곳에서 정지, 오른쪽 포인터는 pivot보다 작은 값을 만나면 그 곳에서 정지
    • 둘 다 정지하면 두 값을 교환 후 계속 진행
  • 두 포인터가 교차하면 정지 후 pivot에 가까운 원소가 pivot과 교환