[Python] 퀵 정렬

• 퀵 정렬
  • 주어진 배열을 두 개로 분할하고, 각각을 정렬
  • 최악의 시간 복잡도 O(n^2), 합병정렬보다 좋지 못하다
  • 평균적으로 가장 빠름( O(nlogn))

 

• 합병정렬과 다른점
  • 합병정렬은 그냥 두 부분으로 나누는 반면에, 퀵정렬은 분할할 때, 기준 아이템(pivot item) 중심으로, 기준보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 위치
  • 각 부분 정렬이 끝난 후, 합병정렬은 합병이란 후 처리 작업이 필요하나, 퀵정렬은 필요하지 않음

 

def quickSort(a,begin,end):
    if begin < end:
        p = partition(a,begin,end)
        quickSort(a,begin,p-1)
        quickSort(a,p+1,end)

def partition(a,begin,end):
    pivot = (begin+end)//2
    L = begin
    R = end
    while L < R:
        while (L<R and a[L] < a[pivot]):
            L += 1
        while (L < R and a[R] >= a[pivot]):
            R -= 1
        if L < R:
            if L==pivot:
                pivot = R
            a[L], a[R] = a[R], a[L]
    a[pivot], a[R] = a[R], a[pivot]
    return R

a =[69,10,30,2,16,8,31,22]
quickSort(a,0,7)
print(a)

코드실행결과

• 퀵 정렬 순서
  
  1. 중앙에 값을 pivot 으로 선택
  2. 범위의 시작값 L, 마지막값 R
  3. L >= R이 아닐때까지
  4. L에서 오른쪽으로 이동하면서 pivot보다 크거나 같은 값 찾기, R에서 왼쪽으로 이동하면서 pivot보다 작은 원소 찾기
  5. L<R 이면 (L == pivot이면 pivot = R 그리고 L값과 R값 자리 바꾸기)
     작은 값을 앞으로 보내기 위해
  6. L =< R이면 pivot과 R(작은값) 바꾸기
  7. pivot 기준으로 왼쪽구간 오른쪽 구간 각각 1번부터