목차

• 정렬이란?
• 분할 정복 Divide and Conquer
• 퀵정렬
  • 수도코드
    • 코드 설명
  • 시간 복잡도
  • 평가
  • 구현
    • 파이썬
    • 자바

정렬이란?

• 임의로 나열되어 있는 데이터들을 주어진 항목에 따라 크기 순서대로 작은 순서부터 (오름차순) 또는 큰 순서부터 (내림차순) 늘어놓은 것임
• 정렬되어 있는 데이터들은 다음과 같은 작업을 수행할 때 응용
  ① 데이터를 탐색할 때
  ② 리스트에 있는 다른 항목들을 비교할 때

분할 정복 Divide and Conquer

more learn
분할 정복은 말 그대로 문제를 ‘분할’ 해서 ‘정복’ 한 다음 정답을 ‘조합’해 나간다는 의미

• 분할 정복은 재귀를 활용하는 대표적인 알고리즘

퀵 정렬

• 가장 유명한 정렬 알고리즘
• 피벗을 기준으로 좌우를 나누는 특징 때문에 파티션 교환 정렬 Partition-Exchange Sort 이라고도 불림

• 데이터를 비균등하게 분할한 후 반복 정렬
  ① 데이터에서 기준(pivot) 설정
  ② Pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽 분할
  ③ Pivot을 기준으로 왼쪽과 오른쪽을 재귀적으로 반복.
  ④ 정렬된 부분 배열을 하나의 배열에 병합

• 모든 정렬 방법 중에서 평균 수행 시간이 가장 빠른 방법
  • 현재 정렬 과정에서 처리되고 있는 피벗 키 p 를 기준으로 원소를 두 부분으로 나눔
  • 나누어진 두 부분을 따로 다시 퀵 정렬을 수행하여 모든 원소가 순서대로 정렬될 때까지 실행

Lomuto Partition Scheme

여러 가지 변형과 개선 버전이 있는데 가장 대표적인 Lomuto 의 파티션 계획 Lomuto Partition Scheme 을 구현해보겠음

• 항상 맨 오른쪽의 피벗을 택함
• 매우 기본이고 간단한 퀵정렬의 방법
• 피벗보다 작은 값을 left값으로 옮김

[구현 순서]
① 오른쪽 right 포인터가 이동하면서

• 피벗의 값 > right 포인터 값: right 포인터 값과 left 포인터 값 스왑

② 스왑 이후에는 왼쪽 left 포인터가 함께 이동
③ 오른쪽 포인터가 끝에 도달하게 되면

• 피벗 미만인 값: 왼쪽 위치
• 피벗 이상인 값: 오른쪽 위치

④ 왼쪽 포인터의 위치로 피벗 아이템이 이동

• 피벗을 기준으로 작은 값은 왼쪽에 큰 값은 오른쪽으로 분할됨
• 피벗이 그 중앙에 위치

⑤ ①~④ 반복

• 이렇게 계속 분할하면서 lo < hi 를 만족하지 않을 때까지(서로 위치가 역전할 때까지) 계속 재귀로 반복

[포인터]

• left: 피벗보다 작으면 +1(if)
• right: 탐색해가면서 피벗과 값 비교(for)

수도코드

파티션을 나누고 각각 재귀 호출(분할)

Quicksort(A, lo, hi) 
 if lo < hi 
  pivot := partition(A, lo, hi) 
  Quicksort(A, lo, pivot - 1) 
  Quicksort(A, pivot + 1, hi)

피벗: 맨 오른쪽 값을 기준

• 피벗을 기준으로 2개의 포인터가 이동
  • 오른쪽 포인터의 값 < 피벗 : 스왑

partition(A, lo, hi) 
 pivot := A[hi] 
 i := lo 
 for j := lo to hi do
  if A[j] < pivot then 
   swap A[i] with A[j] 
   i := i + 1

 swap A[i] with A[hi] 
 return i

시간 복잡도

• 평균 수행 시간: O($nlog_{2}n$)
• 정렬해야 할 원소들의 값에 따라 최악의 경우에는 O($n^2$)
  [최선의 경우]
  [최악의 경우]
  

평가

• 모든 정렬 방법 중에서 평균 수행 시간이 가장 빠른 방법

구현

파이썬

1) pivot, left값 정리
2) for문르도 right값 설정
2.1) 피벗과 비교(피벗보다 작은 값 찾기)
2.1.1) 바꾸기
2.1.2) left값 늘리기

def quicksort(A, lo, hi):
 def partition(lo, hi):
  pivot = A[hi] 
  left = lo
  for right in range(lo, hi):
   if A[right] < pivot:
    A[left], A[right] = A[right], A[left] 
    left += 1
  # pivot = A[hi]니까 피벗의 자리를 옮기는 것
  A[left], A[hi] = A[hi], A[left] 
  return left
  
 if lo < hi:
  pivot = partition(lo, hi) 
  quicksort(A, lo, pivot - 1) 
  quicksort(A, pivot + 1, hi)