Selection Sort ใน Python: คู่มือฉบับสมบูรณ์

Selection Sort ใน Python: คู่มือฉบับสมบูรณ์

Selection sort ใน Python แบ่งลิสต์ออกเป็นสองลิสต์เล็กๆ ลิสต์หนึ่งแทนองค์ประกอบที่จัดเรียงแล้ว อีกลิสต์หนึ่งมีองค์ประกอบที่ยังไม่จัดเรียง Selection sort หาค่าที่น้อยที่สุดหรือมากที่สุดในแต่ละรอบ และย้ายค่าเหล่านั้นไปยังลิสต์ที่จัดเรียงแล้ว

การจัดเรียงลิสต์เป็นการดำเนินการที่พบบ่อยในหลายโปรแกรม

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

นี่คือที่มาของ Selection sort Selection sort เป็นอัลกอริทึมที่ใช้จัดเรียงลิสต์ในลำดับน้อยไปมากหรือมากไปน้อย

ในคู่มือนี้ เราจะอธิบายวิธีเขียนโปรแกรม Selection sort ใน Python เราจะเดินทางผ่านตัวอย่างตลอดคู่มือ เพื่อให้คุณเรียนรู้รายละเอียดของ Selection sorts

Selection Sort ใน Python คืออะไร?

Selection sort ใน Python หาองค์ประกอบที่น้อยที่สุดในลิสต์ซ้ำๆ และย้ายองค์ประกอบนั้นไปยังปลายหนึ่งของลิสต์ การจัดเรียงทำต่อไปจนกว่าอาร์เรย์จะจัดเรียงตามลำดับ คุณยังสามารถสั่งให้ Selection sort หาค่าสูงสุดได้ ทั้งสองวิธีจัดเรียงลิสต์ได้

Selection sort สมมติว่าองค์ประกอบแรกในลิสต์คือค่าน้อยที่สุด การจัดเรียงจะเปรียบเทียบค่านั้นกับองค์ประกอบที่สอง หากองค์ประกอบที่สองน้อยกว่าค่าน้อยที่สุด องค์ประกอบที่สองจะกลายเป็นค่าน้อยที่สุด

กระบวนการนี้ซ้ำจนถึงองค์ประกอบสุดท้ายของลิสต์ เมื่อถึงองค์ประกอบสุดท้าย ค่าน้อยที่สุดจะถูกวางไว้ที่ต้นของลิสต์ unsorted

คู่มือ Selection Sort ใน Python

ไม่มีวิธีเรียนรู้ Selection sorts ดีกว่าการวิ่งผ่านตัวอย่าง มาเรียงลำดับคะแนนนักเรียนในลำดับน้อยไปมาก พิจารณาลิสต์ที่ยังไม่จัดเรียง:

เราจะเริ่มต้นด้วยการเรียกค่าแรกของลิสต์ว่า minimum แต่ละรอบของ Selection sort จะหาองค์ประกอบที่น้อยที่สุดและย้ายไปยังสับอาร์เรย์ที่จัดเรียงแล้ว

การจัดเรียงค่าน้อยที่สุดเป็นตัวเลือกหนึ่ง Selection sort ทำงานได้หากจัดเรียงค่าสูงสุด แต่ในตัวอย่างนี้เราใช้ค่าน้อยที่สุด

ต่อไป เราจะเปรียบเทียบค่าน้อยที่สุดกับองค์ประกอบที่สอง หากองค์ประกอบนี้น้อยกว่า minimum องค์ประกอบที่สองควรกลายเป็นค่า minimum

เราจะเปรียบเทียบ 73 และ 62 73 มากกว่า 62 หมายความว่าค่า minimum ใหม่คือ 62 ลิสต์จะผ่านตัวเลขอื่นๆ ทั้งหมด:

• 61 มากกว่า 62 (ค่า minimum) หรือไม่? ไม่ ดังนั้นสลับตัวเลข Minimum กลายเป็น 61
• 69 มากกว่า 61 (ค่า minimum) หรือไม่? ใช่ ดังนั้นไม่ทำอะไร Minimum อยู่ที่ 61

ลิสต์ของเราดูเหมือนเดิม:

เมื่อถึงท้ายลิสต์ คุณสามารถย้าย minimum ไปต้นลิสต์:

61 (ค่า minimum) ถูกย้ายไปต้นลิสต์ และค่าอื่นๆ ขึ้นไปหนึ่งตำแหน่ง เราจะทำซ้ำกระบวนการนี้จนกว่าทุกองค์ประกอบจะจัดเรียงแล้ว

แต่ละรอบของลิสต์จะคืนค่า:

1. 73, 62, 61, 69
2. 61, 73, 62, 69
3. 61, 62, 73, 69
4. 61, 62, 69, 73

เมื่อ Selection sort ตรวจสอบทุกองค์ประกอบในลิสต์ การจัดเรียงจะหยุด

สับอาร์เรย์ที่จัดเรียงแล้วและสับอาร์เรย์ที่ยังไม่จัดเรียงทั้งคู่มองไม่เห็นโดยเรา อัลกอริทึมจัดเรียงอาร์เรย์ให้เราและติดตามส่วนที่ยังไม่จัดเรียงของอาร์เรย์

วิธีทำ Selection Sort ใน Python

คุณคุ้นเคยกับทฤษฎีแล้ว: ยินดีด้วย! ถึงเวลาท้าทายใหญ่ เราจะนำอัลกอริทึม Selection sort มาใช้ใน Python มาเขียนโปรแกรมที่รับอาร์เรย์ Python และจัดเรียงในลำดับน้อยไปมาก

กำหนดฟังก์ชันจัดเรียง

เริ่มต้นด้วยการกำหนดฟังก์ชัน Python ที่ทำ Selection sort:

def sortList(array):
    length = len(array)
    for item in range(length):
        minimum = item
        for i in range(item + 1, length):
            if array[i] < array[minimum]:
                minimum = i
        (array[item], array[minimum]) = (array[minimum], array[item])

เราเริ่มต้นด้วยการใช้เมธอด len() ของ Python เพื่อหาความยาวของลิสต์ เราใช้ค่านี้เริ่มลูป for วนผ่านทุกรายการในลิสต์

สำหรับแต่ละรอบในลูป เราตั้งค่า minimum เป็นรายการแรกในลิสต์ เราทำเช่นนี้ในการเดินทางก่อนหน้า หลังจากตั้งค่า minimum แล้ว ลูป for อีกอันเริ่มต้น วนผ่านทุกรายการในลิสต์

สำหรับแต่ละรายการในลิสต์ อัลกอริทึมตรวจสอบว่าค่า minimum มากกว่ารายการนั้นหรือไม่ หากใช่ ไม่เกิดอะไรขึ้น มิฉะนั้น ค่า minimum จะกลายเป็นรายการที่โปรแกรมกำลังอ่าน

หลังวนผ่านทุกรายการในลิสต์ อัลกอริทึมย้ายค่า minimum ไปต้นลิสต์ โปรแกรมจะทำต่อจนกว่าลูป for บนสุดจะสิ้นสุด เนื่องจาก Selection sorts รันจำนวนครั้งเท่ากับความยาวของลิสต์

เรียกใช้ฟังก์ชันจัดเรียง

คุณอาจสังเกตว่าถ้ารันโปรแกรม ไม่มีอะไรเกิดขึ้น เพราะเรายังไม่บอกโค้ดว่าใช้ค่าไหน เพิ่มโค้ดต่อไปนี้ท้ายโปรแกรม นอกฟังก์ชัน sortList:

numbers = [73, 62, 61, 69]
sortList(numbers)
print("Sorted list:", numbers)

เมื่อรันโปรแกรม จะคืนค่า:

[61, 62, 69, 73]

ลิสต์ของเราถูกจัดเรียงแล้ว เต้านั้วมือให้ตัวเอง คุณทำได้แล้ว!

Selection sorts สามารถจัดเรียงลิสต์ในลำดับมากไปน้อยได้ หากต้องการจัดเรียงแบบนี้ ให้เปลี่ยนคำสั่ง "if" ใน Selection sort เป็น:

if array[i] > array[minimum]:

เราเปลี่ยนเครื่องหมายน้อยกว่าเป็นมากกว่า จะจัดเรียงลิสต์ในลำดับมากไปน้อย เพราะค่า minimum จะถูกตั้งให้เป็นค่าสูงสุดในลิสต์ ทางเทคนิค ค่า minimum กลายเป็นค่า maximum

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

Selection sorts คล้าย Bubble sorts เหมาะสำหรับลิสต์ขนาดเล็ก เนื่องจากอัลกอริทึมไม่มีประสิทธิภาพเท่าอื่นๆ เช่น Insertion sort เมื่อใช้กับลิสต์ขนาดใหญ่

Selection sort เป็นการจัดเรียงที่ดีสำหรับการเรียนรู้เมื่อเริ่มต้นกับอัลกอริทึมจัดเรียง อื่นๆ อาจยากต่อการเชี่ยวชาญ แต่การเข้าใจ Selection sorts ชัดเจนช่วยให้คุณเข้าใจประเภทลิสต์ต่างๆ ได้

ความซับซ้อน (Complexity) ของ Selection Sort คืออะไร?

Selection sort มี time complexity เป็น O(n²) หมายความว่าความซับซ้อนของอัลกอริทึมจะเพิ่มขึ้นแบบเอ็กซ์โพเนนเชียล ขึ้นอยู่กับจำนวนองค์ประกอบในลิสต์

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

สรุป

Selection sorts เป็นวิธีสำคัญในการจัดเรียงข้อมูล Selection sorts อ่านทุกรายการในลิสต์ และในแต่ละรอบ ย้ายรายการที่น้อยที่สุดไปต้นลิสต์ เกิดขึ้นจนกว่าจะอ่านทุกรายการในลิสต์

Selection sorts ไม่ได้ใช้กันมากนอกเหนือจากการสอน เพราะมีอัลกอริทึมที่มีประสิทธิภาพมากกว่า แต่เป็นฐานที่ดีสู่การเรียนรู้การจัดเรียงอื่นๆ เช่น Insertion sort หรือ Merge sort

สนใจเรียนรู้เพิ่มเติมเกี่ยวกับ Python? อ่านคู่มือ How to Learn Python ของเรา เพื่อคำแนะนำจากผู้เชี่ยวชาญช่วยพัฒนาความรู้