정렬 알고리즘 - 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

 

• 고급 정렬 알고리즘(병합 정렬, 퀵 정렬, 힙 정렬) 중 하나
  
  
• 수행 방법
• 정렬할 전체 원소에 대해서 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법
• 왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분집합에는 기준 값보다 큰 원소들을 이동시킨다.
• 기준 값 피봇(Pivot)
  - 일반적으로 전체 원소 중에서 가운데(n/2)에 위치한 원소를 선택한다.
  
  
• 퀵 정렬은 다음 두 가지 기본 작업을 반복 수행하여 완성한다.
• 분할(Divide)
  - 정렬할 자료들을 기준 값을 중심으로 2개의 부분 집합으로 분할하기
  
  
• 정복(Conquer)
  - 부분 집합의 원소들 중에서 기준 값보다 작은 원소들은 왼쪽 부분 집합으로 기준 값보다 큰 원소들은 오른쪽
      부분 집합으로 정렬하기
  - 부분 집합의 크기가 1 이하로 충분히 작지 않으면 순환호출을 이용하여 다시 분할

 

• 퀵 정렬 수행 과정
• 정렬되지 않은 [69, 10, 30, 2, 16, 8, 31, 22]의 자료들을 퀵 정렬 방법으로 정렬하는 과정을 살펴보자.
• 원소의 개수가 8개이므로 네 번째 자리에  있는 원소 2를 첫 번째 피봇으로 선택하고 퀵 정렬 시작.
  
  1. 원소 2를 피봇(Pivot)으로 선택하고, 퀵 정렬을 시작

• L 이 오른쪽으로 이동을 하면서 피봇(Pivot)보다 크거나 같은 원소를 찾고, R 은 왼쪽으로 이동을 하면서 피봇(Pivot)보다 작은 원소를 찾는다.
• L 은 원소 69를 찾았지만, R 은 피봇(Pivot)보다 작은 원소를 찾지 못한 체로 원소 69에서 L과 만나게 된다.
• L 과 R 이 만났으므로, 원소 69를 피봇(Pivot)과 교환하여 피봇(Pivot) 원소 2의 위치를 확정한다.
  ( L 과 R 이 겹치면, 피봇(Pivot)원소 와 맞교환 )

 

2. 피봇(Pivot) 2의 왼쪽 부분 집합은 공집합이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합에 대해서 퀵 정렬을 수행 한다.

오른쪽 부분 집합의 원소가 7개 이므로 가운데 있는 원소 16을 피봇(Pivot)으로 선택 한다.

 

• 현재 위치에서 L 과 R의 작업을 반복한다.
• L 은 원소 69를 찾았지만, R 은 피봇(Pivot)보다 작은 원소를 찾지 못한 채로 원소 69에서 L 과 만나게 된다. L 과 R 이 만났으므로, 원소 69를 피봇(Pivot)과 교환하여 피봇(Pivot) 원소 16의 위치를 확정한다.

 

3. 피봇(Pivot) 16의 왼쪽 부분 집합에서 원소 10을 피봇(Pivot)으로 선택하여 퀵 정렬 수행한다.

 

• L 의 원소 10의 R 의 원소 8을 교환하는데, L 의 원소가 피봇(Pivot)이므로 피봇(Pivot) 원소 10의 위치가 확정된다.

 

       4. 피봇(Pivot) 10의 왼쪽 부분 집합의 원소가 한 개이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합은 공집합이므로 역시

퀵 정렬을 수행하지 않는다.

이제 1 단계의 피봇(Pivot) 이었던 원소 16의 오른쪽 부분 집합에 대해 퀵 정렬을 수행한다.

오른쪽 부분 집합의 원소가 4개이므로 원소 30을 피봇(Pivot)으로 선택한다.

 

• L 이 찾은 69를 R 이 찾은 22와 서로 교환한다.

• 현재 위치에서 L 과 R 의 작업을 반복한다.
• L 은 오른쪽으로 이동하면서 피봇(Pivot)보다 크거나 같은 원소인 30을 찾고, R 은 왼쪽으로 이동하면서 피봇(Pivot)보다 작은 원소를 찾다가 못 찾고 원소 30에서 L 과 만난다.
• L 과 R 이 만났으므로 피봇(Pivot)과 교환하는데 R의 원소가 피봇(Pivot)이므로 결국 제 자리가 확정된다.

 

5. 피봇 30의 왼쪽 부분 집합의 원소가 한 개 이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합에 대해서 퀵 정렬을 수행한다.

오른쪽 부분 집합의 원소 2개 중에서 원소 31을 피봇(Pivot)으로 선택한다.

 

• L 은 오른쪽으로 이동하면서 원소 31을 찾고, R 은 왼쪽으로 이동하면서 피봇(Pivot)보다 작은 원소를 찾다가 못 찾은 채로 원소 31에서 L 과 만나게 된다.
• L 과 R 이 만났으므로 피봇(Pivot)과 교환하는데 R 의 원소가 피봇(Pivot)이므로 결국 제 자리가 확정된다.

• 피봇(Pivot) 31의 오른쪽 부분 집합의 원소가 한 개 이므로 퀵 정렬을 수행하지 않는다. 이것으로써 전체 퀵 정렬이 모두 완성하게 된다.

 

• 퀵 정렬 알고리즘 분석
  
• 메모리 사용 공간
• n개의 원소에 대하여 n개의 메모리 사용
  
  
• 연산 시간
• 최선의 경우
  - 피봇(Pivot)에 의해서 원소들이 왼쪽 부분 집합과 오른쪽 부분 집합으로 정확히 n/2개씩 이등분이 되는 경우가 반복되어 수행 단계 수가 최소가 되는 경우
  
  
• 최악의 경우
  - 피봇(Pivot)에 의해 원소들을 분할하였을 때 1개와 n-1개로 한쪽으로 치우쳐 분할되는 경우가 반복되어 수행 단계 수가 최대가 되는 경우. n²
  
  
• 평균 시간 복잡도 : O(nlog₂n)
  - 같은 시간 복잡도를 가지는 다른 정렬 방법에 비해서 자리 교환 횟수를 줄임으로써 더 빨리 실행되어 실행 시간 성능이 좋은 정렬 방법입니다.