병합 정렬 배열을 앞부분 A 배열과 뒷부분 B 배열의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘입니다. 각 배열에서 주목하는 원소의 값을 비교하여 작은 쪽의 원소를 꺼내 새로운 배열 C에 저장합니다. 정렬을 마친 두 A, B 배열을 병합하는 코드입니다. def merge_sorted_list(a: Sequence, b: Sequence, c: MutableSequence) -> None: """정렬을 마친 배열 a와 b를 병합하여 c에 저장""" pa, pb, pc = 0, 0, 0 na, nb, nc = len(a), len(b), len(c) while pa < na and pb < nb: if a[pa] < b[pb]: c[pc] = a[pa] pa += 1 else: c..
자료구조/정렬 알고리즘
힙 정렬 힙은 '부모의 값 ≥ 자식의 값'인 관계가 항상 성립하는 완전 이진 트리입니다. 모든 자식의 노드가 2개인 트리 구조라는 것입니다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙입니다. 즉, 이러한 두 값의 대소관계가 일정하면 됩니다. 힙은 부모-자식 관계는 일정하지만, 형제 사이의 관계는 일정하지 않습니다. 아래 그림과 같이 7이 6보다 왼쪽에, 5와 4가 3과 2보다 왼쪽에 있지만, 아래 2와1보다 큰 3이 오른쪽에 있는 것처럼 말입니다. 이러한 이유로 부분 순서 트리라고도 합니다. 힙 정렬에서 배열의 인덱스는 다음과 같습니다. 이러한 순서로 배열을 힙에 저장하면 부모, 오른쪽 자식, 왼쪽 자식과는 다음과 같은 관계가 성립합니다. 원소 a[i] ① 부모: a[(i - 1) // 2] ② 왼..
도수 정렬 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘으로, 다음과 같은 과정을 통해 if 문을 사용하지 않고 for 문만 반복해서 정렬할 수 있습니다. 비교/교환 작업이 필요 없어 매우 빠르지만, 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 적용할 수 있습니다. ① 도수 분포표 만들기 ② 누적 도수 분포표 만들기 ③ 작업용 배열 만들기 ④ 배열 복사 도수 분포표 만들기 각 학생의 점수를 나타내는 배열 a가 있습니다. [5, 7, 0, 2, 4, 10, 3, 1, 3] (e.g. a[0]은 5점) 이때 0~10점을 나타내기 위한 원소 수 11개인 배열 f를 만듭니다. 그리고 각각 그 값을 넣어줍니다. for i in range(n): f[a[i]] += 1 도수 분포표 배열 [1, ..
셸 정렬 셸 정렬은 단순 삽입 정렬에서 특정 원소를 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아지는 단점을 보완한 정렬 알고리즘입니다. 비교하는 횟수를 확 줄인 알고리즘이죠. 배열 [8, 1, 4, 2, 7, 6, 3, 5]를 셸 정렬로 정렬하는 예시입니다. 먼저 서로 4칸씩 떨어진 원소를 꺼내어 (8, 7), (1, 6), (4, 3), (2, 5)의 4개의 그룹으로 나눈 후 각자 따로 정렬합니다. 그럼 다음과 같이 [7, 1, 3, 2, 8, 6, 4, 5]가 됩니다.(4-정렬) 다음은 2칸 떨어진 원소를 모두 꺼내 (7, 3, 8, 4), (1, 2, 6, 5) 두 그룹으로 나누고, 각각 정렬을 수행합니다.(2-정렬) 마지막으로 1칸 떨어진 배열, 즉 배열 전체에 단순 삽입 정렬을 적용하면 ..
단순 선택 정렬 단순 선택 정렬이란 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘입니다. 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택하고, 정렬하지 않은 부분의 맨 앞 원소와 교환합니다. def selection_sort(a: MutableSequence) -> None: n = len(a) for i in range(n - 1): min = i for j in range(i+1, n): if a[j] < a[min]: min = j a[i], a[min] = a[min], a[i] 예시: [6, 4, 1, 7, 3, 9, 8] ① 먼저 배열에서 가장 작은 원소와 아직 정렬하지 않은 부분(배열 전체)의 첫번째 원소와 교환합니다. → [1, 4,..
버블 정렬 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘입니다. 아래 예시처럼 n개 원소의 배열에서 처음 교환 과정(패스)에서는 비교 횟수가 n - 1회, 다음 패스에서는 비교 횟수가 n - 2회로 최종적으로 시간 복잡도는 O(n^2)입니다. from typing import MutableSequence def bubble_sort(a: MutableSequence) -> None: n = len(a) for i in range(n - 1): for j in range(n-1, i, -1): if a[j-1] > a[j]: a[j-1], a[j] = a[j], a[j-1] 처음에는 이 코드가 이해가 되지 않았는데, 우측의 a[j-1], a[j]를 (a[j-1], a[j]) ..
