알고리즘 - 병합 정렬
병합 정렬은 배열을 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘입니다. 먼저, 정렬된 배열 a, b를 반복문을 이용한 단순 병합을 해보겠습니다. 이럴 경우 병합하는데 필요한 시간 복잡도는 O(n)입니다. def merge_sorted_list(a, b, c) -> None: pa, pb, pc = 0, 0, 0 # 각 배열의 커서 na, nb, nc = len(a), len(b), len(c) # 각 배열의 크기 print(f'배열 a: {a}') print(f'배열 b: {b}') while pa None: if left < right: center =..
2020. 12. 8.
알고리즘 - 셸 정렬
단순 삽입 정렬의 장점은 살리고 단점을 보완해, 더 빠르게 정렬하는 알고리즘을 셸 정렬이라고 합니다. 셸 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나누어, 각 그룹별로 정렬을 수행합니다. 그리고 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄이는 방법입니다. 위와 같이 8개의 원소를 갖는 배열이 있을 때, 단순 삽입 정렬은 1을 맨 앞으로 이동시킬 때 총 7번 이동시켜야 합니다. 셸 정렬을 하면 먼저 서로 4칸씩 떨어진 원소를 꺼내어 4개의 그룹으로 나누고 그룹별로 각각 정렬합니다. (8, 5), (4, 2), (9, 7), (6, 1) --> (5, 8), (2, 4), (7,9), (1, 6) 이렇게 4칸 떨어진 원소를 정렬하는 방법을 4-정렬이라고 합니다. 이어서 2칸 떨어진 원소를 ..
2020. 11. 24.
