การเรียงลำดับการแทรก Python ทำงานเหมือนกับการเรียงลำดับการ์ดเกม ในการใช้การเรียงลำดับการแทรก คุณต้องสร้างสองรายการ:รายการที่เรียงลำดับและไม่มีการเรียงลำดับ คุณเปรียบเทียบแต่ละรายการในรายการที่ไม่ได้เรียงลำดับจนกว่าคุณจะเรียงลำดับรายการนั้น การเรียงลำดับการแทรกเป็นอัลกอริธึมมาตรฐานทั่วไปในภาษา Python
คุณเคยเรียงลำดับไพ่ในมือของคุณหรือไม่? นั่นเป็นวิธีหนึ่งในการคิดเกี่ยวกับแนวคิดของการเรียงลำดับการแทรก Python เมื่อคุณต้องการจัดเรียงรายการที่มีองค์ประกอบเพียงไม่กี่อย่าง การจัดเรียงการแทรกจะช่วยได้
การเรียงลำดับการแทรกจะวางองค์ประกอบที่ไม่ได้เรียงลำดับในตำแหน่งที่ถูกต้องหลังจากการวนซ้ำแต่ละครั้งในอาร์เรย์
ในคู่มือนี้ เราจะพูดถึงประเภทของการแทรกและวิธีการทำงาน เราจะพูดถึงวิธีการใช้การเรียงลำดับการแทรกใน Python โดยอ้างอิงจากตัวอย่าง คุณจึงสามารถเริ่มต้นใช้งานอัลกอริทึมการจัดเรียงนี้ได้
การเรียงลำดับการแทรก Python คืออะไร
การเรียงลำดับการแทรกแบ่งรายการออกเป็นสองรายการย่อย:เรียงลำดับและไม่เรียงลำดับ จากนั้นจะเปรียบเทียบแต่ละองค์ประกอบในรายการที่ไม่ได้เรียงลำดับและดำเนินการต่อไปจนกว่าแต่ละรายการในรายการจะถูกจัดเรียง
อัลกอริธึมการเรียงลำดับการแทรกจะย้ายรายการที่เรียงลำดับไปยังรายการย่อยที่เรียงลำดับแล้ว และลบออกจากรายการย่อยที่ไม่ได้เรียงลำดับ รายการย่อยทั้งสองเป็นส่วนหนึ่งของอาร์เรย์เดียวกัน แต่จะแยกแยะว่ารายการถูกจัดเรียงหรือไม่
คุณสามารถนึกถึงการแทรกแบบต่างๆ เช่น วิธีจัดเรียงไพ่ในมือของคุณในเกมไพ่
คุณต้องย้ายทีละรายการผ่านรายการการ์ดและเปรียบเทียบการ์ดแต่ละใบ การ์ดที่เรียงแล้วจะปรากฏทางด้านซ้ายมือของคุณ การ์ดที่ไม่ได้เรียงลำดับจะปรากฏทางด้านขวาจนกว่าคุณจะจัดเรียงทั้งหมด
81% ของผู้เข้าร่วมกล่าวว่าพวกเขารู้สึกมั่นใจมากขึ้นเกี่ยวกับโอกาสในการทำงานด้านเทคโนโลยีหลังจากเข้าร่วม bootcamp จับคู่กับ Bootcamp วันนี้
ผู้สำเร็จการศึกษาจากหลักสูตร bootcamp โดยเฉลี่ยใช้เวลาน้อยกว่าหกเดือนในการเปลี่ยนอาชีพ ตั้งแต่เริ่มต้น bootcamp ไปจนถึงหางานแรก
การเรียงลำดับการแทรก Python ทำงานอย่างไร
มาลงมือทำธุรกิจและจัดเรียงอาร์เรย์โดยใช้อัลกอริธึมการจัดเรียงการแทรก พิจารณาอาร์เรย์ที่ไม่เรียงลำดับต่อไปนี้:
| 9 | 4 | 3 | 5 |
ในการเรียงลำดับการแทรก องค์ประกอบแรกจะถือว่าเป็นการเรียงลำดับ องค์ประกอบที่สองถูกเก็บไว้ในตัวแปรของตัวเอง เราจะเรียกตัวแปรนี้ว่า current_number .
| จัดเรียงแล้ว | current_number | | |
| 9 | 4 | 3 | 5 |
เราต้องเปรียบเทียบ current_number โดยมีรายการอยู่ที่ตำแหน่งแรกในอาร์เรย์ ถ้า current_number มากกว่าองค์ประกอบแรกจะอยู่ในที่เดียวกัน มิฉะนั้น current_number จะถูกย้ายไปที่ด้านหน้าขององค์ประกอบแรก
4 ไม่เกิน 9 ดังนั้นองค์ประกอบทั้งสองนี้จึงสลับตำแหน่งกัน
| 4 | 9 | 3 | 5 |
สององค์ประกอบแรกในรายการของเราถูกจัดเรียง ต่อไป เราเปลี่ยนค่าของ current_number เป็นรายการที่สามในรายการและเปรียบเทียบกับรายการทั้งหมดทางด้านซ้าย
current_number ของเรากลายเป็น 3 เราต้องเปรียบเทียบ:
- 3 มากกว่า 9 หรือไม่? ไม่ ดังนั้น 3 จะถูกแทรกก่อน 9
- 3 มากกว่า 4 หรือไม่? ไม่ ดังนั้น 3 จะถูกย้ายก่อน 4
รายการของเราตอนนี้มีลักษณะดังนี้:
| 3 | 4 | 9 | 5 |
กระบวนการนี้จะเกิดขึ้นซ้ำๆ จนกว่าจะจัดเรียงรายการ รายการของเรามีการเปรียบเทียบที่จะดำเนินการอีกชุดเดียวเท่านั้น เนื่องจากมีสี่ค่าเท่านั้น ในการทำซ้ำครั้งต่อไป 5 จะกลายเป็น current_number
- 5 มากกว่า 9 หรือไม่? ไม่สิ 5 ท่าก่อน 9
ถูกนำมาใช้ tไม่มีการเปรียบเทียบอีกต่อไปเพราะ 5 เป็นตัวเลขสุดท้ายในรายการที่เราจัดเรียง หลังจากการวนซ้ำนี้ อาร์เรย์ของเราได้รับการจัดเรียง:
| 3 | 4 | 5 | 9 |
มันง่ายมาก! ในการเรียงลำดับการแทรก เราเก็บค่าที่จัดเรียงไว้ทางด้านซ้ายของรายการเสมอ ค่าที่ไม่เรียงลำดับปรากฏทางด้านขวา
สำหรับการวนซ้ำแต่ละรายการในรายการ เราเปรียบเทียบ current_number กับรายการที่ไม่เรียงลำดับทั้งหมด กระบวนการนี้ซ้ำๆ จนกว่ารายการของเราจะถูกจัดเรียง
วิธีการเขียนการเรียงลำดับการแทรกใน Python
ทุกอย่างเรียบร้อยดีและผ่านการจัดเรียงการแทรกบนกระดาษอย่างดี ตอนนี้ได้เวลาเข้าสู่ nitty-gritty และใช้การเรียงลำดับการแทรกใน 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 . ของเรา ฟังก์ชั่น เราสร้าง Python for loop ซึ่งวนซ้ำทุกหมายเลขในรายการ จากนั้น เราตั้งค่าองค์ประกอบแรกในรายการเป็นค่าที่จัดเรียงโดยกำหนดให้กับตัวแปร Python current_number .
เราวนซ้ำทุกรายการในรายการ Python ที่ไม่ได้เรียงลำดับ (ทุกรายการหลัง current_number) จากนั้น เราเปรียบเทียบ current_number กับตัวเลขแต่ละตัวทางด้านซ้าย หลังจากสิ่งนี้เกิดขึ้น เราตั้งค่า current_number ให้เท่ากับองค์ประกอบตามหลังในรายการ
เขียนโปรแกรมหลัก
เราต้องเขียนโปรแกรมหลักที่รันการเรียงลำดับการแทรกของเรา:
numbers = [9, 4, 3, 5] sortNumbers(numbers) print(numbers)
รหัสของเราส่งคืน:
[3, 4, 5, 9]
รายการของเราได้รับการเรียงลำดับจากน้อยไปมาก! ยินดีด้วยที่มาถึงจุดนี้ได้
การเรียงลำดับการแทรก Python:ลำดับจากมากไปน้อย
การเรียงลำดับการแทรกสามารถเรียงลำดับตัวเลขจากมากไปหาน้อยได้ ในการทำสิ่งนี้ให้สำเร็จ คุณต้องกลับเครื่องหมาย “น้อยกว่า” (>) ในลูป while และทำให้เป็นเครื่องหมายมากกว่า:
ในขณะที่ i>=0 และ current_number> toSort[i]:
โค้ดบรรทัดนี้ แทนที่ในตัวอย่างข้างต้นของเราจะเรียงลำดับรายการในลำดับที่กลับกัน
คุณควรใช้การเรียงลำดับการแทรกเมื่อใด
การเรียงลำดับการแทรกจะใช้ได้ดีที่สุดเมื่อข้อมูลในรายการเกือบจะถูกจัดเรียง หรือเมื่อคุณกำลังเรียงลำดับรายการขนาดเล็ก มีอัลกอริธึมที่มีประสิทธิภาพมากกว่าที่คุณสามารถใช้เพื่อจัดเรียงรายการขนาดใหญ่ได้ ตัวอย่างเช่น การจัดเรียงแบบรวมหรือการเรียงลำดับแบบรวดเร็วนั้นเร็วกว่า
การเรียงลำดับการแทรกนั้นเร็วกว่าการเรียงลำดับแบบฟอง
การเรียงลำดับการแทรกมีประโยชน์ในการรู้อยู่แล้ว การรู้วิธีใช้งานการเรียงลำดับการแทรกจะทำให้คุณมีอีกประเภทหนึ่งที่คุณสามารถใช้ได้
การเรียงลำดับการแทรกนั้นซับซ้อนน้อยกว่าอัลกอริธึมการเรียงลำดับอื่นๆ เมื่อคุณได้เรียนรู้วิธีเขียนการเรียงลำดับการแทรกแล้ว คุณจะใกล้ชิดกับการเรียนรู้เกี่ยวกับการจัดเรียงที่ซับซ้อนมากขึ้น เช่น การเรียงลำดับการผสาน
การเรียงลำดับการแทรก Python:การวิเคราะห์ความซับซ้อน
เช่นเดียวกับอัลกอริธึมทั้งหมด การพิจารณาความซับซ้อนที่ดีที่สุด แย่ที่สุด และปานกลางเป็นสิ่งสำคัญ ข้อมูลนี้จะช่วยให้เราเข้าใจถึงประสิทธิภาพของอัลกอริธึมในการทำงาน:ในกรณีนี้คือการจัดเรียงรายการ
กรณีที่เลวร้ายที่สุดและความซับซ้อนโดยเฉลี่ยคือ O(n2) ซึ่งหมายความว่าอัลกอริทึมจะเติบโตช้าลงแบบทวีคูณเมื่อคุณเพิ่มค่าเพื่อจัดเรียงในรายการของคุณมากขึ้น
กรณีที่ดีที่สุดคือ O(n) สิ่งนี้จะเกิดขึ้นเมื่อเรารันอัลกอริธึมในรายการที่เรียงลำดับ อัลกอริธึมจะตรวจสอบว่ารายการถูกจัดเรียงแล้วหยุดทำงาน
คุณสามารถเรียนรู้เพิ่มเติมเกี่ยวกับวิธีที่เราแสดงความซับซ้อนของอัลกอริทึมในชุดสองส่วนของเราใน Big O Notation
บทสรุป
การเรียงลำดับการแทรกเป็นเหมือนการเรียงลำดับรายการไพ่ในมือของคุณในเกมไพ่ คุณเก็บสองรายการ:รายการของรายการที่เรียงลำดับและรายการของรายการที่จะเรียงลำดับ จากนั้น ให้คุณดำเนินการตามรายการของรายการที่ยังไม่ได้จัดเรียง และสับเปลี่ยนตำแหน่งจนกว่าจะจัดเรียงทั้งหมด
คุณกำลังมองหาแหล่งข้อมูลภาษาการเขียนโปรแกรม Python เพิ่มเติมหรือไม่? ดูคู่มือ How to Learn Python ฉบับสมบูรณ์ของเรา คุณจะพบเคล็ดลับยอดนิยมเกี่ยวกับวิธีการเรียนรู้ Python และรายชื่อหลักสูตรออนไลน์ หนังสือ และแหล่งข้อมูลอื่นๆ
