Bubble Sort ใน Python คืออะไร อธิบายพร้อมตัวอย่าง

Bubble Sort คืออะไร?

Bubble Sort เป็น Sorting Algorithm สำหรับเรียง List ให้เป็น Ascending (หรือ Descending) Order เป็น Algorithm ที่เข้าใจง่ายที่สุด แต่ไม่ค่อยมีประสิทธิภาพ Time Complexity O(n²) ใช้ได้กับ Input ขนาดเล็ก แต่ไม่เหมาะกับ List ใหญ่

ข้อดี: In-place Sorting (ไม่ใช้ Extra Space) Space Complexity O(1)

Bubble Sort ทำงานอย่างไร?

ใช้ Nested Loop 2 ชั้น:

Outer Loop: วน n รอบ
Inner Loop: เปรียบเทียบ Element ติดกัน ทุกคู่ใน Array

Logic หลัก: เปรียบเทียบ 2 Element ติดกัน ถ้าตัวแรก > ตัวถัดไป → Swap ให้ตัวเล็กมาหน้า ตัวใหญ่ไปหลัง

หลังรอบ Outer Loop ที่ 1: Element ใหญ่สุดจะอยู่ Index สุดท้าย
หลังรอบที่ 2: Element ใหญ่เป็นอันดับ 2 จะอยู่ Index สุดท้าย-1
... จนครบ

ตัวอย่างการทำงาน (Visual)

Array เริ่มต้น: [5, 2, 1, 3, 4]

Outer Loop = 1

5 > 2 → Swap → [2, 5, 1, 3, 4]

5 > 1 → Swap → [2, 1, 5, 3, 4]

5 > 3 → Swap → [2, 1, 3, 5, 4]

5 > 4 → Swap → [2, 1, 3, 4, 5] ← 5 (Max) อยู่ท้ายแล้ว

Outer Loop = 2

2 > 1 → Swap → [1, 2, 3, 4, 5]

... ไม่มี Swap อีกแล้ว (แต่ Loop ยังทำต่อจนครบ n รอบ)

ตัวอย่างโค้ด

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # Optimization: ถ้าไม่มี Swap ในรอบนี้ = เรียงแล้ว
        swapped = False
        for j in range(n - 1 - i):  # -i เพราะท้ายเรียงแล้ว
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # Pythonic Swap
                swapped = True
        if not swapped:
            break  # Early Exit
    return arr

array = [2, 3, 1, 5, 4]
print("Original:", array)
print("Sorted:  ", bubble_sort(array))

ผลลัพธ์

Original: [2, 3, 1, 5, 4]
Sorted:   [1, 2, 3, 4, 5]

Optimized Bubble Sort

def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        # Last i elements already sorted
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

Complexity Analysis

Case	Time Complexity	Notes
Best	O(n)	Already sorted (with optimization)
Average	O(n²)
Worst	O(n²)	Reverse sorted
Space	O(1)	In-place
Stable	Yes	Equal elements keep order

เมื่อไหร่ควรใช้ Bubble Sort?

ข้อมูลเล็กมาก (n < 50)
ข้อมูลเรียงเกือบเสร็จแล้ว (Nearly Sorted)
การศึกษา/สอน Algorithm พื้นฐาน
Memory จำกัดมาก (In-place)

Built-in Alternative

# Python ใช้ Timsort (O(n log n)) - เร็วกว่ามาก
arr = [2, 3, 1, 5, 4]
arr.sort()        # In-place
sorted_arr = sorted(arr)  # New list
print(arr)  # [1, 2, 3, 4, 5]