[정렬] 병합정렬, 퀵정렬

1. 병합정렬

자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬한다.

앞서 말한 버블 정렬, 삽입정렬, 선택정렬에 비해 속도가 빠르다는 장점이 있음.

 

분할 단계

1단계 :               8, 1, 4, 3, 2, 5, 10, 6

2단계 :      8, 1, 4, 3                  2, 5, 10, 6

3단계 :  8, 1         4, 3            2, 5          10, 6

4단계 : 8     1      4     3       2       5      10         6

 

병합 단계

1단계 : 8     1      4     3       2       5      10         6

그냥 병합하는 것이 아닌 각 숫자의 크고 작음을 비교해서 병합한다.

2단계 :  1, 8         3, 4            2, 5          6, 10 

3단계 :      1, 3, 4, 8                  2, 5, 6, 10

4단계 :               1, 2, 3, 4, 5, 6, 8, 10

 

반복수행하는 부분이 있기 때문에 재귀함수를 쓴다.

def mSort(ns):
    #분할단계
    #갯수가 2보다 작을때까지 쪼갠다
    if len(ns)<2:
        return ns
    
    midIdx = len(ns) // 2
    leftNums = mSort(ns[0:midIdx])
    rightNums = mSort(ns[midIdx:len(ns)])
    
    #병합단계
    mergeNums = []
    leftIdx = 0; rightIdx = 0
    while leftIdx < len(leftNums) and rightIdx < len(rightNums):
        #자리바꿈
        if leftNums[leftIdx] < rightNums[rightIdx]:
            mergeNums.append(leftNums[leftIdx])
            leftIdx += 1
        else:
            mergeNums.append(rightNums[rightIdx])
            rightIdx += 1
    
    mergeNums = mergeNums + leftNums[leftIdx:]
    mergeNums = mergeNums + rightNums[rightIdx:]
    
    return mergeNums
    
nums = [8, 1, 4, 3, 2, 5, 10, 6]
print(mSort(nums))

2. 퀵정렬

기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.

 

1단계 :               8, 1, 4, 3, 2, 5, 4, 10, 6, 8 ---기준값5

2단계 :          1, 4, 3, 2, 4       5        8, 10, 6, 8  ---기준값 3, 6

3단계 :     1, 2       3,  4, 4       5                  6  8, 8, 10 ---기준값 4, 8

4단계 :     1, 2       3,  4, 4       5                  6  8, 8, 10

 

def qSort(ns):
    if len(ns)<2:
        return ns
    
    midIdx = len(ns)//2
    midVal = ns[midIdx]
    
    smallNums = []; sameNums = []; bigNums = []
    
    for n in ns:
        if n < midVal:
            smallNums.append(n)
        elif n == midVal:
            sameNums.append(n)
        else:
            bigNums.append(n)
        
    return qSort(smallNums) + sameNums +qSort(bigNums)

nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(qSort(nums))

sameNums 이외의 것들은 다시 qSort를 돌려서 얻어낸다.