정렬 알고리즘(Sorting)(2) - 퀵 정렬

퀵 정렬

기준 데이터를 설정

그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈

(첫 번째 데이터를 기준 데이터(Pivot)로 설정)

 

일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘

병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 됨

 

 

1. 5 = 기준 데이터 = 피벗

2. 왼쪽에서부터 5보다 큰 데이터 선택, 오른쪽에서부터 5보다 작은 데이터 선택 (각각 7, 4 선택)

3. 7과 4 위치 변경

 

 

4. 4와 7 위치 변경 이후 다시 5를 기준으로 왼쪽에서부터 큰 데이터 선택, 오른쪽부터는 작은 데이터 선택

5. 9와 2 위치 변경

 

 

6. 9와 2 위치 변경 후, 다시 작업 수행

7. 데이터를 찾았는데 위치가 엇갈림

8. 위치가 엇갈리는 경우 피벗과 작은 데이터의 위치 변경

 

 

9. 피벗 5를 기준으로 왼쪽 데이터는 모두 5보다 작고, 오른쪽 데이터는 모두 5보다 큼 -> 분할 완료

분할(Divide) : 피벗을 기준으로 데이터 묶음을 나누는 작업

 

 

10. 왼쪽에 있는 데이터 묶음 퀵 정렬 수행

11. 오른쪽에 있는 데이터 묶음 퀵 정렬 수행

(왼쪽과 오른쪽을 각각의 배열로 판단 -> 다시 퀵 정렬 수행)

 

퀵 정렬이 빠르게 동작하는 이유(퀵 정렬의 시간 복잡도)

 

데이터의 분할이 절반씩 일어난다면 전체 연산 횟수 = O(NlogN)

너비 X 높이 = N X logN = NlogN

퀵 정렬의 평균 시간 복잡도 = O(NlogN)

최악의 경우 O(N^2) -> ex. 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 대해서 퀵 정렬을 수행하는 경우

 

+ )

다양한 프로그래밍 언어에서 표준 정렬 라이브러리를 제공할 때, 퀵 정렬 기반으로 라이브러리가 작성되어 있는 경우,

최악의 경우에도 O(NlogN)을 보장할 수 있는 형태로 구현할 수 있게 보장해줌 -> 라이브러리는 기본적으로 NlogN을 보장하고 있음

 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
  if start >= end:#원소가 1개인 경우 종료
    return
  pivot = start
  left = start + 1
  right = end
  while(left <= right):
    #피벗보다 큰 데이터를 찾을 때까지 반복
    while(left <= end and array[left] <= array[pivot]):
      left += 1
    #피벗보다 작은 데이터를 찾을 때까지 반복
    while(right > start and array[right] >= array[pivot]):
      right -= 1
    if left > right: #엇갈렸다면 작은 데이터와 피벗 교체
      array[right], array[pivot] = array[pivot], array[right]
    else: #엇갈리지 않았다면 작은 데이터와 큰 데이터 교체
      array[left], array[right] = array[right], array[left]
  
  #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
  quick_sort(array, start, right-1)
  quick_sort(array, right+1, end)

quick_sort(array, 0, len(array)-1)
print(array)

 

파이썬을 이용한 간결한 퀵 정렬 코드(슬라이싱 이용)

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
  if len(array) <= 1:
    return array
  pivot = array[0]
  tail = array[1:]

  left_side = [x for x in tail if x <= pivot] #분할된 왼쪽 부분
  right_side = [x for x in tail if x > pivot] #분할된 오른쪽 부분

  #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행하고, 전체 리스트 반환
  return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))