[python/파이썬] 퀵 정렬(Quick sort)

 

개념

-재귀 알고리즘과 분할정복(Divide and Conquer) 기법이 이용됩니다.

-다른 정렬 알고리즘을 이용하면 데이터 수가 많아질 수록 시간이 오래걸리고 메모리가 커지지만(시간 복잡도:N²)

퀵정렬은 시간복잡도가 NlogN이므로 훨씬 빠르기때문입니다.(최악의 경우인 리스트가 이미 정렬 되있거나 역순으로 정렬 되어있으면 N²의 시간 복잡도를 가집니다.)

CODE

def quick_sort(a) :
    if len(a) <= 1 : # 리스트의 길이가 1이면 정렬할 필요가 없기 때문에 바로 반환한다.
        return a
    pivot = a[0] # 리스트에서 원하는 기준점(피벗)을 선택한다.
    left = [] # 피벗보다 작은 수들의 리스트
    right = [] # 피벗보다 큰 수들의 리스트
    piv = [] #피벗을 빼놓고 큰수 작은수로 나누어야 하기때문에 피벗 부분을 넣을 리스트를 생성한다.
    for i in a :
        if i < pivot :
            left.append(i)
        elif i > pivot :
            right.append(i)
        else :
            piv.append(i)
    return quick_sort(left) + piv + quick_sort(right)
arr = [10,30,20,40,90,60]
print(quick_sort(arr))
#[10,20,30,40,60,90]

퀵정렬 과정

-리스트에서 원하는 기준점(피벗/pivot)을 선택합니다.

-pivot을 기준으로 왼쪽은 작은 값을 오른쪽은 큰 값을 넣을 리스트를 생성합니다.

-반복문을 통하여 작은 값과 큰 값을 나눕니다.

-pivot을 기준으로 작은 값을 넣은 리스트와 큰 값을 넣은 리스트도 똑같이 재귀 알고리즘을 이용하여 pivot을 기준으로 큰값과 작은값으로 나눕니다.

-반복을 하다가 리스트의 개수(길이)가 1이 된다면 리스트를 리턴을 하여 더이상 반복을 못 하도록 합니다.

 

 

감사합니다