Sorting · การจัดเรียง (Sorting)
Putting items in order
- Sorting arranges a list into order, usually smallest first.
- The key move is a swap: exchange two items.
- In Python:
a[i], a[j] = a[j], a[i]swaps two list items in one line.
การจัดเรียงรายการตามลำดับ
- การจัดเรียง จัดลิสต์ให้อยู่ตามลำดับ โดยปกติเริ่มจากตัวเล็กสุดก่อน
- การเคลื่อนไหวหลักคือการ สลับ: เปลี่ยนที่สองรายการ
- ใน Python:
a[i], a[j] = a[j], a[i]สลับสองรายการในลิสต์ได้ในบรรทัดเดียว
Bubble sort
- Compare each pair of neighbours; swap them if they are out of order.
- After one full pass, the largest item has "bubbled" to the end.
- Repeat the passes until no swaps are needed.
บับเบิลซอร์ต
- เปรียบเทียบคู่ของ เพื่อนบ้าน ทุกคู่; สลับหากไม่เรียงลำดับ
- หลังการทำรอบเต็มหนึ่งรอบ รายการที่มีค่าสูงสุดจะ "ฟอง" ไปยังท้าย
- ทำรอบซ้ำจนไม่ต้องสลับอีก
data = [3, 1, 2]
n = len(data)
for i in range(n - 1):
for j in range(n - 1 - i):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
print(data)
Insertion sort
- Treat the left part of the list as already sorted.
- Take the next item and slide it left until it sits in the right place.
- Like sorting playing cards in your hand, one at a time.
อินเซอร์ชันซอร์ต
- พิจารณาส่วนซ้ายของลิสต์ว่าเป็นส่วนที่เรียงลำดับแล้ว
- นำรายการถัดมาเลื่อนไปทางซ้ายจนวางอยู่ในตำแหน่งที่ถูกต้อง
- เหมือนการจัดไพ่ในมือของคุณทีละใบ
data = [3, 1, 2]
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and data[j] > key:
data[j + 1] = data[j]
j = j - 1
data[j + 1] = key
print(data)
Compare them
- Both check roughly
n × npairs, so both are slow on big lists. - Insertion sort is fast when the list is almost sorted already.
- Faster methods exist, but bubble and insertion are easy to understand.
เปรียบเทียบกัน
- ทั้งคู่ตรวจสอบคู่ประมาณ
n × nดังนั้นจึงช้าสำหรับลิสต์ใหญ่ - อินเซอร์ชันซอร์ตเร็วเมื่อลิสต์ เกือบ เรียงลำดับอยู่แล้ว
- มีวิธีที่เร็วกว่านี้ แต่บับเบิลและอินเซอร์ชันเข้าใจง่าย
In Cambridge pseudocode
- Bubble sort with a
tempvariable for the swap.
ใน伪代码 Cambridge
- บับเบิลซอร์ตพร้อมตัวแปร
tempสำหรับสลับ
FOR i ← 0 TO LENGTH(list) - 2
FOR j ← 0 TO LENGTH(list) - 2 - i
IF list[j] > list[j + 1] THEN
temp ← list[j]
list[j] ← list[j + 1]
list[j + 1] ← temp
ENDIF
NEXT j
NEXT i
Common mistakes
- Bubble and insertion sort are both O(n²).
- Trace a small list by hand to check your sort works.
ข้อผิดพลาดที่พบบ่อย
- บับเบิลซอร์ตและอินเซอร์ชันซอร์ตเป็น O(n²) ทั้งคู่
- Trace ลิสต์ขนาดเล็กด้วยมือเพื่อตรวจสอบว่าซอร์ตทำงานถูกต้อง
Now you try
- Each task changes the list in place — no need to return it.
- Press Check answer to test your code.
ลองดูเลย
- แต่ละงานเปลี่ยนลิสต์ ในสถานที่ — ไม่จำเป็นต้องคืนค่า
- กด Check answer เพื่อทดสอบโค้ดของคุณ
Watch a sort run · ดูการจัดเรียงทำงาน
Sorting repeatedly compares and swaps until everything is in order. · การจัดเรียงเปรียบเทียบและสลับซ้ำจนกว่าทุกอย่างจะอยู่ในลำดับที่ถูกต้อง
Write swap(items, i, j) that exchanges the items at index i and index j in the list. Change the list in place (no return). · เขียน swap(items, i, j) ที่แลกเปลี่ยนรายการที่ดัชนี i และดัชนี j ใน list. เปลี่ยน list โดยตรง (ไม่ return)
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Write bubble_sort(items) that sorts the list into ascending order using bubble sort. Change the list in place. · เขียน bubble_sort(items) ที่จัดเรียง list เป็นลำดับเพิ่มขึ้นโดยใช้ Bubble sort. เปลี่ยน list โดยตรง
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Write insertion_sort(items) that sorts the list into ascending order using insertion sort. Change the list in place. · เขียน insertion_sort(items) ที่จัดเรียง list เป็นลำดับเพิ่มขึ้นโดยใช้ Insertion sort. เปลี่ยน list โดยตรง
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่