정렬: 병합정렬, 퀵정렬

병합정렬 (후위순회 방식)

자기의 영역을 lt와 rt로 (두개의 영역) 나누기

1개씩 있는 것은 이미 정렬되었다고 생각.

tmp라는 곳에 작은 순으로 넣은 후 arr에 해당 부분 넣기. (두 부분 합치기)

#병합정렬
def Dsort(lt, rt):
    if lt < rt:
        mid = (lt+rt) //2
        Dsort(lt, mid)
        Dsort(mid+1, rt)
        #왼쪽과 오른쪽 자식이 다 끝났으면 왼쪽과 오른쪽 자식 값들이 정렬되었다는 뜻
        #두 값 합치기 (본연의 일: 병합)
        p1 = lt
        p2 = mid +1
        tmp = []
        while p1 <= mid and p2 <= rt:
            if arr[p1] < arr[p2]:
                tmp.append(arr[p1])
                p1 += 1
            else:
                tmp.append(arr[p2])
                p2 += 1
        if p1<=mid: tmp=tmp+arr[p1:mid+1] #p1이 남았을 때
        if p2<=rt: tmp=tmp+arr[p2:rt+1] #p2가 남았을 때
        #tmp에 정렬된 것이 들어가서 arr에 복사해주기
        for i in range(len(tmp)):
            arr[lt+i] = tmp[i]

if __name__ == "__main__":
    arr = [23, 11, 45, 36, 15, 67, 33, 21]
    print("Before sort : ", end = ' ')
    print(arr)
    Dsort(0, 7)
    print()
    print("After sort :", end = ' ')
    print(arr)

#############결과###############3
#Before sort :  [23, 11, 45, 36, 15, 67, 33, 21]
#
#After sort : [11, 15, 21, 23, 33, 36, 45, 67]

 

 

퀵정렬 (전위순회 방식)

중심축 값인 pivot을 기준으로 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)

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)
    
#############결과###############3
#Before sort :  [45, 21, 23, 36, 15, 67, 11, 60, 20, 33]
#
#After sort : [11, 15, 20, 21, 23, 33, 36, 45, 60, 67]