[python] 알고리즘 - 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

출처: https://visualgo.net/en

 

 

퀵소트는 반복문을 하나만 쓰기 때문에 시간복잡도 면에서 더 우수한 성능을 기대를 할 수 있다. 위 (이미지를 보다. 코드를 먼저 보는 게 더 나을 수도 있다. 보기와는 달리 정말 간단하다. 코드를 이해하면 이게 왜 빠를 수밖에 없는지 바로 이해된다.)

 

gif 이미지에서 8을 첫번째 피벗으로 선택한다. 이때 작은 데이터와 큰 데이터를 구분하고 8의 왼쪽과 오른쪽에 붙인다. 다음으로 5를 선택하고 반복한다. (노란색이 피벗이다.) 

 

포인트는 재귀(Recursive)를 사용한다는 것이다.

 

1. 배열에서 Pivot(기준점, 중심)을 정한다.

2. 피벗 보다 작은 데이터들은 left 리스트로, 큰 값은 right 리스트로 이동한다.

3. 이 과정을 재귀로 반복 시키면서 붙인다.

 

#Quick Sort
def quick_Sort(array):
    if len(array) <= 1:
        return array
    
    left, right = [], []
    pivot = array[0]
    
    for a in range(1, len(array)):
        if pivot < array[a]:
            right.append(array[a])
        else:
            left.append(array[a])
    
    return quick_Sort(left) + [pivot] + quick_Sort(right)


#Test Code
import random
array = random.sample(range(100), 10)

print(array)
print(quick_Sort(array))