코딩 테스트 대비! 파이썬으로 정렬 알고리즘 구현하기

파이썬으로 정렬 알고리즘 구현하기


문제 설명

다음 정렬 알고리즘들을 파이썬으로 구현하라.
- 버블 정렬(Bubble Sort)
- 선택 정렬(Selection Sort)
- 삽입 정렬(Insertion Sort)


예시 입출력

입력 배열: [3, 1, 4, 2, 5]

버블 정렬 결과: [1, 2, 3, 4, 5]
선택 정렬 결과: [1, 2, 3, 4, 5]
삽입 정렬 결과: [1, 2, 3, 4, 5]

솔루션 코드

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

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

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        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

# 테스트 케이스
input_arr = [3, 1, 4, 2, 5]
print("버블 정렬 결과:", bubble_sort(input_arr.copy()))
print("선택 정렬 결과:", selection_sort(input_arr.copy()))
print("삽입 정렬 결과:", insertion_sort(input_arr.copy()))

코드 설명

이 포스팅에서는 버블 정렬, 선택 정렬, 삽입 정렬 세 가지 기본 정렬 알고리즘을 파이썬으로 구현했습니다. 정렬 알고리즘은 코딩 테스트에서 자주 출제되는 주제이므로 반드시 학습해야 합니다.

버블 정렬은 인접한 두 원소를 비교하여 교환을 반복하는 방식입니다. 구현이 단순하지만 시간 복잡도가 O(n^2)으로 비효율적입니다.

선택 정렬은 주어진 배열에서 최소값을 찾아 앞으로 보내는 방식입니다. 버블 정렬보다 효율적이지만 여전히 O(n^2)의 시간 복잡도를 가집니다.

삽입 정렬은 정렬된 부분 배열과 정렬되지 않은 부분 배열로 나누어 진행합니다. 정렬된 배열에 하나씩 원소를 삽입하는 방식으로 동작합니다. 평균 시간 복잡도는 O(n^2)이지만 입력 데이터가 이미 정렬되어 있다면 O(n)의 시간 복잡도를 가집니다.

이처럼 각 정렬 알고리즘은 장단점이 있으므로, 문제 상황에 맞게 적절한 알고리즘을 선택할 수 있어야 합니다. 또한 실제로 구현해보는 과정을 통해 알고리즘의 동작 원리를 깊이 이해할 수 있습니다. 정렬 알고리즘을 학습하면 코딩 테스트뿐 아니라 실무에서도 도움이 됩니다.