정렬 알고리즘 완벽 가이드

파이썬으로 배우는 핵심 정렬 알고리즘들을 초보자도 이해할 수 있도록 실무 예제와 함께 설명합니다. 버블 정렬부터 병합 정렬까지, 각 알고리즘의 원리와 활용법을 마스터해보세요.

---

목차

1. 파이썬에서 변수 교환하기
2. 버블 정렬(Bubble Sort)
3. 삽입 정렬(Insertion Sort)
4. 병합 정렬(Merge Sort)
5. 셸 정렬(Shell Sort)
6. 선택 정렬(Selection Sort)
7. 정렬 알고리즘 선택 기준

---

1. 파이썬에서 변수 교환하기

김개발 씨가 처음 정렬 알고리즘을 공부하던 날이었습니다. 코드를 작성하다 보니 두 변수의 값을 서로 바꿔야 하는 상황이 생겼습니다.

"어, 이거 어떻게 하지? 그냥 a = b 하면 원래 a 값이 사라지는데..."

변수 교환은 두 변수가 가진 값을 서로 맞바꾸는 기본적인 연산입니다. 마치 두 컵에 담긴 음료를 서로 바꾸려면 빈 컵이 하나 더 필요한 것처럼, 전통적인 방식에서는 임시 변수가 필요합니다.

하지만 파이썬은 이를 한 줄로 우아하게 해결합니다.

다음 코드를 살펴봅시다.

# 전통적인 방식: 임시 변수 사용
a = 5
b = 10
temp = a      # 임시 변수에 a 값 보관
a = b         # a에 b 값 대입
b = temp      # b에 원래 a 값 대입
print(f"a={a}, b={b}")  # a=10, b=5

# 파이썬 방식: 튜플 언패킹
x = 5
y = 10
x, y = y, x   # 한 줄로 교환 완료
print(f"x={x}, y={y}")  # x=10, y=5

김개발 씨는 입사 첫 주에 선배로부터 정렬 알고리즘 과제를 받았습니다. 버블 정렬을 구현하라는 것이었는데, 막상 시작하려니 가장 기본적인 부분에서 막혔습니다.

바로 두 변수의 값을 서로 바꾸는 방법이었습니다. "선배, 두 변수 값을 바꾸려면 어떻게 해야 해요?" 김개발 씨가 물었습니다.

박시니어 씨가 웃으며 대답했습니다. "좋은 질문이네요.

일단 기본 원리부터 이해해봅시다." 두 컵에 각각 콜라와 사이다가 담겨 있다고 상상해보세요. 이 두 음료를 서로 바꾸려면 어떻게 해야 할까요?

당연히 빈 컵이 하나 더 필요합니다. 먼저 콜라를 빈 컵에 옮기고, 사이다를 콜라 컵에 옮긴 다음, 빈 컵의 콜라를 사이다 컵에 옮기면 됩니다.

프로그래밍에서도 마찬가지입니다. 변수 a에 5가, 변수 b에 10이 들어있을 때, 그냥 a = b를 실행하면 a도 10이 되어버립니다.

원래 a에 있던 5는 영원히 사라지는 것입니다. 그래서 전통적인 방식에서는 **임시 변수(temp)**를 사용합니다.

temp에 a 값을 미리 저장해두고, a에 b 값을 넣은 다음, b에 temp 값을 넣으면 교환이 완료됩니다. C언어나 자바에서는 이 방식을 사용합니다.

하지만 파이썬은 다릅니다. 파이썬에는 튜플 언패킹이라는 강력한 기능이 있습니다.

a, b = b, a라고 쓰면 오른쪽의 b, a가 먼저 튜플로 묶이고, 그 다음 왼쪽의 a, b에 차례대로 할당됩니다. 이 과정을 자세히 살펴보면 이렇습니다.

먼저 b, a가 평가되어 (10, 5)라는 튜플이 만들어집니다. 그 다음 이 튜플이 언패킹되면서 첫 번째 값 10이 a에, 두 번째 값 5가 b에 할당됩니다.

임시 변수 없이 한 줄로 교환이 완료되는 것입니다. 실무에서 정렬 알고리즘을 구현할 때 이 기법은 정말 유용합니다.

버블 정렬, 선택 정렬 등에서 요소를 교환하는 코드가 자주 등장하는데, 파이썬에서는 arr[i], arr[j] = arr[j], arr[i] 한 줄로 깔끔하게 처리할 수 있습니다. 박시니어 씨의 설명을 들은 김개발 씨는 감탄했습니다.

"파이썬이 정말 편리하네요!" 이제 본격적으로 정렬 알고리즘을 구현할 준비가 되었습니다.

실전 팁

💡 - 파이썬의 튜플 언패킹은 세 개 이상의 변수도 한 번에 교환할 수 있습니다: a, b, c = c, a, b

• 리스트 요소 교환도 동일하게 적용됩니다: arr[0], arr[1] = arr[1], arr[0]

---

2. 버블 정렬(Bubble Sort)

김개발 씨가 첫 번째로 배울 정렬 알고리즘은 버블 정렬이었습니다. 박시니어 씨가 말했습니다.

"버블 정렬은 가장 직관적인 정렬 방법이에요. 마치 거품이 물 위로 떠오르는 것처럼 큰 값이 뒤로 밀려나거든요."

버블 정렬은 인접한 두 요소를 비교하여 순서가 잘못되었으면 교환하는 과정을 반복하는 알고리즘입니다. 마치 탄산음료의 거품이 아래에서 위로 떠오르듯, 큰 값들이 점점 뒤쪽으로 이동합니다.

구현이 단순해서 교육용으로 많이 사용됩니다.

다음 코드를 살펴봅시다.

def bubble_sort(arr):
    n = len(arr)
    # 전체 배열을 n-1번 순회
    for i in range(n - 1):
        swapped = False
        # 인접한 요소들을 비교하며 교환
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # 교환이 없었다면 이미 정렬 완료
        if not swapped:
            break
    return arr

# 사용 예시
numbers = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(numbers))  # [11, 12, 22, 25, 34, 64, 90]

박시니어 씨가 화이트보드에 숫자들을 적었습니다. [64, 34, 25, 12].

"자, 이 숫자들을 작은 순서대로 정렬해볼까요?" 김개발 씨는 고개를 갸웃했습니다. "그냥 눈으로 보면 12, 25, 34, 64인데...

컴퓨터는 어떻게 하나요?" "컴퓨터는 한 번에 전체를 볼 수 없어요. 대신 옆에 있는 두 숫자만 비교할 수 있죠." 버블 정렬의 원리는 정말 간단합니다.

배열의 처음부터 끝까지 이웃한 두 요소를 비교하면서, 왼쪽이 오른쪽보다 크면 서로 바꿉니다. 이 과정을 한 번 완료하면 가장 큰 값이 맨 뒤로 이동합니다.

마치 줄 서기와 비슷합니다. 키가 큰 사람이 계속 뒤로 밀려나는 것처럼요.

64가 34와 비교되어 뒤로 가고, 다시 25와 비교되어 뒤로 가고, 12와 비교되어 또 뒤로 갑니다. 한 바퀴를 돌면 64는 맨 뒤에 자리 잡습니다.

그런데 아직 앞쪽은 정렬되지 않았습니다. 그래서 같은 과정을 다시 반복합니다.

이번에는 64를 제외한 나머지에서 34가 맨 뒤로 이동합니다. 이렇게 계속 반복하면 결국 모든 요소가 정렬됩니다.

코드를 살펴보면, 바깥 반복문은 n-1번 돌고, 안쪽 반복문은 아직 정렬되지 않은 부분만 순회합니다. 핵심은 if arr[j] > arr[j + 1] 부분입니다.

왼쪽이 오른쪽보다 크면 교환하는 것이죠. 여기서 최적화 기법이 하나 있습니다.

swapped 변수를 사용하는 것입니다. 만약 한 바퀴를 돌았는데 교환이 한 번도 일어나지 않았다면, 이미 배열이 정렬된 상태입니다.

더 이상 반복할 필요가 없죠. 버블 정렬의 시간복잡도는 **O(n^2)**입니다.

n개의 요소에 대해 n번씩 비교하기 때문입니다. 1000개의 데이터라면 약 100만 번의 비교가 필요합니다.

그래서 데이터가 많으면 느려집니다. 그럼에도 버블 정렬이 가치 있는 이유가 있습니다.

첫째, 구현이 매우 간단합니다. 둘째, 추가 메모리가 필요 없습니다.

셋째, 이미 정렬된 데이터에 대해서는 O(n)으로 빠르게 동작합니다. 김개발 씨가 물었습니다.

"그럼 실무에서도 버블 정렬을 쓰나요?" 박시니어 씨가 솔직하게 대답했습니다. "거의 안 써요.

하지만 정렬 알고리즘의 기본 원리를 이해하는 데는 최고입니다. 이걸 이해하면 다른 알고리즘도 쉽게 배울 수 있어요."

실전 팁

💡 - 이미 정렬된 배열에서는 swapped 최적화로 O(n)에 완료됩니다

• 작은 데이터셋이나 거의 정렬된 데이터에는 충분히 사용할 만합니다

---

3. 삽입 정렬(Insertion Sort)

다음 날, 박시니어 씨가 카드 한 벌을 들고 왔습니다. "김개발 씨, 카드 게임 해본 적 있죠?

손에 든 카드를 정리할 때 어떻게 해요?" 김개발 씨는 평소 습관대로 대답했습니다. "새 카드를 받으면 이미 정리된 카드 사이에 끼워 넣어요."

삽입 정렬은 정렬되지 않은 요소를 이미 정렬된 부분의 적절한 위치에 삽입하는 알고리즘입니다. 마치 카드 게임에서 손패를 정리하는 방식과 똑같습니다.

구현이 간단하고, 거의 정렬된 데이터에서는 매우 효율적으로 동작합니다.

다음 코드를 살펴봅시다.

def insertion_sort(arr):
    # 두 번째 요소부터 시작
    for i in range(1, len(arr)):
        key = arr[i]  # 삽입할 요소
        j = i - 1
        # key보다 큰 요소들을 오른쪽으로 이동
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        # 적절한 위치에 key 삽입
        arr[j + 1] = key
    return arr

# 사용 예시
numbers = [12, 11, 13, 5, 6]
print(insertion_sort(numbers))  # [5, 6, 11, 12, 13]

박시니어 씨가 카드 7장을 섞어서 테이블에 놓았습니다. "자, 이 카드들을 순서대로 정리해볼까요?" 김개발 씨가 첫 번째 카드를 집었습니다.

5였습니다. 손에 카드가 하나뿐이니 이건 이미 정렬된 상태입니다.

두 번째 카드는 2였습니다. 5보다 작으니까 5 앞에 놓았습니다.

세 번째 카드 8은 5 뒤에 놓았습니다. 네 번째 카드 3은 2와 5 사이에 끼워 넣었습니다.

"바로 그거예요! 지금 한 게 삽입 정렬입니다." 삽입 정렬의 핵심 아이디어는 정렬된 영역을 점점 확장해 나가는 것입니다.

처음에는 첫 번째 요소만 정렬된 상태로 봅니다. 그 다음 두 번째 요소를 정렬된 부분의 적절한 위치에 끼워 넣습니다.

이제 두 개가 정렬되었습니다. 세 번째 요소도 마찬가지로 처리합니다.

코드를 보면, key는 현재 삽입하려는 요소입니다. while 반복문에서는 key보다 큰 요소들을 하나씩 오른쪽으로 밀어냅니다.

빈자리가 생기면 거기에 key를 삽입합니다. 예를 들어 [12, 11, 13, 5, 6]을 정렬한다고 해봅시다.

처음에 12는 혼자이니 정렬된 상태입니다. 11을 삽입할 차례가 되면, 11은 12보다 작으므로 12를 오른쪽으로 밀고 11을 앞에 넣습니다.

결과는 [11, 12]입니다. 13은 12보다 크니까 그 뒤에 그대로 둡니다.

[11, 12, 13]. 5는 13, 12, 11 모두보다 작으므로 세 요소를 다 밀고 맨 앞에 삽입됩니다.

[5, 11, 12, 13]. 삽입 정렬도 최악의 경우 **O(n^2)**입니다.

하지만 거의 정렬된 데이터에서는 탁월한 성능을 보입니다. 이미 정렬되어 있다면 while 반복문이 거의 실행되지 않아 O(n)에 가깝게 동작합니다.

실무에서 삽입 정렬이 쓰이는 경우가 있습니다. 바로 작은 배열을 정렬할 때입니다.

파이썬의 내장 정렬 함수인 sorted()나 list.sort()도 내부적으로 작은 부분 배열에는 삽입 정렬을 사용합니다. 또한 실시간으로 데이터가 들어오는 상황에서도 유용합니다.

새 데이터가 하나씩 들어올 때마다 정렬된 상태를 유지해야 한다면, 삽입 정렬의 아이디어가 딱입니다. 김개발 씨가 고개를 끄덕였습니다.

"카드 정리하는 방식이랑 똑같네요. 이해하기 쉬워요!"

실전 팁

💡 - 거의 정렬된 데이터에서는 버블 정렬보다 훨씬 빠릅니다

• 온라인 알고리즘으로, 데이터를 받는 즉시 정렬할 수 있습니다

---

4. 병합 정렬(Merge Sort)

며칠 후, 김개발 씨에게 10만 건의 데이터를 정렬하는 업무가 떨어졌습니다. 버블 정렬로 시도했더니 너무 느렸습니다.

박시니어 씨가 말했습니다. "이제 진짜 효율적인 알고리즘을 배워야 할 때가 됐네요.

분할 정복이라는 전략을 아세요?"

병합 정렬은 배열을 반으로 계속 나누고, 나눈 부분을 정렬하면서 합치는 분할 정복 알고리즘입니다. 마치 여러 명이 시험지를 나눠서 채점한 후 합치는 것과 같습니다.

항상 **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

박시니어 씨가 종이 8장을 테이블에 펼쳐놓았습니다. 각각 [38, 27, 43, 3, 9, 82, 10, 45]가 적혀 있었습니다.

"자, 이걸 여러 명이 나눠서 정렬한다고 생각해봐요." "먼저 반으로 나눕니다." [38, 27, 43, 3]과 [9, 82, 10, 45]. "또 반으로 나눕니다." [38, 27], [43, 3], [9, 82], [10, 45].

"한 번 더요." 이제 각각 하나씩입니다. "숫자가 하나뿐이면 이미 정렬된 거죠.

이제 합치면서 정렬합니다." 병합 정렬의 핵심 전략은 **분할 정복(Divide and Conquer)**입니다. 큰 문제를 작은 문제로 쪼개고, 작은 문제를 해결한 후, 그 결과를 합쳐서 큰 문제를 해결합니다.

분할 단계에서는 배열을 계속 반으로 나눕니다. 요소가 하나가 될 때까지 나누면, 그건 이미 정렬된 것입니다.

하나짜리 배열은 그 자체로 정렬되어 있으니까요. 병합 단계가 진짜 마법이 일어나는 곳입니다.

정렬된 두 배열을 합쳐서 하나의 정렬된 배열을 만듭니다. 두 배열의 맨 앞 요소를 비교해서 작은 것을 먼저 결과에 넣습니다.

이 과정을 반복하면 두 배열이 하나로 합쳐집니다. 예를 들어 [27, 38]과 [3, 43]을 합친다고 해봅시다.

27과 3을 비교하면 3이 작으니까 3을 먼저 넣습니다. 다음으로 27과 43을 비교하면 27이 작습니다.

그 다음 38과 43을 비교하면 38이 작습니다. 마지막으로 43을 넣으면 [3, 27, 38, 43]이 완성됩니다.

코드에서 merge_sort 함수는 재귀적으로 자신을 호출합니다. 배열이 하나 이하가 되면 그대로 반환하고, 그렇지 않으면 반으로 나눠서 각각 정렬한 후 merge 함수로 합칩니다.

병합 정렬의 시간복잡도는 항상 **O(n log n)**입니다. 분할하는 데 log n 단계가 필요하고, 각 단계에서 n개의 요소를 병합합니다.

데이터가 어떤 상태든 상관없이 일정한 성능을 보장합니다. 단점도 있습니다.

추가 메모리가 필요합니다. 병합할 때 임시 배열을 만들어야 하기 때문입니다.

공간복잡도가 O(n)입니다. 김개발 씨가 10만 건 데이터에 병합 정렬을 적용했습니다.

버블 정렬로 몇 분 걸리던 것이 순식간에 끝났습니다. "와, 이게 알고리즘의 힘이군요!"

실전 팁

💡 - 대용량 데이터에 적합하며, 외부 정렬(파일 정렬)에도 사용됩니다

• 안정 정렬이므로 같은 값의 상대적 순서가 유지됩니다

---

5. 셸 정렬(Shell Sort)

"삽입 정렬이 좋긴 한데, 데이터가 완전히 뒤섞여 있으면 너무 느려요." 김개발 씨의 불만에 박시니어 씨가 대답했습니다. "그래서 도널드 셸이라는 분이 기발한 아이디어를 냈어요.

멀리 떨어진 요소부터 먼저 정렬하면 어떨까? 하고요."

셸 정렬은 삽입 정렬의 개선 버전으로, 일정 간격(gap)만큼 떨어진 요소들끼리 먼저 정렬합니다. 간격을 점점 줄여가며 정렬하다가 마지막에 간격이 1이 되면 일반 삽입 정렬이 됩니다.

이렇게 하면 요소들이 제자리에서 멀리 떨어져 있어도 빠르게 이동할 수 있습니다.

다음 코드를 살펴봅시다.

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 초기 간격

    while gap > 0:
        # gap 간격으로 삽입 정렬 수행
        for i in range(gap, n):
            temp = arr[i]
            j = i
            # gap 간격의 요소들과 비교하며 삽입
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2  # 간격을 절반으로 줄임

    return arr

# 사용 예시
numbers = [12, 34, 54, 2, 3]
print(shell_sort(numbers))  # [2, 3, 12, 34, 54]

박시니어 씨가 책장을 가리켰습니다. "저 책들이 완전히 뒤죽박죽이라고 해봐요.

삽입 정렬처럼 하나씩 옮기면 한참 걸리겠죠?" 김개발 씨가 고개를 끄덕였습니다. 맨 끝에 있는 책을 맨 앞으로 옮기려면 중간의 모든 책을 밀어야 합니다.

"그런데 만약 멀리 떨어진 책들끼리 먼저 대충 순서를 맞춰놓으면 어떨까요? 나중에 세밀하게 정리할 때 훨씬 수월하지 않을까요?" 이것이 바로 셸 정렬의 핵심 아이디어입니다.

1959년 도널드 셸(Donald Shell)이 발명한 이 알고리즘은 삽입 정렬의 약점을 보완합니다. 삽입 정렬의 문제는 요소가 한 칸씩만 이동한다는 것입니다.

만약 가장 작은 요소가 배열 맨 뒤에 있다면, n-1번이나 이동해야 맨 앞에 도달합니다. 매우 비효율적입니다.

셸 정렬은 처음에 큰 **간격(gap)**을 사용합니다. 예를 들어 8개의 요소가 있다면 간격 4로 시작합니다.

인덱스 0, 4끼리, 1, 5끼리, 2, 6끼리, 3, 7끼리 정렬합니다. 멀리 떨어진 요소들이 한 번에 제자리 근처로 이동합니다.

그 다음 간격을 2로 줄입니다. 인덱스 0, 2, 4, 6끼리, 1, 3, 5, 7끼리 정렬합니다.

이제 요소들이 더 제자리에 가까워집니다. 마지막으로 간격이 1이 되면 일반 삽입 정렬과 같아집니다.

하지만 이 시점에서 배열은 이미 거의 정렬된 상태입니다. 삽입 정렬은 거의 정렬된 배열에서 매우 빠르게 동작하므로, 최종 정렬이 순식간에 끝납니다.

코드를 보면, 바깥 while 반복문이 gap을 절반씩 줄여가고, 안쪽에서는 gap 간격의 삽입 정렬을 수행합니다. 구조는 삽입 정렬과 비슷하지만, j -= 1 대신 j -= gap을 사용합니다.

셸 정렬의 시간복잡도는 gap 수열에 따라 달라집니다. n/2, n/4, ...

1을 사용하면 평균 O(n^1.5) 정도입니다. 더 좋은 gap 수열을 사용하면 성능이 향상됩니다.

추가 메모리가 필요 없는 제자리 정렬이라는 장점이 있습니다. 병합 정렬처럼 별도 배열을 만들 필요가 없습니다.

김개발 씨가 감탄했습니다. "작은 아이디어 하나로 성능이 확 좋아지네요!"

실전 팁

💡 - gap 수열을 잘 선택하면 성능이 크게 향상됩니다 (Hibbard, Sedgewick 수열 등)

• 제자리 정렬이므로 메모리 효율이 좋습니다

---

6. 선택 정렬(Selection Sort)

"정렬 알고리즘 중에 가장 직관적인 게 뭐예요?" 신입 개발자가 물었습니다. 박시니어 씨가 대답했습니다.

"아마 선택 정렬일 거예요. 가장 작은 걸 찾아서 앞으로 보내고, 그 다음 작은 걸 찾아서 그 다음에 놓고...

이런 식이거든요."

선택 정렬은 배열에서 가장 작은 요소를 찾아 맨 앞으로 보내고, 그 다음 작은 요소를 그 다음 위치로 보내는 과정을 반복합니다. 마치 시험 점수를 정리할 때 가장 높은 점수부터 뽑아서 순서대로 나열하는 것과 같습니다.

교환 횟수가 최소화되는 장점이 있습니다.

다음 코드를 살펴봅시다.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        # 현재 위치를 최솟값 위치로 가정
        min_idx = i
        # 나머지 요소들 중 최솟값 찾기
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # 최솟값을 현재 위치로 교환
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 사용 예시
numbers = [64, 25, 12, 22, 11]
print(selection_sort(numbers))  # [11, 12, 22, 25, 64]

학교 운동회 날입니다. 선생님이 학생들을 키 순서대로 세우려고 합니다.

어떻게 하면 좋을까요? 가장 직관적인 방법은 이것입니다.

먼저 전체를 쭉 둘러보고 가장 키가 작은 학생을 찾습니다. 그 학생을 맨 앞으로 보냅니다.

다음으로 나머지 학생들 중 가장 키가 작은 학생을 찾아 두 번째에 세웁니다. 이 과정을 반복하면 모든 학생이 키 순서대로 줄을 섭니다.

이것이 선택 정렬의 원리입니다. 매우 직관적이고 이해하기 쉽습니다.

코드를 살펴보면, 바깥 반복문의 i는 현재 채워야 할 위치입니다. 안쪽 반복문에서는 i 이후의 요소들 중 가장 작은 값의 위치(min_idx)를 찾습니다.

찾았으면 arr[i]와 arr[min_idx]를 교환합니다. 구체적인 예를 들어봅시다.

[64, 25, 12, 22, 11]을 정렬한다고 합시다. 첫 번째 라운드에서 전체를 살펴보면 11이 가장 작습니다.

64와 11을 교환하면 [11, 25, 12, 22, 64]가 됩니다. 두 번째 라운드에서는 인덱스 1부터 살펴봅니다.

12가 가장 작습니다. 25와 12를 교환하면 [11, 12, 25, 22, 64]가 됩니다.

이런 식으로 계속하면 최종적으로 [11, 12, 22, 25, 64]가 됩니다. 선택 정렬의 시간복잡도는 **O(n^2)**입니다.

비교 횟수는 n(n-1)/2로 항상 같습니다. 데이터가 이미 정렬되어 있어도 마찬가지입니다.

이 점이 버블 정렬이나 삽입 정렬과 다릅니다. 하지만 교환 횟수는 최대 n-1번입니다.

각 라운드에서 딱 한 번만 교환하기 때문입니다. 교환 비용이 비싼 상황에서는 이 점이 장점이 됩니다.

또한 제자리 정렬이므로 추가 메모리가 필요 없습니다. 구현도 매우 간단합니다.

그러나 선택 정렬은 불안정 정렬입니다. 같은 값을 가진 요소들의 상대적 순서가 바뀔 수 있습니다.

예를 들어 [(3, 'a'), (2, 'b'), (3, 'c')]를 정렬하면 (3, 'a')와 (3, 'c')의 순서가 바뀔 수 있습니다. 김개발 씨가 물었습니다.

"그럼 선택 정렬은 언제 쓰나요?" 박시니어 씨가 대답했습니다. "실무에서는 잘 안 쓰지만, 교환 비용이 비싼 특수한 상황이나 교육용으로 사용됩니다."

실전 팁

💡 - 교환 횟수가 중요한 상황에서 유리합니다

• 불안정 정렬이므로 안정성이 필요하면 다른 알고리즘을 선택하세요

---

7. 정렬 알고리즘 선택 기준

프로젝트 마감을 앞두고 김개발 씨는 고민에 빠졌습니다. "버블, 삽입, 선택, 셸, 병합...

정렬 알고리즘이 이렇게 많은데, 실제로 어떤 걸 써야 하죠?" 박시니어 씨가 웃으며 대답했습니다. "상황에 따라 다르죠.

정답은 없어요."

정렬 알고리즘 선택은 데이터 크기, 데이터 상태, 메모리 제약, 안정성 요구 등 여러 요소를 고려해야 합니다. 대부분의 경우 언어 내장 정렬을 사용하면 되지만, 특수한 상황에서는 적합한 알고리즘을 직접 선택해야 합니다.

다음 코드를 살펴봅시다.

# 파이썬 내장 정렬 (Timsort - 병합+삽입 하이브리드)
numbers = [64, 34, 25, 12, 22]
sorted_numbers = sorted(numbers)  # 새 리스트 반환
numbers.sort()  # 제자리 정렬

# 상황별 선택 가이드
def choose_sort(data_size, nearly_sorted, memory_limited):
    if data_size < 50:
        return "삽입 정렬"
    elif nearly_sorted:
        return "삽입 정렬 또는 Timsort"
    elif memory_limited:
        return "셸 정렬 또는 퀵 정렬"
    else:
        return "병합 정렬 또는 Timsort"

# 실무에서는 대부분 내장 정렬 사용
import random
data = [random.randint(1, 1000) for _ in range(10000)]
data.sort()  # Timsort, O(n log n) 보장

김개발 씨가 지난 한 주 동안 배운 알고리즘들을 정리해봤습니다. 버블 정렬, 삽입 정렬, 선택 정렬, 셸 정렬, 병합 정렬.

각각 장단점이 있었습니다. 박시니어 씨가 표를 그려주었습니다.

"자, 상황별로 어떤 알고리즘이 좋은지 정리해봅시다." 첫 번째 기준은 데이터 크기입니다. 데이터가 50개 미만으로 작다면 단순한 알고리즘도 충분합니다.

삽입 정렬이 오버헤드가 적어서 오히려 빠를 수 있습니다. 반면 데이터가 수천, 수만 개 이상이라면 O(n log n) 알고리즘이 필수입니다.

두 번째 기준은 데이터 상태입니다. 이미 거의 정렬된 데이터라면 삽입 정렬이 최강입니다.

O(n)에 가까운 성능을 보입니다. 반면 완전히 무작위한 데이터라면 병합 정렬이나 퀵 정렬이 좋습니다.

세 번째 기준은 메모리 제약입니다. 추가 메모리를 쓸 수 없는 환경이라면 제자리 정렬인 셸 정렬, 퀵 정렬, 힙 정렬을 고려해야 합니다.

메모리가 충분하다면 병합 정렬의 안정성이 유리합니다. 네 번째 기준은 안정성입니다.

같은 값의 상대적 순서를 유지해야 한다면 안정 정렬을 선택해야 합니다. 삽입 정렬, 병합 정렬이 안정 정렬입니다.

선택 정렬, 퀵 정렬은 불안정 정렬입니다. 그렇다면 실무에서는 어떻게 할까요?

정답은 간단합니다. 대부분의 경우 언어 내장 정렬을 사용하면 됩니다. 파이썬의 sorted()와 list.sort()는 Timsort라는 하이브리드 알고리즘을 사용합니다.

병합 정렬과 삽입 정렬의 장점을 결합한 것으로, 거의 모든 상황에서 최적의 성능을 냅니다. Timsort는 실제 데이터에서 자주 나타나는 패턴을 잘 처리합니다.

이미 정렬된 부분을 찾아서 활용하고, 작은 배열에는 삽입 정렬을 적용합니다. 최악의 경우에도 O(n log n)을 보장하면서, 거의 정렬된 데이터에서는 O(n)에 가깝게 동작합니다.

김개발 씨가 마지막 질문을 했습니다. "그럼 정렬 알고리즘을 배운 의미가 없는 거 아니에요?" 박시니어 씨가 고개를 저었습니다.

"아니요. 내부 원리를 이해하면 왜 그 알고리즘이 그런 성능을 내는지 알 수 있어요.

특수한 상황에서 최적의 선택을 할 수 있고, 면접에서도 자주 물어봅니다. 무엇보다 알고리즘적 사고력을 키우는 데 정렬만큼 좋은 주제가 없어요." 김개발 씨는 고개를 끄덕였습니다.

정렬 알고리즘을 공부하면서 분할 정복, 최적화, 트레이드오프 등 중요한 개념들을 자연스럽게 배웠습니다. 이제 더 복잡한 알고리즘도 자신 있게 도전할 수 있을 것 같았습니다.

실전 팁

💡 - 실무에서는 99% 이상 언어 내장 정렬을 사용합니다

• 알고리즘 원리를 이해하면 특수 상황에서 올바른 선택을 할 수 있습니다
• 정렬 알고리즘은 분할 정복, 최적화 등 핵심 개념을 배우는 좋은 교재입니다

---

이상으로 학습을 마칩니다. 위 내용을 직접 코드로 작성해보면서 익혀보세요!