Developer Wony Story

병합 정렬이란?

재귀 용법을 활용한 정렬 알고리즘으로 배열을 절반으로 잘라나가고 이를 다시 정렬된 배열의 형태로 합병하며 정렬함.

알고리즘 구현

병합 정렬은 배열을 나누는 함수, 나누어진 배열을 하나로 합치는 함수 2가지를 구현해야 함

1. merge 함수

def merge(left, right):
    merged = list()
    left_index, right_index = 0, 0
    
    while len(left) > left_index and len(right) > right_index:
        if left[left_index] > right[right_index]:
            merged.append(right[right_index])
            right_index += 1
        else:
            merged.append(left[left_index])
            left_index += 1
    
    while len(left) > left_index:
        merged.append(left[left_index])
        left_index += 1
        
    while len(right) > right_index:
        merged.append(right[right_index])
        right_index += 1
        
    return merged

2. merge_split 함수(실질적인 병합 정렬 역할의 함수)

def merge_split(data):
    if len(data) <= 1:
        return data
    
    mid = len(data) // 2
    left = merge_split(data[:mid])
    right = merge_split(data[mid:])
    
    return merge(left, right)

시간 복잡도

각 단계별로 O(N)으로 실행되고, 그 단계들은 logN개만큼 만들어지므로 O(logN)의 시간 복잡도를 가진다.

결국 이 모든 과정을 통합하면 O(NlogN)이라는 시간 복잡도가 나오게 된다.

1. 퀵 정렬이란?

• 기준점(Pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 에디터는 오른쪽으로 모아서 정렬을 하는 것
• 각 왼쪽, 오른쪽으로 나눈 것은 재귀 용법을 통해 다시 왼쪽, 오른쪽으로 나눔
• 반환하는 값은 [정렬된 왼쪽 리스트] + [Pivot] + [정렬된 오른쪽 리스트]

2. 알고리즘 구현

def qsort(data):
    if len(data) <= 1:
        return data
    left, right = list(), list()
    pivot = data[0]
    for index in range(1, len(data)):
    	if pivot > data[index]:
            left.append(data[index])
        else:
            right.append(data[index])
    return qsort(left) + [pivot] + qsort(right)

파이썬의 list comprehension을 사용한다면 위의 코드보다 짧게 구현이 가능해진다.

def qsort(data):
    if len(data) <= 1:
    	return data
    pivot = data[0]
    left = [ item for item in data[1:] if pivot > item ]
    right = [ item for item in data[1:] if pivot <= item ]
    return qsort(left) + [pivot] + qsort(right)

3. 시간복잡도

일반적으로는 O(N logN)이지만, 최악의 경우인 맨 처음 pivot이 배열 내에서 가장 크거나 가장 작으면 모든 데이터를 비교하는 상황이 나오므로 O(N^2)이 될 수 있다.

1. 삽입정렬이란?

두번째 인덱스부터 시작하여 해당 인덱스 앞에 있는 데이터부터 비교해서 그 값이 더 크다면 값을 서로 교환.

2. 구현코드

def insertion_sort(data):
	for stand in range(len(data)-1):
    		for idx in range(stand+1, 0, -1):
            		if data[idx] < data[idx-1]:
                		data[idx], data[idx-1] = data[idx-1], data[idx]
                        else:
                		break
	return data

3. 시간복잡도

• 최악의 경우: O(N^2)
• 완전 정렬이 된 경우: O(N)