Why learn sorting algorithms?

They are fundamental algorithms and great for practicing time complexity analysis. In practice, use built-in functions.

Which sorting is fastest?

Quick/merge/heap sort are fastest at O(n log n). Basic sorts are O(n²).

What is stable sorting?

Sorting that preserves relative order of equal elements. Bubble, insertion, merge are stable.

[2026] Sorting Algorithms | Bubble, Selection, Insertion Sort Complete Guide

2026년 3월 28일 · 20분 읽기 · 수정 2026년 3월 28일 Beginner Tutorial

이 글의 핵심

Master basic sorting algorithms: bubble, selection, and insertion sort. Learn principles, implementations, time complexity analysis with detailed examples.

Introduction

”Sorting is the Beginning of Algorithms”

Sorting is the most fundamental algorithm. It’s the best topic for learning time complexity analysis and optimization.

1. Bubble Sort

Algorithm

Compare adjacent elements and move larger values to the right: 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

[5, 2, 4, 1, 3]
 ↓ Compare & swap
[2, 5, 4, 1, 3]
    ↓
[2, 4, 5, 1, 3]
       ↓
[2, 4, 1, 5, 3]
          ↓
[2, 4, 1, 3, 5]  ← 5 in place

Python Implementation

Compare adjacent cells and swap if left is larger. Each pass “bubbles up” the largest value in the unsorted range to the right end. 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

def bubble_sort(arr):
    n = len(arr)
    
    for i in range(n):
        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
        
        # Already sorted if no swaps
        if not swapped:
            break
    
    return arr
# Test
arr = [5, 2, 4, 1, 3]
print(bubble_sort(arr))  # [1, 2, 3, 4, 5]

Time Complexity

Best: O(n) (already sorted)
Average: O(n²)
Worst: O(n²)
Space: O(1)
Stable: Yes Step-by-Step Trace: 다음은 text를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

[5, 2, 4, 1, 3]
Pass 1:
[2, 5, 4, 1, 3]
[2, 4, 5, 1, 3]
[2, 4, 1, 5, 3]
[2, 4, 1, 3, 5] ← 5 in place
Pass 2:
[2, 4, 1, 3, 5]
[2, 1, 4, 3, 5]
[2, 1, 3, 4, 5] ← 4 in place
Pass 3:
[1, 2, 3, 4, 5] ← 3 in place
Pass 4: No swaps → Done

2. Selection Sort

Algorithm

Find minimum and swap with front: 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

[5, 2, 4, 1, 3]
 ↓ Find min: 1
[1, 2, 4, 5, 3]  ← 1 in place
    ↓ Find min: 2
[1, 2, 4, 5, 3]  ← 2 in place
       ↓ Find min: 3
[1, 2, 3, 5, 4]  ← 3 in place
          ↓
[1, 2, 3, 4, 5]  ← Done

Python Implementation

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        min_idx = i
        
        # Find minimum after i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        
        # Swap
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    
    return arr
# Test
arr = [5, 2, 4, 1, 3]
print(selection_sort(arr))  # [1, 2, 3, 4, 5]

Time Complexity

Best: O(n²)
Average: O(n²)
Worst: O(n²)
Space: O(1)
Stable: No Why Not Stable? 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

[5a, 5b, 2]
Step 1: Find min (2), swap with 5a
[2, 5b, 5a]  ← 5b now before 5a (order changed!)
Selection sort can change relative order of equal elements

3. Insertion Sort

Algorithm

Insert into sorted portion: 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

[5, 2, 4, 1, 3]
[5] 2 4 1 3  ← 5 is sorted
[2, 5] 4 1 3  ← Insert 2
[2, 4, 5] 1 3  ← Insert 4
[1, 2, 4, 5] 3  ← Insert 1
[1, 2, 3, 4, 5]  ← Insert 3

Python Implementation

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # Move elements larger than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key
    
    return arr
# Test
arr = [5, 2, 4, 1, 3]
print(insertion_sort(arr))  # [1, 2, 3, 4, 5]

Time Complexity

Best: O(n) (already sorted)
Average: O(n²)
Worst: O(n²)
Space: O(1)
Stable: Yes Step-by-Step Trace: 다음은 text를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

[5, 2, 4, 1, 3]
i=1, key=2:
  [5, 5, 4, 1, 3]  (shift 5)
  [2, 5, 4, 1, 3]  (insert 2)
i=2, key=4:
  [2, 5, 5, 1, 3]  (shift 5)
  [2, 4, 5, 1, 3]  (insert 4)
i=3, key=1:
  [2, 4, 5, 5, 3]  (shift 5)
  [2, 4, 4, 5, 3]  (shift 4)
  [2, 2, 4, 5, 3]  (shift 2)
  [1, 2, 4, 5, 3]  (insert 1)
i=4, key=3:
  [1, 2, 4, 5, 5]  (shift 5)
  [1, 2, 4, 4, 5]  (shift 4)
  [1, 2, 3, 4, 5]  (insert 3)

4. Sorting Comparison

Algorithm	Best	Average	Worst	Space	Stable
Bubble	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)	No

When to Use Each

다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# Bubble Sort
# - Educational purposes
# - Nearly sorted arrays (with early termination)
# Selection Sort
# - Minimize number of swaps
# - Small arrays
# Insertion Sort
# - Nearly sorted arrays (best case O(n))
# - Small arrays
# - Online sorting (elements arrive one at a time)
# Quick/Merge/Heap Sort
# - Large arrays
# - Need O(n log n) performance

5. Python Built-in Sorting

sorted() vs sort()

다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# sorted(): Returns new list
arr = [5, 2, 4, 1, 3]
sorted_arr = sorted(arr)
print(arr)  # [5, 2, 4, 1, 3] (original preserved)
print(sorted_arr)  # [1, 2, 3, 4, 5]
# sort(): In-place sorting
arr = [5, 2, 4, 1, 3]
arr.sort()
print(arr)  # [1, 2, 3, 4, 5] (original modified)
# Reverse
arr.sort(reverse=True)
print(arr)  # [5, 4, 3, 2, 1]
# Custom key
students = [('Alice', 85), ('Bob', 90), ('Charlie', 80)]
students.sort(key=lambda x: x[1], reverse=True)
print(students)  # [('Bob', 90), ('Alice', 85), ('Charlie', 80)]

Timsort (Python’s Default)

아래 코드는 python를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

# Python uses Timsort (hybrid of merge + insertion)
# - Time: O(n log n) worst case
# - Space: O(n)
# - Stable: Yes
# - Optimized for real-world data
arr = [5, 2, 4, 1, 3]
arr.sort()  # Uses Timsort

Practical Tips

Coding Interview Tips

아래 코드는 python를 사용한 구현 예제입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ✅ Use built-in functions most of the time
arr.sort()  # Timsort (O(n log n))
# ✅ When stable sort needed
# Python sort() is stable
# ✅ Partial sorting
import heapq
arr = [5, 2, 4, 1, 3]
smallest_3 = heapq.nsmallest(3, arr)
print(smallest_3)  # [1, 2, 3]

Advanced Example: Stable Sort with Keys

When same scores must preserve original input order, need stable sort like insertion, merge, or Timsort. Below is a pattern for sorting by (score descending, original index ascending). 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

from dataclasses import dataclass
@dataclass
class Row:
    name: str
    score: int
rows = [
    Row("A", 90),
    Row("B", 90),
    Row("C", 80),
]
# Python's sort is stable, so use index as secondary key
indexed = list(enumerate(rows))
indexed.sort(key=lambda t: (-t[1].score, t[0]))
ordered = [r for _, r in indexed]
print([r.name for r in ordered])  # ['A', 'B', 'C']

Common Mistakes

아래 코드는 python를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

# ❌ Wrong: Comparing floats directly
# May cause unstable ordering
# ❌ Wrong: Using sorted() when in-place needed
# Doubles memory usage
# ❌ Wrong: Implementing O(n²) sort in contests
# Causes timeout (only when problem allows)

Cautions

Partial sorting (top-k) may be more efficient with heap or heapq.nsmallest.
For nearly sorted arrays, insertion sort or Timsort approaches best case.

In Practice

In application code, use language built-in sorting and only define custom keys.
For large-scale data, consider external sorting (disk, chunks) and distributed frameworks.

Comparison and Alternatives

Situation	Recommendation
General list sorting	`list.sort` / `sorted`
Top-k	Heap
Uniform integer distribution	Counting sort (separate article)

Additional Resources

Python Sorting HOW TO
CLRS — Introduction to Algorithms (sorting reference)

Summary

Key Points

Bubble: Adjacent swaps, O(n²), stable
Selection: Select minimum, O(n²), unstable
Insertion: Insert into sorted portion, O(n²), stable
Practice: Use Python sort() (Timsort)

Complexity Comparison

Sort	Best	Average	Worst	When to Use
Bubble	O(n)	O(n²)	O(n²)	Nearly sorted
Selection	O(n²)	O(n²)	O(n²)	Minimize swaps
Insertion	O(n)	O(n²)	O(n²)	Nearly sorted, small arrays

Next Steps

Advanced Sorting (Quick/Merge/Heap)

Keywords

Sorting Algorithm, Bubble Sort, Selection Sort, Insertion Sort, Time Complexity, Stable Sort, Coding Interview, Algorithm, O(n²), Timsort

이 글의 핵심

Introduction

”Sorting is the Beginning of Algorithms”

Sorting is the most fundamental algorithm. It’s the best topic for learning time complexity analysis and optimization.

1. Bubble Sort

Algorithm

Python Implementation

Time Complexity

2. Selection Sort

Algorithm

Python Implementation

Time Complexity

3. Insertion Sort

Algorithm

Python Implementation

Time Complexity

4. Sorting Comparison

When to Use Each

5. Python Built-in Sorting

sorted() vs sort()

Timsort (Python’s Default)

Practical Tips

Coding Interview Tips

Advanced Example: Stable Sort with Keys

Common Mistakes

Cautions

In Practice

Comparison and Alternatives

Additional Resources

Summary

Key Points

Complexity Comparison

Next Steps

Related Posts

Keywords