quick sort (기본: 맨 끝을 pivot으로)

코드

 

# quick (pivot은 끝 값)
def quick_sort(a):
    quick_sort_sub(a, 0, len(a) - 1)
 
 
def quick_sort_sub(a, start, end):  # start, end 모두 포함
    n = len(a)
    if end - start <= 0:  # 길이가 1이하는 종료
        return
 
    # start부터 전체 배열 흝으며 pivot보다 작은 값 앞에서부터 넣기.
    # 그 후, pivot을 마지막 바꾼 자리 옆에 놓아서 왼쪽 작은거 오른쪽 큰 거로 나누기
    # 나눈 좌우 quick sort하기(재귀)
    pivot = a[end]  # 맨 끝 기준
    i = start  # i는 pivot보다 작은 것들을 앞쪽으로 놔두기 위한 인덱스 용도
    for j in range(start, end):  # 처음부터 맨 끝-1까지 흝기
        if a[j] < pivot:  # less than pivot
            a[i], a[j] = a[j], a[i]  # 앞에서부터 채워나감
            i += 1
    a[i], a[end] = a[end], a[i]  # pivot자리를 중간에
 
    # 왼 오 정렬
    quick_sort_sub(a, start, i - 1)
    quick_sort_sub(a, i + 1, end)

 

quick sort는 기준값 하나를 정해서 그것을 기준으로 그보다 작은 값, 큰 값들을 배열 양옆으로 둔다.

그 후 양옆으로 quick sort를 재귀호출해서 정렬하는 방식이다.

이 코드는 간단하게 처음 입력에서 가장 끝값을 pivot으로 둔다.

기준 값 정하는 알고리즘은 다음에 다뤄보도록 하겠다.

 

(평균)시간 복잡도: O(nlogn)

반씩 재귀호출 logn번

배열을 처음부터 끝까지 훑음 n