정렬 알고리즘 3형제 비교하기 🧼🧢🖊️: 버블 vs 선택 vs 삽입

안녕하세요 logro 입니다 :)

오늘의 하루 한 개념은 정렬 알고리즘의 대표 3형제,
버블 정렬, 선택 정렬, 삽입 정렬을 비교하면서 이해해보는 시간이에요 💡

이 세 가지는 모두 간단하고 직관적이라서, 알고리즘 입문자라면 꼭 한 번은 만나게 됩니다.
그럼 하나씩 알아볼까요? 😊

---

🧼 버블 정렬 (Bubble Sort)

"옆에 있는 값이랑 비교해서 큰 걸 뒤로 보내기!"

버블 정렬은 인접한 두 값을 비교해서 큰 값을 점점 뒤로 보내는 방식이에요.
이걸 반복하면 가장 큰 값이 맨 뒤로 ‘둥둥’ 떠오르듯 정렬돼요.

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

📌 특징 요약

• 비교 횟수 많음 😥
• 코드 구조는 단순!
• 시간 복잡도: O(n²)

알고리즘의 속도를 말해주는 마법의 도구, 시간 복잡도란?

알고리즘의 속도를 말해주는 마법의 도구, 시간 복잡도란?

 

---

🧢 선택 정렬 (Selection Sort)

"가장 작은 값을 찾아서 앞으로 보내기!"

리스트에서 가장 작은 값을 찾아 첫 번째 자리에 놓고,
그다음 작은 값을 두 번째 자리에 놓는 식으로 정렬해요.

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]

📌 특징 요약

• 교환 횟수는 적은 편
• 무조건 끝까지 찾아야 해서 비효율적
• 시간 복잡도: 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

📌 특징 요약

• 이미 정렬된 데이터에 강함 💪
• 비교적 효율적인 방식
• 시간 복잡도: O(n²) (하지만 거의 정렬된 경우는 O(n))

---

🧠 한눈에 정리해보자!

정렬 방식	아이디어	시간 복잡도	특징
버블 정렬	인접 비교	O(n²)	구현은 쉬우나 비효율적
선택 정렬	최소값 선택	O(n²)	교환은 적지만 느림
삽입 정렬	앞에 끼워넣기	O(n²) → O(n)	거의 정렬된 데이터에 유리

---

🎯 마무리

버블, 선택, 삽입 정렬은 단순한 만큼 알고리즘의 기본 구조와 흐름을 익히기에 정말 좋아요.
실제 대규모 데이터에는 잘 쓰이지 않지만,
이 3형제를 이해하면 이후에 배울 퀵 정렬, 병합 정렬도 훨씬 쉽게 다가올 거예요! 😎
감사합니다! 🙌