TIL no.10- 퀵 정렬

퀵 정렬

퀵 정렬은 분할 정렬과 마찬가지로 Devide and Conquer와 거의 동일한 방법을 사용한다. 병합 정령이 후위 순회(왼쪽 자식 노드와 오른쪽 자식 노드가 끝나면 부모 노드로 이동) 방식을 사용했다면, 전위 순회(왼쪽 자식 노드와 오른쪽 자식 노드가 갈라지기 전 파티션(중심값)을 기준으로 왼쪽과 오른쪽으로 분리) 방식을 사용한다. 리스트 안에 선택한 원소를 피벗(pivot) 이라고 한다.

퀵 정렬 코드

def Qsort(lt, rt):
    if lt<rt:
        pos=lt
        pivot = arr[rt]
        for i in range(lt, rt):
            if arr[i] <= pivot:
                arr[i], arr[pos]=arr[pos], arr[i]
                pos+=1
        arr[rt], arr[pos]=arr[pos], arr[rt]
        Qsort(lt, pos-1)
        Qsort(pos+1, rt)


arr=[45, 21, 23, 36, 15, 67, 11, 60, 20, 33]
print("before", end="")
print(arr)
Qsort(0, 7)
print()7
print("after", end="")
print(arr)

퀵 정렬 과정

arr의 리스트 안에서 pivot 값을 arr[rt]로 정한다. 여기서 arr[rt]는 33이다.
pivot 33을 중심으로 피봇값 보다 작은 것은 왼쪽으로 큰 것은 오른쪽을 나눈다.

pos=lt로 정의해 놓고 for i in range(lt, rt)를 이용해 자리를 스와핑 해서 파티션 작업을 해준다. 그리고 pivot=33은 자기 자리를 찾은 것이고 왼쪽 영역과 오른쪽 영역을 분화해서 다시 함수가 호출된다.

lt<rt가 참이 될 때까지 함수는 계속 호출된다.