[이코테]CHAPTER 06 정렬 - 퀵정렬- 파이썬(Python)

1) 퀵 정렬

: 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸기. 피벗(Pivot)(교환하기 위한 기준) 사용

 

 -  호어 분할 방식(Hoare Partition)

    1. 리스트에서 첫번째 데이터를 피벗 설정

    2. 리스트 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서는 피벗보다 작은 데이터를 찾기

 

    3. 큰 데이터와 작은 데이터 교환

1. '5'보다 큰 데이터를 선택하므로 왼쪽에서부터 '5'보다 큰 '7' <->오른쪽에서부터 '5'보다 작은 '4' 둘이 변경  2. '5'보다 큰 데이터를 선택하므로 왼쪽에서부터 '9' 선택 <-> 오른쪽에서부터 '2' 둘이 변경 3. '5'보다 큰 데이터를 선택하므로 왼쪽에서부터 '6' 선택, 오른쪽에서부터 '1' 선택하였는데 이렇게 두 값이 엇갈린 경우 작은 데이터('1')와 피벗의 위치('5')를 변경 4. 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치, 피벗의 오른쪽에는 피벗보다 큰 데이터를 위치하여 왼쪽 리스트와 오른쪽 리스트를 개별적으로정렬

1. 오른쪽 리스트에서는 '1'을 피벗으로, 왼쪽 리스트에서는 '6'을 피벗으로 설정     오른쪽 리스트는 왼쪽에서부터 '1'보다 큰  '4'<->오른쪽에서부터 '1'보다 작은 '0'     왼쪽 리스트는 왼쪽에서부터 '6'보다 큰 '9', 오른쪽에서부터 '6'보다 작은 값 존재 하지 않으므로 그대로 유지 2. 오른쪽 리스트 왼쪽에서부터 '1'보다 큰 '4', 왼족에서부터 '1'보다 작은 '0'을 선택하였는데      이렇게 두 값이 엇갈린 경우 작은 데이터('0')과 피벗의 위치('1')를 변경 3. 따라서, 0, 1, 5, 6은 위치 고정

1. 오른쪽 리스트에서는 '2'를 피벗으로, 왼쪽 리스트에서는 '9'를 피벗으로 설정    오른쪽 리스트는 왼쪽에서부터 '2'보다 큰 '4', 오른쪽에서부터는 '2'보다 작은 값이 존재하지 않으므로 그대로 유지    왼쪽 리스트는 왼쪽에서부터 '9'보다 큰 데이터 없음 .         오른쪽에서부터 작은 '8'을 선택하였는데 두 값이 엇갈렸으므로 피벗의 위치('9')와 작은 데이터('8')을 변경 2. 따라서 이번에는 2, 9위치가 고정되어서 0,1,2,5,6,9 위치가 고정된다.

1. 오른쪽 리스트에서튼 '4'를 피벗으로, 왼쪽 리스트에서는 '8'를 피벗으로 설정    오른쪽 리스트는 왼쪽에서부터 '4'보다 큰 데이터 존재하지 않고, 오른쪽에서부터 '4'보다 작은 데이터 '3'이므로        피벗의 위치('4')와 작은 데이터('3')을 변경.    왼쪽 리스트는 왼쪽에서부터 '8'보다 큰 데이터 존재하지 않고, 오른쪽에서부터 '8'보다 작은 데이터 '7'이므로        피벗의 위치('8')와 작은 데이터('7')을 변경 2. 정렬 완료

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+=1
        #피벗보다 작은 데이터를 찾을 때까지 왼쪽으로 한칸씩 이동(<-)
        while start<=right and array[right]>=array[pivot]:
            right-=1
        if left>right:#엇갈린 경우 작은 데이터와 피벗 교체
            #작은데이터, 피벗데이터
            array[right],array[pivot]=array[pivot],array[right]
        else: #엇갈리지 않았을 경우 작은 데이터와 큰 데이터 교체
            array[left],array[right]=array[right],array[left]
    
    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array,start,right-1)
    quick_sort(array,right+1,end)
    
quick_sort(array,0,len(array)-1)
print(array)

파이썬 장점을 살린 퀵 정렬 소스코드

array = [5,7,9,0,3,1,6,2,4,8]
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)

print(quick_sort(array))

퀵 정렬의 시간 복잡도 : O(NlogN) , 하지만 최악의 경우 시간 복잡도는 O(N^2)이다. 하지만 파이썬은 기본 정렬 라이브러리(sorted)를 이용하면 O(NlogN)을 보장해준다.