카테고리 없음
[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 15
호랑구야
2023. 7. 3. 09:00
* 수업은 JS 기반이지만 Python으로 구현
Section 15
더 빠른 정렬들
- 시간복잡도를 O(N^2)에서 O(N*logN)으로 향상시킨다.
- 효율성과 간단함은 상충관계로, 알고리즘이 효율적일수록 이해하는데 시간이 걸린다.
합병 정렬: 소개
분할, 정렬, 합병 세 가지 조합으로 이루어져 있다. 0개 요소 혹은 1개 요소 배열이 이미 정렬되어 있는 상태라는 것을 활용한다. 배열을 더 작은 배열로 나누어 0개 혹은 1개가 되면, 옆의 요소와 비교하여 정렬 후 합병을 한다. 이것을 모든 요소가 수행하여 배열을 완성한다.
배열 정렬: 소개
- 두 정렬된 배열을 합병하는 헬퍼 함수를 먼저 구현하는 것이 유용하다.
- 정렬된 두 배열이 주어지면 헬퍼 함수가 정렬된 새 배열을 만든다.
- 헬퍼 함수는 O(n+m)의 시간과 O(n+m)의 공간으로 실행된다.
- n은 첫 번째 배열의 크기
- m은 두 번째 배열의 크기
배열 정렬: 구현
- 빈 배열을 만든다.
- 각 배열마다 가장 작은 값을 확인한다.
- 카운터 2개를 이용한 while 루프를 만든다.
- 두 카운터는 0부터 시작한다.
- 두 카운터가 각각 배열 끝에 도달하지 않았다면, 첫 번째 배열의 첫 번째 항목과 두 번째 배열의 첫 번째 항목을 비교한다.
- 만약 첫 번째 배열의 첫 번째 항목이 더 작았다면, 첫 번째 배열의 두 번째 항목과 두 번째 배열의 첫 번째 항목을 비교한다.
- 이런 방식을 반복하다가 한 배열이 완료된다면, 나머지 배열의 남은 값은 전부 결과 배열에 넣는다.
# Merge Sort Helper
def Merge(arr1, arr2):
# 결과 배열 선언
result = []
# 카운터 i: arr1용 j: arr2용
i = 0
j = 0
# i가 배열1의 길이보다 작고, j가 배열2의 길이보다 작은 동안 루프 진행
while((i < len(arr1)) and (j < len(arr2))):
# 함수 진행 확인 용도
print(i, j)
# 각 배열의 원소를 비교하여 더 작은 것이 결과 배열로 들어감
# 두 값이 같을 때에는 일단 arr2의 요소를 넣고
# 나머지를 arr2의 그 다음값과 비교하여
# 더 작은 값인 arr1의 요소가 result안으로 들어가
# 결과에 문제가 없으므로 그대로 진행
if arr1[i] < arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
# 함수 진행 확인 용도
print(result)
# 만약 루프가 끝난 후, 배열1 혹은 배열2에 남은 요소가 있다면 결과 배열에 넣기
while(i < len(arr1)):
result.append(arr1[i])
i += 1
while(j < len(arr2)):
result.append(arr2[j])
j+= 1
# 결과 배열 return
return result
Merge([1, 3, 6], [2, 4, 5, 7, 8, 9])
Merge([1, 3, 4, 6], [2, 4, 5, 7, 8, 9])합병 정렬: 구현
- 배열을 반으로 나누고, 하위 배열이 0 혹은 1개의 요소만 남을 때까지 반복한다.
- 작은 하위 배열이 준비되면, 합병 함수를 이용하여 배열을 다시 합치고 원래의 길이가 될 때까지 반복한다.
- 배열을 다시 합친 이후 가장 마지막에 합병된 배열을 반환한다.
# Merge Sort
def MergeSort(arr):
# 만약 배열의 수가 1보다 작거나 같다면 배열을 반환하라
# base case, 함수의 재귀가 멈추는 시점
if len(arr) <= 1:
return arr
# 배열의 중간 지점 변수
mid = int(len(arr) / 2)
# 매번 다른 데이터를 이용해 함수를 호출하는 부분
left = MergeSort(arr[:mid])
right = MergeSort(arr[mid:])
# 함수 진행 확인 용도
print('L: ', left, 'R: ', right)
return Merge(left, right)# Merge Sort
def MergeSort(arr):
# 만약 배열의 수가 1보다 작거나 같다면 배열을 반환하라
# base case, 함수의 재귀가 멈추는 시점
if len(arr) <= 1:
return arr
# Merge Sort Helper
def Merge(arr1, arr2):
# 결과 배열 선언
result = []
# 카운터 i: arr1용 j: arr2용
i = 0
j = 0
# i가 배열1의 길이보다 작고, j가 배열2의 길이보다 작은 동안 루프 진행
while((i < len(arr1)) and (j < len(arr2))):
# 함수 진행 확인 용도
print('i: ', i, 'j: ', j)
# 각 배열의 원소를 비교하여 더 작은 것이 결과 배열로 들어감
# 두 값이 같을 때에는 일단 arr2의 요소를 넣고
# 나머지를 arr2의 그 다음값과 비교하여
# 더 작은 값인 arr1의 요소가 result안으로 들어가
# 결과에 문제가 없으므로 그대로 진행
if arr1[i] < arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
# 함수 진행 확인 용도
print('Rst: ', result)
# 만약 루프가 끝난 후, 배열1 혹은 배열2에 남은 요소가 있다면 결과 배열에 넣기
while(i < len(arr1)):
result.append(arr1[i])
i += 1
while(j < len(arr2)):
result.append(arr2[j])
j+= 1
# 결과 배열 return
return result
# 배열의 중간 지점 변수
mid = int(len(arr) / 2)
# 매번 다른 데이터를 이용해 함수를 호출하는 부분
left = MergeSort(arr[:mid])
right = MergeSort(arr[mid:])
# 함수 진행 확인 용도
print('M: ', mid, 'L: ', left, 'R: ', right)
return Merge(left, right)
MergeSort([3, 2, 5, 13, 8, 23, 0, 9])합병 정렬: 빅오 복잡도
배열 n개를 반으로 나누는 것을 반복하여 1개가 될 때까지 수행한다면 반으로 나누는 횟수는 log n번이 된다. 8개의 배열은 반으로 나누는 행위를 3번 수행한다. 그리고 나눈 것끼리 매번 n번의 비교가 있기 때문에 n log n이 된다. 데이터에 구애받지 않는 정렬 알고리즘에서 최선은 O(n log n)을 활용할 수 있다.
ex) 8개 배열 나누기
8
4 4
2 2 2 2
1 1 1 1 1 1 1 1
- 시간복잡도
- Best: O(n log n)
- Average: O(n log n)
- Worst: O(n log n)
- 공간복잡도
- O(n)
반응형