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.

Sorting Algorithms | Bubble· Selection

2024년 1월 12일 · 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:

[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.

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:

[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:

[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

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?

[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:

[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

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:

[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

# 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()

# 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 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

# ✅ 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).

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

# ❌ 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

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

A. Master basic sorting algorithms: bubble, selection, and insertion sort.

Q. What should I read before this?

A. Follow the previous article or related articles links at the bottom of each post to learn in sequence.

Q. Where can I study this more deeply?

A. Check cppreference and the relevant library’s official documentation. The reference links at the end of the article are also worth using.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.

이 글의 핵심

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

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

Q. What should I read before this?

Q. Where can I study this more deeply?

Related Articles (Internal Links)

Keywords Covered in This Article (Related Search Terms)

이 글이 도움이 되셨나요?