[python] 정렬 알고리즘

07 Dec 2023

python

정렬 알고리즘은 컴퓨터 과학에서 가장 기본이 되는 알고리즘 중 하나로, 데이터를 특정한 기준에 따라 순서대로 정렬하는 작업을 의미합니다. 이번 포스트에서는 파이썬에서 자주 사용되는 몇 가지 정렬 알고리즘에 대해 알아보겠습니다.

선택 정렬 (Selection Sort)

선택 정렬은 주어진 리스트 중에서 가장 작은 값을 찾아 맨 앞으로 보내는 과정을 반복하여 정렬하는 알고리즘입니다. 아래는 선택 정렬의 파이썬 코드 예시입니다.

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

삽입 정렬 (Insertion Sort)

삽입 정렬은 현재 위치에서 그 이전의 배열들을 비교하여 자신의 위치를 찾아 삽입하는 알고리즘입니다. 아래는 삽입 정렬의 파이썬 코드 예시입니다.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복(divide and conquer) 알고리즘으로, 기준(pivot)을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분할하여 정렬하는 알고리즘입니다. 아래는 퀵 정렬의 파이썬 코드 예시입니다.

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)

병합 정렬 (Merge Sort)

병합 정렬은 분할 정복 알고리즘으로, 배열을 반으로 나눈 후 정렬하여 다시 병합하는 과정을 반복하여 정렬하는 알고리즘입니다. 아래는 병합 정렬의 파이썬 코드 예시입니다.

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

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

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result

위에 소개된 알고리즘은 파이썬에서 사용되는 대표적인 정렬 알고리즘들입니다. 각각의 알고리즘은 특정한 경우에 더욱 효율적이며, 정렬해야 할 데이터의 크기와 특성에 따라 선택하여 사용할 수 있습니다.

참고 자료: