퀵 소트 (Quick sort)

참고 :

debuglog.tistory.com/67

Python으로 알고리즘 공부 02. 퀵 정렬 (Quick Sort)

---

■ 퀵 소트

1) 정의 :

분할정복을 사용하여 piviot 값을 기준으로 하여 좌, 우를 나누어 정렬하는 방식

> (꼭 그래야 하는 것은 아니지만) piviot 보다 작은 아이템은 왼쪽, 큰 아이템은 오른쪽

> pivot은 랜덤 값이 제일 적당 ...OR... 평균에 가까운 수

> 재귀 형식 사용 : 점화식의 형태

 

2) 복잡도 :

평균 시간복잡도 : O(N * log(N) )

최악 시간복잡도 : O(N^2)

 

3) 예시 :

(a)

import random

def quick_sorted(arr):

    if len(arr) > 1: # 재귀 탈출 조건
    	"""두가지 방식이 존재"""
        # pivot = arr[len(arr)-1]
        pivot = random.choice(arr) # chooses one randome value
        
        left, mid, right = [], [], []
        for i in range(len(arr)-1):
            if arr[i] < pivot:
                left.append(arr[i])
            elif arr[i] > pivot:
                right.append(arr[i])
            else:
                mid.append(arr[i])
        mid.append(pivot)
        
        # 재귀 사용하여 list 합산으로 결과를 합쳐서 돌려줌
        return quick_sorted(left) + mid + quick_sorted(right)
    else:
        return arr
        
arr = [3, 5, 1, 2, 9, 6, 4, 7, 5]
print(quick_sorted(arr))

>>> [1, 2, 3, 4, 5, 5, 6, 7, 9]

(b)

import random

def quick_sorted(arr):

    if len(arr) > 1:
    
        pivot = random.choice(arr) # chooses one randome value
        
        """ list comprehension 사용 """
        left =  [num for num in arr if num < pivot]
        mid  =  [num for num in arr if num == pivot]
        right = [num for num in arr if num > pivot]
        
        return quick_sorted(left) + mid + quick_sorted(right)
    else:
        return arr
        
arr = [3, 5, 1, 2, 9, 6, 4, 7, 5]
print(quick_sorted(arr))

>>> [1, 2, 3, 4, 5, 5, 6, 7, 9]