การเรียงแบบเลือก (selection sort) ใน Python
ในบทเรียนนี้ คุณจะเขียนการเรียงแบบเลือก โดยหาสมาชิกที่เล็กที่สุดทุกครั้งแล้ววางในตำแหน่งที่ถูกต้อง
บทนำ
ปัญหาที่ต้องแก้
อัลกอริทึมเรียงลำดับบางตัวพยายามย้ายข้อมูลให้น้อยที่สุด ซึ่งสำคัญมากเมื่อการย้ายแต่ละครั้งมีต้นทุนสูง selection sort ใช้แนวคิดที่ต่างจาก bubble sort: หาตัวที่ถูกต้องให้เจอก่อน แล้วค่อยย้ายครั้งเดียว
ลองนึกภาพแบบนี้
selection sort เหมือนการจัดทีมเรียงตามความสูง เรากวาดตาดูทุกคนที่ยังรออยู่ เรียกคนที่เตี้ยที่สุดออกมายืนที่ตำแหน่งถัดไปในแถว แล้วกวาดตาดูคนที่เหลืออีกรอบเพื่อหาคนเตี้ยที่สุดคนต่อไป ทำแบบนี้จนไม่เหลือใคร
for start in range(len(result)):📍 ตำแหน่งว่างถัดไปในแถวminimum = start🤔 สมมติว่าคนนี้เตี้ยที่สุดresult[index] < result[minimum]🔎 กวาดดูที่เหลือหาคนที่เตี้ยกว่าresult[start], result[minimum] = ...🔄 ย้ายคนที่เตี้ยที่สุดเข้าตำแหน่งว่างselection sort หาตัวที่เล็กที่สุดในส่วนที่ยังไม่เรียงซ้ำไปเรื่อย ๆ แล้วสลับเข้าตำแหน่งถัดไปของส่วนที่เรียงแล้ว ใช้การเปรียบเทียบ O(n²) ครั้ง แต่สลับไม่เกิน n - 1 ครั้ง
ประเด็นสำคัญ
- ทุกตัวทางซ้ายของ
startเรียงแล้ว ส่วนตั้งแต่startเป็นต้นไปยังไม่เรียง minimumจำดัชนีของค่าที่เล็กที่สุดเท่าที่เจอในส่วนที่ยังไม่เรียง- ลูปด้านใน
for index in range(start + 1, len(result)):กวาดดูส่วนที่เหลือของลิสต์ result[start], result[minimum] = result[minimum], result[start]สลับตำแหน่งละหนึ่งครั้ง
ใช้เมื่อไร?
- เรียนรู้แนวคิดการเรียงลำดับแบบต่าง ๆ และเปรียบเทียบกัน
- งานที่การเขียนหรือย้ายข้อมูลมีต้นทุนสูง แต่การเปรียบเทียบมีต้นทุนต่ำ
- หา k รายการที่เล็กที่สุดด้วยการหยุดหลัง k รอบ
เมื่อไรยังไม่จำเป็น
- โปรแกรมจริง:
sorted()เร็วกว่ามาก - ข้อมูลที่เกือบเรียงแล้ว: selection sort ยังกวาดดูทุกอย่าง ขณะที่ insertion sort จบได้เร็ว
ภาพจำลอง การเรียงแบบเลือก (selection sort) ใน Python
O(n²)กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น
โค้ดตัวอย่าง
def selection_sort(values):
result = values.copy()
for start in range(len(result)):
minimum = start
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
return result
print(selection_sort([64, 25, 12, 22, 11]))
ผลลัพธ์จากการรัน
[11, 12, 22, 25, 64]
อธิบายโค้ด
ตัวแปร minimum จำตำแหน่งของค่าที่เล็กที่สุดในส่วนที่เหลือของลิสต์ เมื่อจบแต่ละรอบ ค่านั้นจะถูกสลับกับตำแหน่ง start อัลกอริทึมมีความซับซ้อน O(n²) เสมอเพราะต้องเปรียบเทียบหลายครั้ง แต่สลับที่ไม่เกิน n ครั้ง
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
สลับข้างในลูปด้านใน
วิธีนี้กลายเป็นการเรียงที่ช้ากว่าและยุ่งกว่า เพราะต้องสลับหลายครั้ง
for index in range(start + 1, len(result)):
if result[index] < result[start]:
result[start], result[index] = result[index], result[start]
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
เรียนบทนี้จบแล้วใช่ไหม
ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า
ฝึกด้วยโจทย์
ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI
- หาค่าน้อยสุดในอาเรย์ หาค่าที่น้อยที่สุดในลิสต์ ง่าย
- K-th Smallest Element Find the k-th smallest value without fully sorting. ปานกลาง