퀵 소트 quick sort

분할 : 배열을 다음과 같은 조건이 만족되도록 두 부분으로 나눈다.

elements in lower parts <= elements in upper parts

정복 : 각 부분을 순환적으로 정렬한다.

합병 : x

마지막 값을 pivot으로 선택하려고 한다.

피봇을 기준으로 작은 값은 피봇 앞, 큰 값은 피봇 뒤로 간다.

작은 값 pivot 큰 값

그러나 pivot이 가장 작거나 가장 크다면 시간이 오래 걸린다.

31 8 48 73 11 3 20 29 65 15 중에서 15를 pivot으로 한다.

8 11 3 15 31 48 20 29 65 73 pivot의 왼쪽과 오른쪽을 정렬한다.

3 8 11 15 20 29 31 48 65 73 합병 과정이 필요 없다.

def quicksort(A,p,r):

  if p<r:

    q=partition(A,p,r) #q는 pivot

    quicksort(A,p,q-1) #왼쪽 정렬

    quicksort(A,q+1,r) #오른쪽 정렬

def partition(A,p,r):

  배열 A의 원소들을 A[r]을 기준으로 양쪽에 재배치하고 A[r]이 자리한 위치를 return 한다.

파이썬을 사용하면 더 간결하게 표현할 수 있다. 다른 블로그를 보니 이런 코드가 있었다. 파이썬 멋있다.

arr=[31,8,48,73,11,3,20,29,65,15]
def quicksort(arr):
    if len(arr)<2:return arr
    pivot = arr[-1]
    left=[]
    right=[]
    center=[]
    for i in arr:
        if i<pivot:
            left.append(i)
        elif i>pivot:
            right.append(i)
        elif i==pivot:
            center.append(i)
    return quicksort(left)+center+quicksort(right)
print(quicksort(arr))