6. Array(배열) - Quick Select

1. Quick Select란?

- 정렬되지 않은 배열에서 N번째로 크거나 작은 수를 찾을 때 사용되는 알고리즘 

- N번째 수를 찾기 위해서는 다음과 같은 방법을 사용할 수 있다. 

 

1) 전체 요소를 오름차순으로 정렬한 후, N번째 수를 찾는 방법

   - O(N log N)의 시간복잡도

 

2) Heap 정렬

   - O(n log k)의 시간복잡도

   - 1)의 방법보다 빠르다. 

 

3) Quick Select

  - O(n)의 시간복잡도

 - 가장 빠른 방법이다. 

 

- 이 중에서 가장 빠른 Quick Select에 대해서 알아보자. 

---

2. Quick Select 개념

- Quick Select는 Partitioning(파티셔닝)을 이용한 알고리즘이다.

 

▶ Partitioning 이란?

   - Pivot 이라는 하나의 숫자를 기준으로 배열의 요소를 정렬하는 방식

   - Pivot 보다 작은 수는 좌측에 위치한다.

   - Pivot 보다 큰 수는 우측에 위치한다. 

   - 이와 같은 규칙으로 배열의 요소를 정리하는 것이다. 

 

- 아래의 사진이 안보이는 분들을 위해 PDF형태로 공유합니다. 

Quick_Select_1.pdf

5.31MB

Quick_Select_2.pdf

1.83MB

 

a) 정렬 과정

 

c) Quick Select 시간복잡도

- Quick Select는 어떤 수가 Pivot으로 지정되냐에 따라 시간복잡도의 영향을 끼친다.

- 다음과 같은 케이스로 시간복잡도가 분류될 수 있다. 

---

3. 코드구현

from typing import List
import random

# k번째 큰 수를 반환하는 경우 
def quick_select(case: List[int], k: int) -> int:
  length = len(case)
  if length == 1:
    return case[0]

  pivot_idx = random.randrange(length)
  last_idx = length - 1

  # 최초에 pivot을 지정한 뒤에 배열의 가장 우측의 요소와 swap한다. 
  case[pivot_idx], case[last_idx] = case[last_idx], case[pivot_idx]

  # pivot보다 작은 수인지 판단할 포인터
  left_idx = 0 

  # pivot보다 큰 수인지 판단할 포인터 
  # -2를 하는 이유는 len() 메소드는 총 요소의 개수를 반환하기 때문이고, 맨 우측의 pivot을 제외하기 위함 
  right_idx = length - 2
  
  pivot = case[-1]  

  while left_idx <= right_idx: # 두 개의 포인터가 교차하면 종료 

    if case[left_idx] <= pivot: # 좌측 포인터가 pivot보다 작은 경우, 우측으로 이동 
      left_idx += 1
      continue

    if pivot < case[right_idx]: # 우측 포인터가 pivot보다 큰 경우, 좌측으로 이동
      right_idx -= 1
      continue

    if pivot < case[left_idx] and pivot >= case[right_idx]: # 두 포인터가 더이상 이동하지 못하는 경우 
      case[left_idx], case[right_idx] = case[right_idx], case[left_idx] # 두 포인터가 가리키는 값을 swap
      continue
  
  # quick select를 한바퀴 돌으면, left_idx가 pivot의 우측에 정렬되는 수 중에 가장 왼쪽의 수를 가리킨다. 
  case[left_idx], case[last_idx] = case[last_idx], case[left_idx]
  if left_idx == length - k: # 좌측 포인터가 가리키는 index가 찾고 있는 index인 경우 
    return case[left_idx]

  elif left_idx < length - k: # pivot의 우측에 있는 수 중에 찾고 있는 수가 있는 경우
    return quick_select(case = case[left_idx + 1:], k = k) # 우측의 요소를 대상으로 quick select를 다시 적용
    # left_idx + 1을 하는 이유는, 현재 left_idx가 가리키는 수는 찾는 수가 아니므로 고려 대상에서 제외하기 때문

  elif length - k < left_idx: # pivot의 좌측에 있는 수 중에 찾고 있는 수가 있는 경우
    return quick_select(case = case[:left_idx], k = k - (length - left_idx)) # 좌측의 요소를 대상으로 quick select를 다시 적용
    # k - (length - left_idx)를 하는 이유는, 좌측의 수 만을 대상으로 배열을 형성하는 경우, 요소 개수의 변화로 타겟 index가 달라지기 때문이다. 

print(quick_select(case = [5, 7, 9, 3, 2, 1, 4], k = 2))