퀵정렬의 분할알고리즘

def partition(al, low, high):

    # al[low:high] 축값은 al[high-1]에 있다.

    v=al[high-1]

    j=low               # j는 큰 값들의 시작위치를 나타낸다

    for i in range(low,high-1):

        if al[i]<=v:    # 현재 값이 축값보다 같거나 작다면 큰값들의 앞의 위치와 swap한다.

            if i>j: al[i],al[j]=al[j],al[i]     # 위치가 서로 다르면 swap한다

            j=j+1                               # 큰 값들의 시작위치는 1 증가한다.

    al[j],al[high-1]=v,al[j]      # 마지막으로 축값과 큰 값들의 시작위치를 swap한다.

    return j                         # 축값의 위치를 돌려준다.

 

------------------------------------------------------------------------------------------------

위의 알고리즘은 아주 간단하고 멋지기 짝이 없다.

실행도중의 리스트가 다음과 같이 분할 되어 있다고 생각하자.

 

[축값보다 작은 값들의 모임][축값보다 큰 값들의 모임-시작위치 j ][아직 남은 리스트들-시작위치 i ][축값]

 

만약 위치 i의 값이 축값보다 작다면 축값보다 작은 값들의 리스트는 한개 증가해야 한다.

      j번째 값과 i번째 값을 서로 바꾸어 주면 이 문제가 해결된다.

 

만약 위치 i의 값이 축값보다 크다면 그냥 축값보다 큰 값들의 모임이 한개 증가한댜. 아무것도 해줄 필요가 없다.

-------------------------------------------------------------------------------------------------------

처음에 축값보다 작은 놈이 나온다면 축값보다 작은 리스트의 길이는 1이 되고 축값보다 큰 리스트의 시작위치는

1이 증가한다. 만약 또 축값보다 작은 놈이 나온다면 마찬가지로 작은 리스트의 길이는 증가하고

축값보다 큰 리스트의 시작위치는 1이 증가한다.

 

그 다음에 축값보다 큰 값이 나왔다면 이때 j는 바로 이 위치를 가리키게 된다. 그래서 위의 알고리즘은

모든 경우에 맞게 동작하는 것이다.

 

리스트의 끝에 다왔을 때에도 j의 위치와 high-1의 위치를 바꾸어주면 된디.

이것도 [축값이 가장 큰 경우든, 축값이 가장 작은 경우든] 모든 경우에 맞게 동작하는 것이다.

==================================================================================

그래서 위와 같은 알고리즘이 나오게 된다. 정말 멋있다.