정렬 알고리즘 (버블, 선택, 삽입)

정렬이 왜 중요할까?

정렬(Sorting)은 거의 모든 알고르짐 문제에서 기본으로 사용됩니다.

데이터를 정리하면 검색, 탐색, 그룹핑 등이 쉬워집니다.

---

비교 정렬 알고리즘 (3형제)

버블 정렬 (Bubble Sort)

• 인접한 요소를 비교해서 더 큰 값을 오른쪽으로 '계속 밀어내는' 방식
  가장 큰 수가 '거품처림' 끝으로 떠오른다.

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

 

✅ 시간복잡도: O(n²)
✅ 안정 정렬 (같은 값의 순서 유지됨)

---

선택 정렬 (Selection Sort)

• 가장 작은 값을 선택해서 맨 앞으로 보내는 방식
  한 바퀴 돌 때 마다 가장 작은 애가 제저리를 찾는다.

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

 

 

✅ 시간복잡도: O(n²)
❌ 안정 정렬 아님

---

삽입 정렬 (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

 

 

✅ 평균: O(n²), 최선: O(n)
✅ 안정 정렬

---

알고리즘	최선	평균	최악	안정 정렬
버블 정렬	O(n)	O(n²)	O(n²)	O
선택 정렬	O(n²)	O(n²)	O(n²)	X
삽입 정렬	O(n)	O(n²)	O(n²)	O

입력 데이터가 이미 정렬된 경우, 삽입 정렬이 가장 유리합니다.

---

요약 정리

알고리즘	특징 요약
버블 정렬	옆과 비교해 큰 값을 뒤로 밀어냄
선택 정렬	가장 작은 값을 골라 앞으로 보냄
삽입 정렬	현재 값을 앞에서 삽입할 위치를 찾아 끼워 넣