อัลกอริทึม Python

การเรียงแบบเลือก (selection sort) ใน Python

ในบทเรียนนี้ คุณจะเขียนการเรียงแบบเลือก โดยหาสมาชิกที่เล็กที่สุดทุกครั้งแล้ววางในตำแหน่งที่ถูกต้อง

  • ระดับกลาง
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง

บทนำ

ปัญหาที่ต้องแก้

อัลกอริทึมเรียงลำดับบางตัวพยายามย้ายข้อมูลให้น้อยที่สุด ซึ่งสำคัญมากเมื่อการย้ายแต่ละครั้งมีต้นทุนสูง 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 ครั้ง

ประเด็นสำคัญ

  1. ทุกตัวทางซ้ายของ start เรียงแล้ว ส่วนตั้งแต่ start เป็นต้นไปยังไม่เรียง
  2. minimum จำดัชนีของค่าที่เล็กที่สุดเท่าที่เจอในส่วนที่ยังไม่เรียง
  3. ลูปด้านใน for index in range(start + 1, len(result)): กวาดดูส่วนที่เหลือของลิสต์
  4. result[start], result[minimum] = result[minimum], result[start] สลับตำแหน่งละหนึ่งครั้ง

ใช้เมื่อไร?

  • เรียนรู้แนวคิดการเรียงลำดับแบบต่าง ๆ และเปรียบเทียบกัน
  • งานที่การเขียนหรือย้ายข้อมูลมีต้นทุนสูง แต่การเปรียบเทียบมีต้นทุนต่ำ
  • หา k รายการที่เล็กที่สุดด้วยการหยุดหลัง k รอบ

เมื่อไรยังไม่จำเป็น

  • โปรแกรมจริง: sorted() เร็วกว่ามาก
  • ข้อมูลที่เกือบเรียงแล้ว: selection sort ยังกวาดดูทุกอย่าง ขณะที่ insertion sort จบได้เร็ว

ภาพจำลอง การเรียงแบบเลือก (selection sort) ใน Python

O(n²)

กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น

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

รันโค้ด →
main.py
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]))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

[11, 12, 22, 25, 64]

อธิบายโค้ด

ตัวแปร minimum จำตำแหน่งของค่าที่เล็กที่สุดในส่วนที่เหลือของลิสต์ เมื่อจบแต่ละรอบ ค่านั้นจะถูกสลับกับตำแหน่ง start อัลกอริทึมมีความซับซ้อน O(n²) เสมอเพราะต้องเปรียบเทียบหลายครั้ง แต่สลับที่ไม่เกิน n ครั้ง

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
  3. จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
รันในคอมไพเลอร์ Python →

ข้อผิดพลาดที่พบบ่อย

สลับข้างในลูปด้านใน

วิธีนี้กลายเป็นการเรียงที่ช้ากว่าและยุ่งกว่า เพราะต้องสลับหลายครั้ง

ปัญหา
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

โจทย์ทั้งหมด