[코드] 무작위 알고리즘과 퀵 정렬 / 파이썬으로 퀵정렬

 

 

 

관련 도서 : 컴퓨터과학이 여는 세계_이광근_121쪽_무작위

잠깐!* 퀵정렬 : 가장 맨 앞(왼쪽)의 수를 기준으로 정하고, 이 값보다 작으면 왼쪽, 크면 오른쪽으로 옮겨 정렬한다. 퀵정렬에 대해 더 알고 싶다면 이 블로그 추천 >> gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

왜 무작위 알고리즘이랑 퀵정렬을 함께 이야기하는 거지?

퀵정렬의 보통 비용(시간복잡도)는 O(n logn) . 그러나 최악의 경우, (이미 정렬이 다 되어 있는 경우)는 O(n^2)라는 비용이 든다. 보통 정렬이 다 된 자료를 제공하는 경우는 드물기는 하지만, 어찌되었든 이런 퀵정렬 최악의 경우를 벗어나는 방법이 있을까? 라는 의문에 대해 답하는 내용이다.

 

 책에서는 문제를 해결하는 여러 알고리즘 중 하나로 '무작위' 알고리즘(120쪽)을 이야기하는데, 여기에서 퀵 정렬이 예시로 등장한다. 때로는 의도없이 선택의 기로에서 무심하게 동전을 던져 결정하는 방법이 알고리즘을 튼튼히 하는 데 쓰일 수 있다는 것. 모든 단계가 정해진 과정으로 딱 맞춰 움직이는 알고리즘의 경우, 자칫 입력값에 따라 큰 폭으로 엉뚱한 답을 만들 수 있는데, 유연함을 주는 것이 무작위 알고리즘이라고 한다.

>> 예를 들어 최단거리를 구할때, 현재 위치에서 가장 가까운 도시를 선택하는 규칙으로 이동할 수도 있지만, 이것이 항상 최단거리를 보장하는 것은 아니다. 그래서 중간 중간에는 갈림길에서 무작위로 도시를 택해 이동하는 방식을 섞는 것. 꽤 효과가 있다고 한다.

퀵정렬이 최악의 경우를 맞이 하는 것은, 항상 가장 맨 앞의 숫자가 피벗(pivot : 기준으로 선택한 원소)이라는 규칙때문에 발생한다. 따라서 이를 위해 피벗을 무작위로 선택하는 방법이 대안이 될 수 있다는 것.

* 퀵정렬의 비용줄이기(?)에 관심이 생겼다면 m.blog.naver.com/PostView.nhn?blogId=ljy9378&logNo=221508655059&proxyReferer=https:%2F%2Fwww.google.com%2F 추천

아직 모르는 게 한참 많다보니, 이런 문제상황에 대한 대안들이 너무나 신기하고 재밌다.

 

그럼 퀵정렬을 파이썬으로 구현한 코드를 확인해보자!

 

def part( list, pivot ) :   # 주어진 리스트를 기준값 pivot으로 나누는 함수

    left = [ ]        # 왼쪽에 놓일 수(원소)들이 들어갈 리스트

    right = [ ]

    while ( list != [ ] ) :   # 리스트에 정렬할 것이 없을 때까지 반복 

        head = list.pop(0)    # 리스트의 첫번째 값을 꺼내 head에 저장, 전부 꺼낼 때까지 반복됨

        if head <= pivot :    # head 값이 pivot보다 작은(작거나 같은) 경우,

            left = left + [head]        # left 에 추가함

        else :    # head가 pivot보다 큰 경우

            right  = right + [head]   # right 에 추가함

    return ( left, right )  # pivot을 기준으로 나뉜 left, right 리스트를 돌려줌.

 

def qsort ( list ) :    # 위 함수랑 엮어서 완성되는 퀵정렬

    if list == [ ] :    # 정렬할 값이 없는 경우

        return list      # 리스트를 그냥 돌려줌 

    else :             

        pivot = list[0]    # 리스트의 가장 첫번째 값을 pivot으로 정함

        left, right = part(list[1:], pivot)  #part에 2번째원소부터 전체와(pivot을 제외함), pivot값을 넣어 나뉜 리스트 저장.

        print("pivot =",pivot,"left=", left, "right=", right ) # 중간 진행과정을 보고자 넣은 부분임

        return qsort(left) +[pivot] + qsort(right)  # 왼쪽 / 오른쪽 분할된 리스트는 퀵정렬을 반복하여 합쳐서 돌려줌.

 

#테스트해보기

list = [5,1,3,6,4,2]

qsort(list)

출력해보면,