정렬 알고리즘: 퀵 정렬

배열이 있을 때..

1. 배열의 맨 앞에 있는 수를 pivot으로 설정한다 (피벗은 다른 수로 선택할 수도 있다는데 일단 난 맨 앞에걸로 하겠음)

2. 배열의 두 번째 수부터 오른쪽으로 진행하면서 pivot보다 큰 수를 찾는다 => 여기서 찾은 수의 인덱스를 left라고 하겠음

3. 배열의 끝부터 왼쪽으로 진행하면서 pivot보다 작은 수를 찾는다. => 여기서 찾은 수의 인덱스를 right라고 하겠음

4. 찾은 left와 right인덱스의 값을 서로 바꿈.. 근데~ 만약에 left가 right보다 오른쪽에있다?? 그러면 작은수랑 피벗이랑 바꿈..

5. 이렇게되면 피벗을 기준으로 왼쪽엔 피벗보다 작은값, 오른쪽엔 피벗보다 큰값으로 대충 정리가 됨.. 그니까 피벗 기준으로 앞부분, 뒷부분을 또 퀵소트를 돌림(재귀함수)

 

array=[5,7,9,0,3,1,6,2,4,8]

def quick_sort(array,start,end):
    if start>=end: #원소가 1개인 경우
        return
    pivot = start #첫번째 원소를 피벗으로 설정함
    left=start+1 #왼쪽부터 찾을 인덱슨데 첫번째 원소는 피벗이니까 그 다음거부터 찾을거임.
    right=end #이건 오른쪽부터 찾을거..인덱스
    while left<=right:
        while left<=end and array[left]<=array[pivot]: #왼쪽에서부터 피벗보다 큰 수를 찾아야하므로 피벗보다 작은수면 left++
            left+=1
        while right > start and array[right] >= array[pivot]: #오른쪽에서부터 피벗보다 작은 수를 찾아야함.. 피벗보다 큰 수면 right 감소시킴
            right-=1
        if left>right: #left, right가 엇갈린경우
            array[right],array[pivot]=array[pivot],array[right] #엇갈린경우 작은 수와 피벗을 교체
        else:
            array[left],array[right]=array[right],array[left]#엇갈리지 않았으면 left, right스왑 함
        
        #이렇게 다 돌고나면 피벗을 기준으로 피벗보다[ 피벗보다 작은수들, 피벗 , 피벗보다 큰수들 ] 로 정리됨
        #피벗 앞뒤로 퀵소트 실행시킴. 
        #(right위치에 피벗이 있음)
    quick_sort(array,start,right-1) 
    quick_sort(array,right+1,end)

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

그리고 평균 O(NlogN)의 시간복잡도를 가지고

최악의 경우 O(N^2)의 시간복잡도를 가짐. 

 

암튼 난 이해함~