[알고_이론] 퀵정렬 (Quick sort _ by python )

퀵정렬이란?

정렬할 리스트를 두개로 분할하고 정렬하는 방법이다.

 

퀵정렬 수행 방법

1) 배열의 값 중에서 임의의 수를 피봇을 설정한다. 

 

2) 피봇(=Pivot) 의 좌측은 피봇보다 작거나 같은 값 들, 오른쪽 큰 값들의 구성을 "목표"로한다.

 

3. 좌측에서 피봇보다 큰 숫자, 우측에서 작은 숫자가 나오면 교환하고 그 둘의 자리를 바꾸고 이를 반복한다.

 

4. 좌, 우측의 값을 포인팅 해주는 L,R이 피봇을 지나서 엇갈리는 상황이 오면 L과 피봇을 교체해주고 재귀 호출로 분할 정복을 수행한다.

 

 

 

왼쪽에서는 자신보다 큰 8을 찾아서 고정, 오른쪽에서 자신보다 작은 1을 찾아서 고정 => 둘이 교환

 

 

 

 

 

위의 작업을 반복하다보니, 피봇을 지나서 L,R과 엇갈리게 되었다.

엇갈리게 됬을 때는, 피봇을 기준으로 왼쪽과 오른쪽을 각각 재귀호출하여 퀵정렬을 하는데! 이 때, 배열의 길이가 1인 경우는 재귀 함수를 하지 않고 종료한다.

 

 

 

퀵정렬 파이썬 코드

import random
def quick_sort(arr):
    if len(arr) <= 1: #길이가 1이면 재귀 종료
        return arr
    pivot = arr[len(arr) // 2] # 저는 피봇을 중간 값을 설정하였습니다.
    lesser_arr, equal_arr, greater_arr = [], [], []
    for num in arr:
        if num < pivot: # 피봇보다 작은 값을 별도의 배열에 담아준다.
            lesser_arr.append(num)
        elif num > pivot:# 피봇보다 큰 값 별도의 배열에 담아준다.
            greater_arr.append(num)
        else:
            equal_arr.append(num)
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)
    # 재귀 함수를 통해, 각 배열에 대한 재귀 퀵정렬을 수행한다.

arr = random.sample(range(100),10)
print(arr)
print(quick_sort(arr))