버블 소트(Bubble Sort)

인접한 두 원소를 반복적으로 비교하여 값의 크기가 반대라면 교환하는 방식으로 동작합니다. 한 라운드가 완료되면 가장 큰 원소가 배열의 끝으로 이동하며, 이후 반복 시에는 이미 정렬된 요소를 제외하고 비교 대상을 줄일 수 있습니다. 교환 작업이 한 사이클 동안 전혀 일어나지 않는 경우, 전체 데이터가 정렬되었음을 의미하므로 알고리즘을 조기에 종료할 수 있습니다.

def bubble_sort(target_list):
    n = len(target_list)
    comparison_cnt = 0
    
    for i in range(n - 1):
        swapped = False
        
        # 마지막 i개 요소는 이미 정렬됨
        for j in range(0, n - i - 1):
            comparison_cnt += 1
            
            if target_list[j] > target_list[j + 1]:
                target_list[j], target_list[j + 1] = target_list[j + 1], target_list[j]
                swapped = True
                
        if not swapped:
            break
            
    return target_list, comparison_cnt

dataset = [9, 1, 22, 31, 45, 3, 6, 2, 11]
sorted_result, ops = bubble_sort(dataset.copy())
print("Result:", sorted_result)
print("Comparisons:", ops)

선택 소트(Selection Sort)

정렬되지 않은 구간에서 최솟값을 발견하면, 그 위치를 찾아 현재 진행 중인 정렬 시작 지점과 스왑합니다. 매번 순회할 때마다 탐색 범위의 경계가 하나씩 뒤로 밀리므로, 최종적으로 모든 원소가 올바른 위치로 배정됩니다. 비교 횟수는 입력 크기 n에 대해 항상 n(n-1)/2회가 소요되므로 시간 복잡도는 고정적으로 O(n²)입니다.

def selection_sort(target_list):
    n = len(target_list)
    comp_cnt = 0
    
    for i in range(n):
        min_idx = i
        
        # i 이후 구간 중 최소값 인덱스 탐색
        for j in range(i + 1, n):
            comp_cnt += 1
            if target_list[j] < target_list[min_idx]:
                min_idx = j
                
        # 탐색된 최소값과 현재 위치 교체
        target_list[i], target_list[min_idx] = target_list[min_idx], target_list[i]
        
    return target_list, comp_cnt

data_pool = [9, 1, 22, 31, 45, 3, 6, 2, 11]
processed_data, count = selection_sort(data_pool.copy())
print("Sorted:", processed_data)
print("Operations:", count)

삽입 소트(Insertion Sort)

배열을 이미 처리된 부분과 미처리 부분으로 구분합니다. 미처리의 다음 원소를 가져와서, 처리된 부분의 오른쪽부터 왼쪽으로 역순 비교하며 알맞은 자리를 찾아 삽입합니다. 포커 게임에서 카드를 손에 쥘 때 자연스러운 배치 순서를 찾아가는 과정과 유사합니다. 데이터가 대부분 정렬되어 있거나 규모가 작은 경우 매우 우수한 성능을 보이며, 평균 및 최악의 시간 복잡도는 O(n²), 최선은 O(n)입니다.

def insertion_sort(items):
    arr = items.copy()
    
    for current_idx in range(1, len(arr)):
        temp_val = arr[current_idx]
        prev_idx = current_idx - 1
        
        # 정렬된 구간에서 temp_val보다 큰 값을 우측으로 한 칸씩 밀기
        while prev_idx >= 0 and arr[prev_idx] > temp_val:
            arr[prev_idx + 1] = arr[prev_idx]
            prev_idx -= 1
            
        # 빈 공간에 값 배치
        arr[prev_idx + 1] = temp_val
        
    return arr

cards = [3, 34, 5, 34, 23, 45, 56, 3]
ordered_cards = insertion_sort(cards)
print("Ordered List:", ordered_cards)

퀵 소트(Quick Sort)

분할 정복(Divide and Conquer) 전략을 기반으로 합니다. 기준 값(Pivot)을 선정하여 이를 기준으로 작고 큰 데이터를 양쪽으로 분리한 후, 각 부분 집합에 대해 동일하게 재귀 호출합니다. 피벗 선정 및 파티션 방식에 따라 성능 편차가 있으며, 일반적인 경우 O(n log n)의 빠른 속도를 자랑하지만, 동일한 값이 많거나 이미 정렬된 데이터에서 피벗 선정이 부적절하면 O(n²)로 둔화될 수 있습니다. 불안정(Unstable) 정렬 알고리즘입니다.

def partition(sub_array, low, high):
    pivot_val = sub_array[high]
    border_idx = low - 1
    
    for scan_idx in range(low, high):
        if sub_array[scan_idx] <= pivot_val:
            border_idx += 1
            sub_array[border_idx], sub_array[scan_idx] = sub_array[scan_idx], sub_array[border_idx]
            
    sub_array[border_idx + 1], sub_array[high] = sub_array[high], sub_array[border_idx + 1]
    return border_idx + 1

def quick_sort_recursive(arr, left, right):
    if left < right:
        split_point = partition(arr, left, right)
        quick_sort_recursive(arr, left, split_point - 1)
        quick_sort_recursive(arr, split_point + 1, right)

raw_numbers = [96, 14, 10, 9, 6, 99, 16, 5, 1, 3, 2, 4, 1, 13, 26, 18, 2, 45, 34, 23, 1, 7, 3, 22, 19, 2]
print("Initial State:", raw_numbers)
quick_sort_recursive(raw_numbers, 0, len(raw_numbers) - 1)
print("Final State:", raw_numbers)

이진 트리(Binary Tree)

루트(Root) 노드를 최상위에 두고, 각 노드가 최대 두 개의 하위 노드(좌측, 우측)를 보유할 수 있는 비선형 자료구조입니다. 노드 단위로 저장되며, 데이터를 검색하거나 계층적 구조를 표현할 때 널리 사용됩니다. 트리를 순회하는 대표 방식은 전위(NLR), 중위(LNR), 후위(LRN)입니다. 후위 순회는 주로 서브트리의 계산 결과(예: 합산, 최대값 추출)를 부모에게 전달해야 하는 경우에 유용합니다.

class TreeNode:
    def __init__(self, data=0, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class BinaryTree:
    def __init__(self, root_node=None):
        self.root = root_node
        self.total_sum = 0
        self.max_value = float('-inf')
        
    def post_order_traverse(self, node):
        if node is None:
            return
            
        self.post_order_traverse(node.left)
        self.post_order_traverse(node.right)
        
        if node.data > self.max_value:
            self.max_value = node.data
        self.total_sum += node.data

# 트리 구성
node_left_leaf = TreeNode(data=1)
node_mid_left = TreeNode(data=2, left=node_left_leaf)
node_right_leaf_1 = TreeNode(data=3)
node_right_leaf_2 = TreeNode(data=4)
node_mid_right = TreeNode(data=5, left=node_right_leaf_1, right=node_right_leaf_2)
node_bottom = TreeNode(data=6, left=node_mid_left, right=node_mid_right)
root_structure = TreeNode(data=10, left=node_bottom, right=TreeNode(data=8))

tree_obj = BinaryTree(root_structure)
tree_obj.post_order_traverse(tree_obj.root)

print("Sum of all nodes:", tree_obj.total_sum)
print("Maximum value:", tree_obj.max_value)