정렬 알고리즘 - 삽입정렬, 선택정렬, 퀵 정렬 with Python

정렬 알고리즘은 자료 구조에서 가장 기본적인 알고리즘 중 하나입니다. 정렬 알고리즘은 요소들을 특정한 기준에 따라 정렬하는 방법을 말합니다. 예를 들어, 숫자 배열을 오름차순이나 내림차순으로 정렬하는 것입니다. 이번 글에서는 구현 가능한 소팅 알고리즘인 선택 정렬, 삽입 정렬, 퀵 정렬에 대해 설명하고, 각 알고리즘을 Python으로 구현해 보겠습니다.

선택 정렬

선택 정렬은 가장 간단한 정렬 알고리즘 중 하나입니다. 선택 정렬은 주어진 리스트에서 최솟값을 찾아 맨 앞으로 보내고, 그 다음으로 작은 값을 찾아서 두 번째 자리로 보내는 과정을 반복합니다. 이를 리스트의 크기만큼 반복하는 것입니다.

선택 정렬의 시간 복잡도는 O(n^2)으로 매우 느린 편이지만, 구현이 간단하고 메모리를 적게 사용한다는 장점이 있습니다.

Python 코드 구현

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

삽입 정렬

삽입 정렬은 선택 정렬과 마찬가지로 간단한 정렬 알고리즘 중 하나입니다. 삽입 정렬은 리스트를 순회하며, 각 요소를 적절한 위치에 삽입합니다. 이를 리스트의 크기만큼 반복하는 것입니다.

삽입 정렬의 시간 복잡도는 선택 정렬과 같은 O(n^2)이지만, 일반적으로 선택 정렬보다 빠릅니다.

Python 코드 구현

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

퀵 정렬

퀵 정렬은 가장 빠른 정렬 알고리즘 중 하나입니다. 퀵 정렬은 리스트를 분할하고, 각 분할된 리스트를 정렬하는 과정을 반복합니다. 이를 분할 정복 알고리즘이라고 부릅니다.

퀵 정렬의 시간 복잡도는 평균적으로 O(n log n)이지만, 최악의 경우 O(n^2)까지 증가할 수 있습니다.

Python 코드 구현

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left, equal, right = [], [], []
    for elem in arr:
        if elem < pivot:
            left.append(elem)
        elif elem == pivot:
            equal.append(elem)
        else:
            right.append(elem)
    return quick_sort(left) + equal + quick_sort(right)

 

 

선택 정렬과 삽입 정렬은 간단한 구현과 메모리 사용이 적다는 장점이 있지만, 시간 복잡도가 높습니다. 반면, 퀵 정렬은 빠른 속도와 평균적으로 좋은 시간 복잡도를 가지지만, 최악의 경우 O(n^2)까지 증가할 수 있습니다. 따라서, 알고리즘을 선택할 때는 특정 상황에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.