[파이썬] 퀵정렬

(1) 처음 시행만 해보면! (33을 pivot으로 하고 정지)

#병합정렬
def qsort(lt,rt) :
    if lt<rt :
        pos=lt #0으로 하면 안됨,분할된 부분의 시작점
        pivot=arr[rt] #그 영역의 맨 오른쪽 값, 9하면 안됨
        for i in range(lt,rt):
            if arr[i]<=pivot: #피봇보다 큰애는 그냥 넘어가는데 작은애 만나면
                arr[i], arr[pos]=arr[pos], arr[i]#이와 같이 스와프 해주고, pos에 1을 더해준다
                pos+=1
        arr[rt], arr[pos]=arr[pos], arr[rt]
        return

if __name__=='__main__' :
    arr=[45,21,23,36,15,67,11,60,20,33]
    print('before sort : ' , end='')
    print(arr)
    qsort(0,9) 
    print()
    print('after sort : ', end='')
    print(arr)

=>
before sort : [45, 21, 23, 36, 15, 67, 11, 60, 20, 33]
after sort : [21, 23, 15, 11, 20, 33, 36, 60, 45, 67]
: 33 기준으로 왼쪽은 작게, 오른쪽은 크게

(2)

#병합정렬
#파티션 작업을 하고 계속 분할 들어가기
def qsort(lt,rt) :
    if lt<rt :
        pos=lt #0으로 하면 안됨,분할된 부분의 시작점
        pivot=arr[rt] #그 영역의 맨 오른쪽 값, 9하면 안됨
        for i in range(lt,rt):
            if arr[i]<=pivot: #피봇보다 큰애는 그냥 넘어가는데 작은애 만나면
                arr[i], arr[pos]=arr[pos], arr[i]#이와 같이 스와프 해주고, pos에 1을 더해준다
                pos+=1
        arr[rt], arr[pos]=arr[pos], arr[rt]
        #전체작업 했으니 이젠 분할 #pos가 축이므로 pos 기준으로 나누기(가운데)
        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()
    print('after sort : ', end='')
    print(arr)