정렬 - 퀵 정렬(quick sort)

1. 퀵 정렬(quick sort)이란?

🌸 정렬 알고리즘의 꽃

🖐 기준점(pivot)을 정해서 피벗보다 작은데이터는 왼쪽, 큰 데이터는 오른쪽으로 -> 반복

🖐 왼쪽 + 기준점 + 오른쪽 리턴

 

2. 순서대로 생각해보기

data = [4, 6, 3, 7, 1] 일 때,

👉 맨 앞 기준으로 작으면 left, 크면 right에 넣어보자

data = [4,6,3,7,1]
pivot = data[0]
left = []
right = []
for idx in range(1,len(data)):
    if data[idx] < pivot:
        left.append(data[idx])
    else:
        right.append(data[idx])
        
print(left, pivot, right)
#출력 결과 : [3, 1] 4 [6, 7]

👉 left의 맨 앞 데이터를 pivot에 넣고 또 해보자

data = left
pivot = data[0]
left = []
right = []
for idx in range(1,len(data)):
    if num < pivot:
        left.append(data[idx])
    else:
        right.append(data[idx])
print(left, pivot, right)
# 출력 결과 : [1] 3 []

 

3. 알고리즘 구현하기

✍ 리스트 개수가 한 개면 해당 리스트 리턴

✍ 맨 앞의 데이터를 피봇으로 놓기

✍ left, right 변수를 만들고 피봇과 비교해 넣어주기

✍ 재귀호출

def quick(data):
    if len(data) <= 1:
        return data
    
    left = list()
    right = list()
    pivot = data[0]  # 맨 앞 데이터를 피벗으로 !
    
    for idx in range(1, len(data)):  # 첫번째 데이터는 피벗이니까 인덱스 1부터 시작
        if data[idx] < pivot :  # 피벗보다 작으면
            left.append(data[idx])  # left에
        else:
            right.append(data[idx])
    
    return quick(left) + [pivot] + quick(right)  # 나눠진 리스트에서 또 퀵소트 호출 ~!

quick([4,6,3,7,1])  # [3,1] 4 [6,7] -> # [1] 3 [] + 4 + [] 6 [7]....
# 출력 결과: [1, 3, 4, 6, 7]

 

4. 복잡도

👉 머지 소트와 유사, 시간복잡도는 O(nlogn)

👉 맨 처음 피벗이 가장 크거나 작으면 모든 데이터를 비교해야하는 상황이 올 수 있음 O(n**2)