[알고리즘/Python] 퀵 정렬 | quick sort

퀵 정렬 [ quick sort ]

- 기준 점 ( pivot )을 잡아서 기준보다 크면 오른쪽 작으면 왼쪽으로 보낸 뒤 각각 또 다시 pivot을 잡아서 반복하는 정렬

 

 

시간복잡도 ⏱

•     최선의 경우 : O(n log(n)) 
  • 이미 정렬이 다 되어있는 경우

•     최악의 경우 :  O(n²)   
•     평균 :  O(n log(n))

장점 

 

1. 평균적인 속도는 가장 빠르다

 

단점

 

1. pivot을 잘못 선택할 경우 ( 리스트가 계속 불균형하게 나누어지는 경우 )는 수행시간이 더 많이 걸린다.

  - 최악의 경우 시간 복잡도가 O(n²)이 된다. 

 

[ python quick sort code | 파이썬 퀵 정렬 코드 ]

ver.1 - 파이썬의 특성을 살린 코드

data = list(map(int,input().split()))

def quick_sort(array):
    
    if len(array) <= 1:
        return array
    
    pivot = array[0]
    tail = array[1:]

    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]

    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

data = quick_sort(data)
print(data)

 

ver.2 

data = list(map(int,input().split()))

def quick_sort(array,start,end):

    if start >= end:
        return
    
    pivot = start
    left = start+1
    right = end

    while left <= right:

        while left <= end and array[left] <= array[pivot]:
            left+=1
        while right > start and array[right] >= array[pivot]:
            right-=1
        
        if left > right :
            array[pivot],array[right] = array[right],array[pivot]
        else:
            array[right],array[left] = array[left],array[right]
        
    quick_sort(array,start,right-1)
    quick_sort(array,right+1,end)

quick_sort(data,0,len(data)-1)
print(data)

---

[ 합병정렬 | Merge Sort ]

[ 힙 정렬 | Heap Sort ]

[ 삽입정렬 | Insertion Sort ]

[ 선택 정렬 | Selection Sort ]