การเรียงแบบฟองและการเรียงแบบแทรก
เขียนอัลกอริทึมการเรียงลำดับกำลังสองทั้งสองแบบ ทำความเข้าใจว่าเหตุใดจึงเป็น O(n²) และรู้จักกรณีเดียวที่การเรียงแบบแทรกดีกว่าการเรียงแบบผสาน
การเรียงแบบฟองและการเรียงแบบแทรก เป็นบทเรียน DSA Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน DSA Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
เหตุใดจึงควรศึกษาอัลกอริทึมการเรียงลำดับ O(n²)
การเรียงลำดับแบบฟองและการเรียงลำดับแบบแทรกใช้เวลา O(n²) ในกรณีเลวร้ายที่สุด จึงไม่เหมาะกับข้อมูลเข้าขนาดใหญ่ อย่างไรก็ตาม การสัมภาษณ์อัลกอริทึมอย่างจริงจังทุกครั้งคาดหวังให้คุณเขียนและวิเคราะห์อัลกอริทึมเหล่านี้ได้ อัลกอริทึมเหล่านี้สอนแนวคิดพื้นฐาน เช่น การเปรียบเทียบ การสลับค่า การเรียงลำดับแบบเสถียร และพฤติกรรมในกรณีดีที่สุด ซึ่งนำไปใช้กับอัลกอริทึมขั้นสูงได้ ผู้สัมภาษณ์ใช้หัวข้อนี้ทดสอบว่าคุณสามารถให้เหตุผลเกี่ยวกับสิ่งคงที่ของลูปและสัญกรณ์เชิงเส้นกำกับจากหลักพื้นฐานได้หรือไม่
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')การเรียงลำดับแบบฟอง: ทำให้ค่าสูงสุดลอยขึ้น
การเรียงลำดับแบบฟอง จะสแกนอาร์เรย์ซ้ำ ๆ และสลับสมาชิกที่อยู่ติดกันเมื่อเรียงผิดลำดับ หลังจบรอบเต็มแต่ละรอบ สมาชิกที่ยังไม่ได้เรียงซึ่งมีค่ามากที่สุดจะ “ลอยขึ้น” ไปยังตำแหน่งสุดท้ายของมัน หลังผ่าน n-1 รอบ อาร์เรย์ทั้งหมดจะเรียงลำดับแล้ว ชื่อนี้มาจากลักษณะที่สมาชิกค่ามากลอยขึ้นเหมือนฟองอากาศ เป็นอัลกอริทึมการเรียงลำดับที่อธิบายได้ง่ายที่สุด แต่แทบไม่ใช้ในทางปฏิบัติ
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]การเรียงลำดับแบบฟองพร้อมการจบก่อนกำหนด
การเรียงลำดับแบบฟองที่ปรับปรุงแล้วใช้ตัวบ่งชี้ swapped หากรอบเต็มของลูปด้านในไม่เกิดการสลับค่าเลย แสดงว่าอาร์เรย์เรียงลำดับแล้วและเราสามารถจบการทำงานก่อนกำหนดได้ วิธีนี้ทำให้กรณีดีที่สุดใช้เวลา O(n) สำหรับข้อมูลเข้าที่เรียงลำดับอยู่แล้ว ซึ่งเป็นข้อได้เปรียบที่แท้จริงเพียงอย่างเดียวของการเรียงลำดับแบบฟอง หากไม่มีตัวบ่งชี้นี้ อัลกอริทึมจะเปรียบเทียบ O(n²) ครั้งเสมอ การปรับปรุงด้วยการจบก่อนกำหนดคือสิ่งที่ผู้สัมภาษณ์ตรวจสอบเมื่อถามถึงการปรับปรุงการเรียงลำดับแบบฟอง
def bubble_sort_optimised(arr):
n = len(arr)
for i in range(n - 1):
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
if not swapped: # already sorted!
print(f'Sorted after pass {i+1}')
break
arr1 = [1, 2, 3, 4, 5] # already sorted
bubble_sort_optimised(arr1) # exits after 1 passการวิเคราะห์ความซับซ้อนของการเรียงลำดับแบบฟอง
ลูปด้านนอกของการเรียงลำดับแบบฟองทำงาน n-1 ครั้ง ลูปด้านในทำงาน n-1-i ครั้งต่อรอบ: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 ครั้งของการเปรียบเทียบ จึงได้ O(n²) ในกรณีเฉลี่ยและกรณีเลวร้ายที่สุด เมื่อใช้ตัวบ่งชี้การจบก่อนกำหนด กรณีดีที่สุดจะลดลงเหลือ O(n) สำหรับข้อมูลเข้าที่เรียงลำดับแล้ว ความซับซ้อนด้านพื้นที่คือ O(1) โดยมีเพียงการสลับค่าที่ต้องใช้ตัวแปรชั่วคราว การเรียงลำดับแบบฟองมี เสถียรภาพ: สมาชิกที่เท่ากันจะรักษาลำดับสัมพัทธ์เดิมไว้ เนื่องจากเราสลับเฉพาะสมาชิกที่มากกว่าอย่างเคร่งครัดเท่านั้น
def bubble_sort_counted(arr):
n = len(arr)
swaps = comparisons = 0
for i in range(n-1):
for j in range(n-1-i):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return comparisons, swaps
arr = [5, 4, 3, 2, 1] # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}') # 10, 10 for n=5การเรียงลำดับแบบแทรก: สร้างชุดไพ่ที่เรียงแล้ว
การเรียงลำดับแบบแทรก จำลองการเรียงไพ่ในมือ: หยิบไพ่ใบถัดไป (สมาชิก) แล้วแทรกไว้ในตำแหน่งที่ถูกต้องท่ามกลางไพ่ที่เรียงแล้วทางด้านซ้าย สิ่งคงที่คือ arr[0:i] จะเรียงลำดับอยู่เสมอ สำหรับสมาชิกใหม่แต่ละตัว ให้เลื่อนสมาชิกที่มีค่ามากกว่าไปทางขวาเพื่อเปิดพื้นที่ อัลกอริทึมนี้ทำงานในตำแหน่งเดิม มีเสถียรภาพ และมีกรณีเลวร้ายที่สุดเป็น O(n²) แต่กรณีดีที่สุดเป็น O(n) สำหรับข้อมูลที่เกือบเรียงลำดับแล้ว
def insertion_sort(arr):
for i in range(1, len(arr)): # start from second element
key = arr[i] # element to insert
j = i - 1
# Shift larger elements to the right
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # insert in correct position
return arr
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr) # [5, 6, 11, 12, 13]การเรียงลำดับแบบแทรกทีละขั้นตอน
ติดตามการทำงานของการเรียงลำดับแบบแทรกกับ [3, 1, 4, 2]: i=1, key=1, เลื่อน 3 ไปทางขวา → [1, 3, 4, 2] i=2, key=4, ไม่ต้องเลื่อน → ไม่เปลี่ยนแปลง i=3, key=2, เลื่อน 4 แล้วจึงเลื่อน 3 ไปทางขวา → [1, 2, 3, 4] สมาชิกแต่ละตัวจะถูกเปรียบเทียบกับสมาชิกทางซ้ายจนกว่าจะพบตำแหน่งที่ถูกต้อง ลูปด้านใน while ทำการเลื่อนด้วยการกำหนดค่า ซึ่งเร็วกว่าอัลกอริทึมที่ใช้การสลับค่า เพราะการกำหนดค่าใช้หนึ่งครั้งต่อการเลื่อนหนึ่งครั้ง ในขณะที่การสลับค่าต้องใช้สามครั้ง
def insertion_sort_trace(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] # shift right (1 assignment)
j -= 1
arr[j+1] = key
print(f'After inserting {key}: {arr}')
insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2] (no change)
# After inserting 2: [1, 2, 3, 4]การเรียงลำดับแบบแทรกกับข้อมูลที่เกือบเรียงลำดับแล้ว
จุดเด่นสำคัญของการเรียงลำดับแบบแทรกคือความซับซ้อน O(n + จำนวนการผกผัน) การผกผัน คือคู่ (i,j) ที่ i < j แต่ arr[i] > arr[j] สำหรับอาร์เรย์ที่เกือบเรียงลำดับและมีการผกผันเพียงไม่กี่คู่ การเรียงลำดับแบบแทรกจะทำงานเร็วมาก บางครั้งเร็วกว่า merge sort ในทางปฏิบัติเนื่องจากความเรียบง่ายและรูปแบบการเข้าถึงที่ใช้แคชได้ดี ทิมซอร์ตของไพทอนใช้การเรียงลำดับแบบแทรกกับอาร์เรย์ย่อยขนาดเล็กด้วยเหตุผลนี้โดยเฉพาะ
# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5] # 4>3 is the only inversion
def count_ops(arr):
arr = arr[:]
ops = 0
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; ops += 1
arr[j+1] = key
return ops
print(count_ops([1,2,4,3,5])) # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1])) # 10 ops (reversed = worst case)ความเสถียรในการเรียงลำดับ
อัลกอริทึมการเรียงลำดับมี เสถียรภาพ หากสมาชิกที่เท่ากันรักษาลำดับสัมพัทธ์เดิมไว้หลังการเรียงลำดับ ทั้งการเรียงลำดับแบบฟองและการเรียงลำดับแบบแทรกมีเสถียรภาพ เพราะไม่เคยสลับสมาชิกที่เท่ากัน ความเสถียรมีความสำคัญเมื่อเรียงลำดับด้วยคีย์หลายตัวต่อเนื่องกัน: ใช้ sort ตามคีย์รองก่อน (โดยคงเสถียรภาพ) จากนั้นใช้ sort ตามคีย์หลัก (โดยคงเสถียรภาพ) เพื่อรักษาลำดับตามคีย์รองของสมาชิกที่มีค่าเท่ากัน การเรียงลำดับแบบผสานก็มีเสถียรภาพเช่นกัน ส่วนการเรียงลำดับแบบกองและการเรียงลำดับแบบเร็วมักไม่มีเสถียรภาพ
# Stable sort preserves order of equal elements
students = [
('Alice', 85),
('Bob', 92),
('Carol', 85),
('Dave', 78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol => stableการเรียงลำดับแบบแทรกโดยใช้การค้นหาแบบทวิภาค
ลูปด้านในของการเรียงลำดับแบบแทรกทำหน้าที่ทั้งค้นหาตำแหน่งที่ถูกต้องและเลื่อนสมาชิก คุณสามารถใช้การค้นหาแบบทวิภาคเพื่อค้นหาตำแหน่งด้วยการเปรียบเทียบ O(log i) ครั้ง แต่การเลื่อนยังคงใช้เวลา O(i) ดังนั้นความซับซ้อนโดยรวมจึงยังเป็น O(n²) การปรับปรุงนี้ลดจำนวนการเปรียบเทียบ (มีประโยชน์เมื่อฟังก์ชันเปรียบเทียบใช้เวลานาน) แต่ไม่ได้ลดจำนวนการดำเนินการทั้งหมด การเรียงลำดับแบบแทรกด้วยการค้นหาแบบทวิภาคนี้ปรากฏในทิมซอร์ตสำหรับขนาดส่วนย่อยเล็ก ๆ
import bisect
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Find insertion point in O(log i)
pos = bisect.bisect_left(arr, key, 0, i)
# Shift elements to make room: still O(i)
arr[pos+1:i+1] = arr[pos:i]
arr[pos] = key
return arr
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]ฟองกับแทรก: ควรใช้แต่ละแบบเมื่อใด
ในการสัมภาษณ์ ให้กล่าวถึงการเปรียบเทียบนี้อย่างมั่นใจ: การเรียงลำดับแบบแทรกดีกว่าการเรียงลำดับแบบฟองอย่างชัดเจน ทั้งสองแบบมีกรณีเลวร้ายที่สุดเป็น O(n²) และใช้พื้นที่ O(1) แต่การเรียงลำดับแบบแทรกเขียนค่าน้อยกว่า (O(n+k) เมื่อมีการผกผัน k คู่ เทียบกับ O(n²) สำหรับการเรียงลำดับแบบฟอง) ใช้แคชได้ดีกว่า และเป็นตัวเลือกในทางปฏิบัติสำหรับ n ขนาดเล็ก (ทิมซอร์ตใช้วิธีนี้) ข้อได้เปรียบที่แท้จริงเพียงอย่างเดียวของการเรียงลำดับแบบฟองคือความเรียบง่ายในเชิงการสอน ในการใช้งานจริง ให้ใช้ sort ที่มีมาให้ในภาษาเสมอ
# Summary: when to use quadratic sorts
# Use insertion_sort when:
# - n <= 20 (small enough that O(n^2) is fine)
# - data is nearly sorted (few inversions => fast)
# - you need stable sort with O(1) space
# - implementing a hybrid (like Timsort)
# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr)) # [1, 2, 5, 8, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]การนับการผกผันเป็นตัวชี้วัด
จำนวน การผกผัน ในอาร์เรย์เท่ากับจำนวนคู่ (i,j) ที่ i < j แต่ arr[i] > arr[j] การเรียงลำดับแบบแทรกจะเลื่อนสมาชิกเป็นจำนวนเท่ากับจำนวนการผกผันพอดี ซึ่งเป็นข้อสังเกตที่มีประโยชน์ การนับการผกผันอย่างมีประสิทธิภาพ (O(n log n)) ต้องใช้การเรียงลำดับแบบผสานที่ปรับแก้ ผู้สัมภาษณ์บางครั้งถามต่อจากการพูดคุยเรื่องการเรียงลำดับว่า “อัลกอริทึมของคุณตระหนักถึงการผกผันมากน้อยเพียงใด”
# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([3, 1, 2])) # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3])) # 0: already sorted
print(count_inversions_naive([3, 2, 1])) # 3: all pairs invertedตรวจสอบความเข้าใจ
ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้
ทบทวนบทเรียน
ในบทเรียนนี้ คุณได้เรียนรู้ว่า การเรียงลำดับแบบฟองทำงาน n-1 รอบ โดยแต่ละรอบทำให้ค่าสูงสุดในขณะนั้นไปอยู่ในตำแหน่งสุดท้ายของมัน มีกรณีเลวร้ายที่สุดเป็น O(n²) แต่กรณีดีที่สุดเป็น O(n) เมื่อใช้ตัวบ่งชี้การจบก่อนกำหนด การเรียงลำดับแบบแทรกเลื่อนสมาชิกไปทางขวาเพื่อแทรก key ปัจจุบันลงในตำแหน่งที่ถูกต้องตามลำดับ ใช้เวลา O(n + จำนวนการผกผัน) จึงเหมาะที่สุดกับข้อมูลที่เกือบเรียงลำดับแล้ว และ อัลกอริทึมทั้งสองมีเสถียรภาพ ใช้พื้นที่ O(1) และมีกรณีเลวร้ายที่สุดเป็น O(n²) แต่การเรียงลำดับแบบแทรกเป็นตัวเลือกที่ดีกว่าการเรียงลำดับแบบฟองอย่างชัดเจนในทุกกรณีที่ใช้งานจริง บทถัดไปเราจะเขียนการเรียงลำดับแบบผสานตั้งแต่ต้น
คำถามที่พบบ่อย
บทเรียน “การเรียงแบบฟองและการเรียงแบบแทรก” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การเรียงแบบฟองและการเรียงแบบแทรก” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส DSA Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การเรียงแบบฟองและการเรียงแบบแทรก”
เขียนอัลกอริทึมการเรียงลำดับกำลังสองทั้งสองแบบ ทำความเข้าใจว่าเหตุใดจึงเป็น O(n²) และรู้จักกรณีเดียวที่การเรียงแบบแทรกดีกว่าการเรียงแบบผสาน คุณปฏิบัติ DSA Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน DSA Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน DSA Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “การเรียงแบบฟองและการเรียงแบบแทรก” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน DSA Interview Prep นี้ได้ไหม
ได้ บทเรียน DSA Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การเรียงแบบฟองและการเรียงแบบแทรก
- การเรียงแบบผสาน: แบ่ง เรียง ผสาน
- การเรียงแบบเร็วและการเลือกหมุด
- การเรียงที่ไม่เปรียบเทียบและ sort() ของ Python