Algorithm - 퀵 정렬(선수지식)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

선수지식(algorithm)

간단한 예제를 통해 퀵 정렬의 원리를 이해하고자 한다.

 

 

---

 

예시(Python)

답안

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)
        
if __name__ == "__main__":
    arr = [45, 21, 23, 36, 15, 67, 11, 60, 20, 33]
    print('Before sort : ', end='')
    print(arr)
    Qsort(0, 9)
    print('After sort : ', end='')
    print(arr)

 

출력

Before sort : [45, 21, 23, 36, 15, 67, 11, 60, 20, 33]

After sort : [11, 15, 20, 21, 23, 33, 36, 45, 60, 67]

 

 

중요내용

1. 퀵 정렬은 전위순회(부모노드 -> 왼쪽 자식노드 -> 오른쪽 자식노드) 방식으로 진행된다.
2. 즉, 퀵 정렬이 실행되면 우선적으로 피봇값을 정하고 이를 중심으로 부모노드에서 파티션 작업이 이루어지며 해당 작업이 모두 끝나면 왼쪽 자식노드의 파티션 작업 -> 오른쪽 자식노드의 작업 순으로 전위순회가 이루어진다.
3. 파티션 작업은 피봇(중심축)을 중심으로 해당 값보다 작은 값은 피봇 기준으로 왼쪽으로 이동시키고, 큰 값은 오른쪽으로 이동시키는 작업을 의미한다. (마지막에는 피봇값과 변수 pos가 서로 스왑됨)
4. 참고로, 변수 pos는 특정 리스트 영역에서 파티션 작업이 시작되는 지점이며, 파티션 작업은 lt부터 rt-1까지 for문을 통해 수행된다.
5. 일반적으로 피봇값은 특정 리스트 영역의 rt(가장 우측 값)으로 정해진다. (for문에서 rt가 제외되는 이유)
6. 한편, 피봇값을 무엇으로 정하는지에 따라 해당 프로그램의 성능이 좌우될 수 있다.
7. arr[i], arr[pos] = arr[[pos], arr[i]는 두 리스트의 벨류 값을 스왑하는 코드이다. (파이썬 문법[스왑])