단순 정렬들: 버블, 선택, 삽입

"다들 버블 정렬을 배우고 곧이어 비웃는 법을 배워. 그런데 이 '느린' O(n²) 정렬 중 하나가 우리가 실제로 쓰는 빠른 정렬 안에 조용히 들어가 있어. 작거나 거의 정렬된 데이터에서는 단순한 쪽이 영리한 쪽을 이기거든."

세 가지 교육용 정렬

셋 다 O(n²)야. 중첩 반복문으로 쌍을 비교하니까. 대신 각자 다른 아이디어를 보여줘.

버블 정렬. 순서가 어긋난 인접한 쌍을 계속 맞바꿔서, 가장 큰 값이 한 바퀴마다 끝으로 '거품처럼' 올라가. 그림으로 그리기가 제일 쉽고 실전에서는 거의 맞는 선택이 아니야. 주된 역할은 누구나 처음 만나는 정렬이라는 거고.
선택 정렬. 한 바퀴마다 아직 정렬 안 된 구간에서 최솟값을 찾아 제자리에 놔. 보통 교환이 O(n)번 이하라 버블 정렬보다 쓰기 횟수가 적어. 다만 모든 정렬 알고리즘을 통틀어 교환 횟수가 절대적으로 최소라고 말하면 안 돼. 그리고 비교는 언제나 O(n²)야.
삽입 정렬. 정렬된 앞부분을 원소 하나씩 늘려 가면서 새 원소를 제자리에 끼워 넣어. 사람들이 카드 패를 정리하는 방식 그대로야.

삽입 정렬이 제 몫을 하는 이유

삽입 정렬의 강점은 이미 정렬됐거나 거의 정렬된 데이터에서 O(n)에 가까워지는 적응성, 그리고 구현 오버헤드가 작다는 점이야. 그래서 여러 하이브리드 정렬이 작은 부분배열을 처리할 때 삽입 정렬 계열을 써. 다만 작은 배열이면 무조건 가장 빠르다는 보장은 없어. 그 임계값은 언어 구현과 자료형, 하드웨어에 따라 달라지거든.

버블, 선택, 삽입 정렬은 모두 최악 O(n²)이야. 삽입 정렬은 거의 정렬된 입력에 적응적이고 오버헤드가 작아 하이브리드 정렬의 작은 구간 처리에 자주 쓰이지만, 실제 우위는 구현과 입력으로 확인해야 해.

단순한 쪽이 맞을 때

판단은 이래. 크고 무작위한 데이터에는 이것들을 절대 꺼내지 마. 백만 항목에 O(n²)이면 연산이 1조야. 그런데 작은 배열이거나, 대략 원소 오십 개 아래거나, 거의 정렬된 데이터거나, 코드 단순함과 낮은 메모리가 점근적 복잡도보다 중요한 상황이라면 삽입 정렬이 진짜로 이길 수 있어. 이 퀘스트에서 계속 나오는 이야기가 한 번 더 나오는 거지. '최고'인 알고리즘은 데이터와 규모에 달렸고, 단순한 도구를 싸잡아 무시하는 건 화려한 걸로 과잉 설계하는 것만큼이나 잘못이야.

피파의 고백

나는 삽입 정렬이 한물간 거라고 자신 있게 '알고' 있었어. 병합 정렬이 O(n log n)인데 왜 O(n²)를 써? 그러다 아빠가 Python의 Timsort가 짧은 구간에서 삽입 정렬을 부른다는 걸 보여줬어. 크기가 작을 때는 삽입 정렬의 낮은 오버헤드가 병합 정렬의 관리 비용을 이기니까. 나는 '점근적 복잡도가 나쁘다'를 '아무 쓸모 없다'로 착각하고 있었던 거야. 빅오가 버리는 그 상수가 정확히 삽입 정렬을 작은 규모의 맞는 도구로 만들어. 점근적 복잡도가 이야기의 다는 아니라는 걸 겸손하게 짚어준 셈이지.

Code

삽입 정렬, 간직할 가치가 있는 하나·python

# 삽입 정렬: 진짜 유용한 단순 정렬. 적응적 + 저-오버헤드.
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                  # key 를 그 슬롯에 떨궈
    return arr

print(insertion_sort([5, 2, 4, 6, 1, 3]))   # [1, 2, 3, 4, 5, 6]

# 적응적 승리: 거의-정렬된 데이터엔, 안쪽 while 이 거의 안 돌아.
nearly = [1, 2, 3, 5, 4, 6]    # 원소 하나만 어긋남
# 각 원소가 ~1 단계에 자리 찾음 -> O(n²) 아니라 O(n) 에 가까움.

# 선택 정렬 (swap 최소화) 이랑 버블 정렬 (그리기 제일 단순) 은
# 둘 다 늘 O(n^2) 비교 — 대부분 교육용, 거의 맞는 선택 아님.
# production 정렬 (Timsort) 이 작은 base case 에 *삽입* 정렬을 써.

Exercise

삽입 정렬이 왜 이미 정렬된 배열에서는 대략 O(n)이고 역순으로 정렬된 배열에서는 O(n²)인지 설명해 봐. 각 경우에 안쪽 while 반복문이 무슨 일을 하는지 따라가면 보여. 그다음 Python의 Timsort가 왜 전부를 병합 정렬하지 않고 굳이 짧은 구간에 삽입 정렬을 쓰는지도 설명해.

Hint

정렬된 데이터에서는 안쪽 while이 한 번도 안 밀어. 각 key가 이미 앞 원소보다 크거나 같으니까. 그래서 전체가 n단계쯤이야. 역순 데이터에서는 모든 key가 맨 왼쪽까지 밀려서 n²/2쯤 되고. Timsort가 짧은 구간에 삽입 정렬을 쓰는 건 그 크기에서는 낮은 상수 오버헤드가 병합 정렬의 재귀와 할당 비용을 이기기 때문이야.

세 가지 교육용 정렬

삽입 정렬이 제 몫을 하는 이유

단순한 쪽이 맞을 때

피파의 고백

Code

External links

Exercise

Progress

댓글 0