[SW Intermediate] Linked List - 정렬

 Linked List - 정렬

---

삽입 정렬 

자료 배열의 모든 원소들을 앞에서 부터 차례대로 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아냄으로써 정렬을 완성한다.

 

[ 삽입 정렬의 정렬과정 ]

 

1) 정렬할 자료를 두 개의 부분집합 S 와 U로 가정한다.

- 부분집합 S: 정렬된 앞부분의 원소들

- 부분집합 U: 아직 정렬되지 않은 나머지 원소들

2) 정렬되지 않은 부분 집합 U의 원소를 하나씩 꺼내며 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아

삽입한다.

3) 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다.

4) 부분집합 U가 공집합이 되면 삽입 정렬이 완성된다.

 

✔ 시간 복잡도: O(n^2)

 

---

병합 정렬

여러 개의 정렬된 자료의 집합을 병합하여 한개의 정렬된 집합으로 만드는 방식이다.

 

1) 분할 정복 알고리즘 활용

-  자료를 최소 단위 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어낸다.

- Top- Down 방식

2) 시간 복잡도

- O(nlogn)

 

[ 분할 과정/병합 과정의 알고리즘 ]

 

def merge_sort(m): 
    if len(m) <= 1: # 사이즈가 0이거나 1인 경우, 바로 리턴
        return 
    # 1. divide 부분
    mid = len(m)//2
    left = m[:mid]
    right = m[mid:]
    
    # 리스트의 크기가 1이 될때까지 merge_sort 재귀호출
    left = merge_sort(left)
    right = merge_sort(right)
    
    # 2. concuer 부분: 분할 된 리스트들 병합
    return merge(left, right)
    
def merge(left, rigt):
    result = [] # 두 개의 분할 된 리스트를 병합하여 result 만듦
    
    while len(left) > 0 and len(right) > 0:
        # 양쪽리스트에 원소가 남아있는 경우
        # 두 서브 리스트의 첫 원소들을 비교하여 작은 것부터 result에 추가함
        
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    
    if len(left) > 0:
        result.extend(left)
    if len(right) > 0:
        result.extend(right)
    
    return result