[Python] 퀵 정렬

퀵 정렬

기준 값을 정하고 기준값에 맞춰 나머지 데이터들의 위치를 맞추는 알고리즘이다.

 

퀵 정렬 과정

#기준 값을 정한다. (편의상 마지막 값을 기준 값으로 정한다.)
[2, 6, 8, 1, 5, 3, 7, 4] # 기준 값 : 4

#기준 값보다 작으면 기준 값의 앞쪽으로, 기준 값보다 크면 기준값의 뒤로 보낸다.
기준 값 : 4
group1 [2, 1, 3]
4
gruop2 [6, 8, 5, 7]

#재귀 호출을 이용해 정렬한다.
group1 [1, 2, 3]
4
group [5, 6, 7, 8]

#다시 합친다.
group1 + 4 + group2

결과 : [1, 2, 3, 4, 5, 6, 7, 8]

 

퀵 정렬 알고리즘

def quick_sort(a):
    n = len(a)
    #종료조건
    if n <= 1:
        return a
    pivot = a[-1]
    g1 = []
    g2 = []

    for i in range(0, n-1):
        if a[i] < pivot:
            g1.append(a[i])
        else:
            g2.append(a[i])
    
    return quick_sort(g1) + [pivot] + quick_sort(g2)

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(quick_sort(d))

 

또 다른 방법

def quick_sort_sub(a, start, end):
    n = len(a)
    #종료조건
    if end - start <= 0:
        return 
    pivot = a[end]
    i = start

    for j in range(start, end):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[end] = a[end], a[i]
    
    #재귀호출
    quick_sort_sub(a, start, i - 1)
    quick_sort_sub(a, i + 1, end)

def quick_sort(a):
    quick_sort_sub(a, 0, len(a) - 1)

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
quick_sort(d)
print(d)