웨일의 블로그 웨일의 블로그

정렬 알고리즘1. 버블 정렬def bubbleSort1(arr): for i in range(len(arr)): for j in range(len(arr) - 1): if arr[j] > arr[j + 1]: temp = arr[j] arr[j] = arr[j + 1] arr[j + 1] = temp def bubbleSort2(arr): idx = 0 temp = 0 while idx < len(arr): for i in range(len(arr) - 1): if arr[i + 1] < arr[i]: temp = arr[i] arr[i] = arr[i + 1] arr[i + 1] = temp idx += 1 arr = [3, 1, 5, 2, 4] bubbleSort2(arr) print(arr) 2. ..

머지소트는 분할 정복 카테고리에 속합니다. 숫자로 이루어진 수열이 반씩 나눠지며 하나만 남게 되는 과정이 분할이고, 각 파티션끼리 합쳐지는 과정이 정복입니다. 머지 소트의 시간복잡도는 O(NlogN)이라고 잘 알려져 있습니다. 왜 O(NlogN)일까요? 우선, 분할과정을 살펴봅시다. 단순히 생각해서 7개의 숫자로 이루어진 수열에서 숫자를 하나씩 떼어내려면 총 6번을 하나씩 떼어내야 합니다. 7보다 1만큼 작은 이유는 마지막에 숫자 두개만 남았을 때 한번만 떼어내면 되기 때문입니다. 숫자가 N개 있으면 N-1번 떼어내야 합니다. 따라서 N에 대해 선형적이므로 분할 과정은 O(N)입니다. 이제 정복 과정을 살펴봅시다. 정복은 같은 레벨의 파티션들을 쌍을 이룬 후, 정렬하며 하나의 파티션으로 병합하는 과정입니..