[2주차] 정렬 알고리즘

정렬 알고리즘

 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘

 

목차

 

1. 기본 정렬

1-(1) 버블 정렬 (Bubble Sort)

1-(2) 선택 정렬 (Selection Sort)

1-(3) 삽입 정렬 (Insertion Sort)

 

2. 심화 정렬

2-(1) 퀵 정렬 (Quick Sort)

2-(2) 병합 정렬 (Merge Sort)

2-(3) 기수 정렬 (Radix Sort)

 

3. 이진 탐색(Binary search)

 

 

 

 

 

 

1. 기본 정렬

• 1-(1) 버블 정렬 (Bubble Sort)

인접한 두 원소를 비교해서 큰 값을 뒤로 보내는 방식.

특징: 가장 단순하지만 비효율적이다. [시간 복잡도 : O(n²)]

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):  # 마지막은 이미 정렬됨
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(bubble_sort([5, 3, 8, 4, 2]))

 

• 1-(2) 선택 정렬 (Selection Sort)

매 단계마다 최솟값(또는 최댓값)을 선택해서 앞(또는 뒤)으로 보내는 방식

특징: 교환 횟수가 적다.  [시간 복잡도 : O(n²)]

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

print(selection_sort([5, 3, 8, 4, 2]))

 

• 1-(3) 삽입 정렬 (Insertion Sort)

앞에서부터 차례로, 적절한 위치에 삽입하면서 정렬.

특징: 거의 정렬된 배열에 매우 빠름.  [시간 복잡도 : 평균 O(n²), 최선 O(n) ]

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:  # key보다 큰 원소들을 뒤로 민다
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort([5, 3, 8, 4, 2]))

 

2. 심화 정렬

• 2-(1) 퀵 정렬 (Quick Sort)

*피벗(Pivot)을 기준으로 작은 값과 큰 값으로 분할하여 재귀적으로 정렬 ( *피벗 : 배열을 두 그룹으로 나누는 기준 값 )

특징: 평균적으로 가장 빠른 정렬 중 하나.  [시간 복잡도 : 평균 O(n log n), 최악 O(n²) ]

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # 가운데 원소를 피벗으로
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

print(quick_sort([5, 3, 8, 4, 2]))

 

• 2-(2) 병합 정렬 (Merge Sort)

배열을 반으로 나누고 각각 정렬 후 합병(Merge)

특징: 안정 정렬(Stable Sort). 항상 O(n log n)  [시간 복잡도 : O(n log n)]

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([5, 3, 8, 4, 2]))

 

• 2-(3) 기수 정렬 (Radix Sort)

자릿수를 기준으로 차례로 정렬 (보통 큐나 안정 정렬을 이용).

특징: 비교 기반이 아님. 특정 경우 매우 빠름.  [시간 복잡도 : O(d·n) ,d=자릿수 ]

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for num in arr:
        index = num // exp
        count[index % 10] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
    return arr

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

 

3. 이진 탐색(Binary search)

 

정렬된 배열에서 중앙값과 비교하며 절반씩 범위를 줄여 탐색.

조건: 반드시 정렬된 배열이어야 함. [시간복잡도 : O(log n)]

 

 

 

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # 찾은 경우 인덱스 반환
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 없는 경우

arr = [2, 3, 4, 5, 8]
print(binary_search(arr, 4))  # 2 (인덱스)
print(binary_search(arr, 7))  # -1 (없음)

 

마치며

다양한 정렬 들이 있다는 것을 정리하고

안정성과 시간복잡도가 적은 것은 병렬 정렬인 점을 알게 되었다.