알고리즘 - Sort 정렬 (Merge sort, Quick sort), Python 코드

Merge Sort (병합정렬)

- 일반적인 방법으로 구현했을 때 이 정렬은 안정정렬에 속하며, 분할 정복 알고리즘 중의 하나이다.

- 분할 정복 알고리즘 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 대개 순환호출을 이용하여 구현한다. 

- 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

 

<병합 정렬의 단계>
- 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
- 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
- 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 병합한다.

 

Merge sort 알고리즘의 특징

장점 : 크기가 큰 레코드를 연결리스트를 이용하여 정렬할 경우 효율적임, 데이터 분포에 영향을 덜 받는다. 

단점 : 크기가 큰 레코드들을 그냥 정렬할 경우 시간 낭비가 심함 (연결리스트 활용하여 해결)

 

 

Python으로 나타낸 Merge sort

#best : nlogn
#avg : nlogn
#worst : nlogn
def mergeSort(arr) :
    if len(arr) > 1 :
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:] 
        mergeSort(L)
        mergeSort(R)    
        i, j, k = 0, 0, 0 
        while i < len(L) and j < len(R) :
            if L[i] < R[j] :
                arr[k] = L[i]
                i += 1
            else :
                arr[k] = R[j]
                j += 1
            k += 1
            
        while i < len(L) :
            arr[k] = L[i]
            i += 1
            k += 1
        while j < len(R) :
            arr[k] = R[j]
            j += 1
            k += 1
        return arr

ll = [1, 2, 3, 2, 5, 6]
print(mergeSort(ll))

 

 

 

Quick sort (퀵정렬)

- 퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다.
- 분할 정복 알고리즘 : 병합 정렬과 달리 리스트를 비균등하게 분할한다. 

- 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

- 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다

 

 

<퀵 정렬의 단계>
- 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
- 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
- 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

 

Quick sort 알고리즘의 특징

장점 : 속도가 빠르다. (가장 빠름)

단점 : 이미 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

 

Python으로 나타낸 Quick sort

#quick sort
def partition(arr, low, high):
    i = (low - 1)
    pivot = arr[high]

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return (i+1)

def quickSort(arr, low, high):
    if len(arr) == 1:
        return arr
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
        
        
        
def Quick(arr) :
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    less, equal, more = [], [], []
    for num in arr:
        if num < pivot:
            less.append(num)
        elif num > pivot:
            more.append(num)
        else:
            equal.append(num)
    return Quick(less) + equal + Quick(more)

 

 

 

 

 

 

[선택, 삽입, 버블 정렬] 

2023.04.05 - [알고리즘] - 알고리즘 - Sort 정렬 (Selection sort, Insertion sort, Bubble sort), Python 코드

알고리즘 - Sort 정렬 (Selection sort, Insertion sort, Bubble sort), Python 코드