วิธีเขียน Insertion Sort ใน Python

วิธีเขียน Insertion Sort ใน Python

Insertion sort ใน Python ทำงานคล้ายการจัดเรียงไพ่ในมือ สร้างสองลิสต์: ลิสต์ที่จัดเรียงแล้ว (sorted) และลิสต์ที่ยังไม่ได้จัดเรียง (unsorted) เปรียบเทียบแต่ละรายการในลิสต์ unsorted จนกว่าจะจัดเรียงรายการนั้นเสร็จ Insertion sort เป็นอัลกอริทึมมาตรฐานที่พบบ่อยใน Python

เคยจัดเรียงไพ่ในมือขณะเล่นไพ่ไหม? นั่นคือหนึ่งวิธีคิดเกี่ยวกับ Insertion sort ใน Python เมื่อต้องจัดเรียงลิสต์ที่มีเพียงไม่กี่องค์ประกอบ Insertion sort จะช่วยได้

Insertion sort วางองค์ประกอบที่ยังไม่ได้จัดเรียงไว้ในตำแหน่งที่ถูกต้องหลังจากแต่ละรอบการทำซ้ำ (iteration) ในอาร์เรย์

ในคู่มือนี้ เราจะพูดถึง Insertion sort คืออะไร ואיך มันทำงาน เราจะอธิบายการนำ Insertion sort ไปใช้ใน Python พร้อมตัวอย่าง เพื่อให้คุณเริ่มต้นกับอัลกอริทึมการจัดเรียงนี้ได้

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

Insertion sort แบ่งลิสต์ออกเป็นสองสับลิสต์ (sublist): sorted และ unsorted จากนั้นเปรียบเทียบแต่ละองค์ประกอบในลิสต์ unsorted และทำต่อไปจนกว่าทุกรายการในลิสต์จะถูกจัดเรียง

อัลกอริทึม Insertion sort ย้ายรายการที่จัดเรียงแล้วเข้าไปในสับลิสต์ sorted และนำออกจากสับลิสต์ unsorted ทั้งสองสับลิสต์เป็นส่วนหนึ่งของอาร์เรย์เดียวกัน แต่อย่างไรก็ตาม พวกมันแยกแยะว่ารายการไหนจัดเรียงแล้ว

คุณสามารถคิดถึง Insertion sorts เหมือนการจัดเรียงชุดไพ่ในมือในเกมไพ่

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

Insertion Sort ใน Python ทำงานอย่างไร?

มาลงมือจัดเรียงอาร์เรย์ด้วยอัลกอริทึม Insertion sort พิจารณาอาร์เรย์ที่ยังไม่จัดเรียง:

ใน Insertion sort องค์ประกอบแรกถือว่าจัดเรียงแล้ว องค์ประกอบที่สองเก็บในตัวแปรของตัวเอง เราจะเรียกตัวแปรนี้ว่า current_number

เราต้องเปรียบเทียบ current_number กับรายการที่ตำแหน่งแรกในอาร์เรย์ หาก current_number มากกว่าองค์ประกอบแรก มันจะอยู่ที่เดิม มิฉะนั้น current_number จะถูกย้ายไปหน้าองค์ประกอบแรก

4 ไม่มากกว่า 9 ดังนั้นสององค์ประกอบนี้สลับตำแหน่งกัน

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

current_number ของเรากลายเป็น 3 เราต้องเปรียบเทียบ:

• 3 มากกว่า 9 หรือไม่? ไม่ ดังนั้น 3 ถูกแทรกก่อน 9
• 3 มากกว่า 4 หรือไม่? ไม่ ดังนั้น 3 ถูกย้ายก่อน 4

ลิสต์ของเราตอนนี้เป็น:

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

• 5 มากกว่า 9 หรือไม่? ไม่ ดังนั้น 5 ย้ายก่อน 9

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

แค่นั้นแหละ! ใน Insertion sort ของเรา เราเก็บค่าที่จัดเรียงแล้วไว้ด้านซ้ายของลิสต์ ค่าที่ยังไม่จัดเรียงปรากฏด้านขวา

สำหรับแต่ละรอบในลิสต์ เราเปรียบเทียบ current_number กับรายการที่ยังไม่จัดเรียงทั้งหมด กระบวนการนี้ซ้ำจนกว่าลิสต์จะจัดเรียงแล้ว

วิธีเขียน Insertion Sort ใน Python

การเดินผ่าน Insertion sort บนกระดาษแล้วคราวนี้ถึงเวลาเข้าไปในรายละเอียดและนำ Insertion sort มาใช้ใน Python

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

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

def sortNumbers(toSort):
    for number in range(1, len(toSort)):
        current_number = toSort[number]
        i = number - 1
        while i >= 0 and current_number < toSort[i]:
            toSort[i + 1] = toSort[i]
            i -= 1
        toSort[i + 1] = current_number

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

เราวนผ่านทุกรายการในลิสต์ Python unsorted (ทุกรายการหลัง current_number) จากนั้นเปรียบเทียบ current_number กับตัวเลขแต่ละตัวทางซ้ายมือ หลังจากนั้นตั้งค่า current_number เท่ากับองค์ประกอบถัดไปในลิสต์

เขียนโปรแกรมหลัก (Main Program)

เราต้องเขียนโปรแกรมหลักที่รัน Insertion sort:

numbers = [9, 4, 3, 5]
sortNumbers(numbers)
print(numbers)

โค้ดคืนค่า:

[3, 4, 5, 9]

ลิสต์ของเราถูกจัดเรียงในลำดับน้อยไปมาก (ascending order) ยินดีด้วย!

Insertion Sort ใน Python: ลำดับมากไปน้อย (Descending Order)

Insertion sort สามารถจัดเรียงตัวเลขในลำดับมากไปน้อยได้ เพื่อทำเช่นนี้ ต้องกลับเครื่องหมาย "น้อยกว่า" (<) ในลูป while ให้เป็นเครื่องหมาย "มากกว่า" (>):

while i >= 0 and current_number > toSort[i]:

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

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

Insertion sort เหมาะสำหรับกรณีที่ข้อมูลในลิสต์ใกล้เคียงกับการจัดเรียงแล้ว (nearly sorted) หรือเมื่อจัดเรียงลิสต์ขนาดเล็ก มีอัลกอริทึมที่มีประสิทธิภาพมากกว่าสำหรับลิสต์ขนาดใหญ่ เช่น merge sort หรือ quick sort

Insertion sort เร็วกว่า Bubble sort

Insertion sort ยังมีประโยชน์ในการเรียนรู้ เพราะทำให้คุณรู้จักอีกประเภทหนึ่งของการจัดเรียง

Insertion sort ไม่ซับซ้อน כמו อัลกอริทึมจัดเรียงอื่นๆ เมื่อคุณเรียนรู้วิธีเขียน Insertion sort คุณก็ใกล้เคียงกับการเรียนรู้การจัดเรียงที่ซับซ้อนกว่า เช่น Merge sort

Insertion Sort ใน Python: การวิเคราะห์ความซับซ้อน (Complexity Analysis)

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

กรณีหย่าที่สุดและเฉลี่ย คือ O(n²) หมายความว่าอัลกอริทึมจะช้าลงแบบเอ็กซ์โพเนนเชียลเมื่อเพิ่มค่าที่ต้องจัดเรียงในลิสต์

กรณีดีที่สุด คือ O(n) เกิดขึ้นเมื่อรันอัลกอริทึมบนลิสต์ที่จัดเรียงแล้ว อัลกอริทึมตรวจสอบว่ารายการจัดเรียงแล้ว แล้วหยุดทำงาน

เรียนรู้เพิ่มเติมเกี่ยวกับการแทนความซับซ้อนของอัลกอริทึมในซีรีส์สองส่วนของเราเกี่ยวกับ Big O Notation

สรุป

Insertion sorts เหมือนการจัดเรียงชุดไพ่ในมือในเกมไพ่ คุณเก็บสองลิสต์: ลิสต์รายการที่จัดเรียงแล้ว และลิสต์รายการที่ต้องจัดเรียง จากนั้นคุณทำงานผ่านลิสต์รายการที่ยังไม่จัดเรียงและสลับตำแหน่งจนกว่าจะจัดเรียงหมด

กำลังมองหาแหล่งทรัพยากร Python เพิ่มเติม? ดูคู่มือ How to Learn Python ของเรา จะพบทีปส์ชั้นนำและรายการคอร์สออนไลน์ หนังสือ และแหล่งทรัพยากรอื่นๆ