สารบัญ[ซ่อน][แสดง]
วิทยาการคอมพิวเตอร์เป็นเรื่องเกี่ยวกับการทำความเข้าใจความซับซ้อนของอัลกอริทึมและโครงสร้างข้อมูล
คุณมีรายการสิ่งของที่ต้องจัดเรียง แต่คุณไม่มีเวลาหรือทรัพยากรที่จะใช้อัลกอริธึมการเรียงลำดับที่ซับซ้อนกว่านี้
การเรียงลำดับการแทรกเป็นหนึ่งในอัลกอริธึมการเรียงลำดับที่ง่ายที่สุด แต่อาจช้าสำหรับรายการขนาดใหญ่
การใช้งานและความเข้าใจที่ง่ายดายทำให้วิธีการนี้เป็นที่ชื่นชอบในหมู่โปรแกรมเมอร์ เหมาะอย่างยิ่งสำหรับรายการเล็กๆ หรือเมื่อคุณต้องการวิธีแก้ปัญหาอย่างรวดเร็ว
ในบล็อกโพสต์นี้ เราจะพิจารณาความซับซ้อนของเวลาในการจัดเรียงการแทรก อัลกอริทึมนี้ใช้เพื่อจัดเรียงอาร์เรย์ และมีรันไทม์ของ O(n2). ซึ่งหมายความว่าความซับซ้อนของเวลาจะเพิ่มขึ้นตามขนาดของอาร์เรย์
อย่างไรก็ตาม อัลกอริธึมนี้อาจเร็วกว่าอัลกอริธึมการจัดเรียงอื่นๆ เช่น Quicksort
มาดูกันดีกว่าว่าการเรียงลำดับการแทรกทำงานอย่างไร!
อัลกอริธึมการเรียงลำดับการแทรกคืออะไร?
องค์ประกอบทีละรายการ การเรียงลำดับการแทรกจะสร้างอาร์เรย์ที่จัดเรียงได้ ซึ่งมักเรียกว่าเป็นรายการ
ตัวอย่างเช่น การเรียงลำดับถูกนำมาใช้ในโปรแกรมคอมพิวเตอร์ที่ซับซ้อน เช่น คอมไพเลอร์ โดยที่ลำดับของโทเค็นมีความสำคัญต่อการตีความโปรแกรม
การเรียงลำดับการแทรกทำงานอย่างไร
เมื่อเราใช้การเรียงลำดับการแทรกเพื่อจัดเรียงอาร์เรย์ อัลกอริธึมจะเริ่มต้นด้วยการค้นหารายการที่เล็กที่สุดในรายการและแทรกลงในตำแหน่งที่ถูกต้อง
จากนั้นจะค้นหารายการที่เล็กที่สุดถัดไปและแทรกลงในตำแหน่งที่ถูกต้อง เป็นต้น
อัลกอริธึมทำงานโดยวนซ้ำในรายการ เปรียบเทียบแต่ละรายการกับรายการที่มาก่อน
หากรายการอยู่ในลำดับที่ไม่ถูกต้อง อัลกอริธึมจะสลับรายการเหล่านั้น จากนั้นจะตรวจสอบเพื่อดูว่ามีการจัดเรียงรายการหรือไม่ และหากเป็นเช่นนั้น อัลกอริทึมจะสิ้นสุด
ในทางปฏิบัติ การเรียงลำดับการแทรกมักใช้โค้ดสองสามบรรทัด ทำให้เป็นตัวเลือกยอดนิยมสำหรับการจัดเรียงอาร์เรย์ขนาดเล็ก อย่างไรก็ตาม ควรพิจารณาความซับซ้อนของเวลาเมื่อใช้อัลกอริทึมนี้
ตัวอย่าง:
นี่คือตัวอย่างการทำงานของการเรียงลำดับการแทรก เราจะใช้อาร์เรย์ต่อไปนี้:
1, 2, 3, 4, 5, 6
อัลกอริทึมเริ่มต้นด้วยการค้นหารายการที่เล็กที่สุดในรายการ ซึ่งก็คือ 1 จากนั้นแทรกลงในตำแหน่งที่ถูกต้อง ตำแหน่งแรก จากนั้นจะพบรายการที่เล็กที่สุดถัดไป ซึ่งก็คือ 2 ซึ่งแทรกลงในตำแหน่งที่ถูกต้อง ซึ่งเป็นตำแหน่งที่สอง
จากนั้นจะพบรายการที่เล็กที่สุดถัดไป ซึ่งก็คือ 3 แล้วจึงแทรกลงในตำแหน่งที่ถูกต้อง ซึ่งเป็นตำแหน่งที่สาม
จากนั้นจะพบรายการที่เล็กที่สุดถัดไป ซึ่งก็คือ 4 แล้วจึงแทรกลงในตำแหน่งที่ถูกต้อง ซึ่งก็คือตำแหน่งที่สี่ เป็นต้น รายชื่อเรียบร้อยแล้ว!
จากตัวอย่าง เราจะเห็นได้ว่าอัลกอริทึมใช้การเปรียบเทียบและสลับหกครั้งเพื่อจัดเรียงรายการ ทั้งนี้เป็นเพราะต้องใช้ n2 การเปรียบเทียบและสลับเพื่อจัดเรียงรายการ n รายการ ในกรณีนี้ n=6
จะปรับปรุงความซับซ้อนของเวลาในการจัดเรียงการแทรกได้อย่างไร
ในขณะที่การเรียงลำดับการแทรกมีรันไทม์ของ O(n2) สามารถปรับปรุงได้โดยใช้อัลกอริธึมการเรียงลำดับที่ดีกว่า เช่น Quicksort
Quicksort มีรันไทม์ O(n log n) ซึ่งเร็วกว่า O(n . มาก2).
อย่างไรก็ตาม ในบางกรณี การเรียงลำดับการแทรกอาจเร็วกว่าการเรียงลำดับอย่างรวดเร็ว
ตัวอย่างเช่น หากรายการอยู่ในลำดับแล้ว การเรียงลำดับการแทรกจะใช้เวลาน้อยกว่าการเรียงลำดับอย่างรวดเร็ว
ในทางปฏิบัติ การเรียงลำดับการแทรกมักใช้โค้ดสองสามบรรทัด ทำให้เป็นตัวเลือกยอดนิยมสำหรับการจัดเรียงอาร์เรย์ขนาดเล็ก
อย่างไรก็ตาม ควรพิจารณาความซับซ้อนของเวลาเมื่อใช้อัลกอริทึมนี้
ความซับซ้อนของเวลา
ความซับซ้อนของกรณีที่เลวร้ายที่สุด O(n2):
ความซับซ้อนของเวลาจะเพิ่มขึ้นตามขนาดของอาร์เรย์ มันต้องใช้เวลา n2 การเปรียบเทียบและสลับเพื่อจัดเรียงรายการ n รายการ
ตัวอย่างเช่น ถ้าเรามีอาร์เรย์ขนาด 1000 อัลกอริธึมจะทำการเปรียบเทียบ 1,000,000 ครั้งและสลับเพื่อจัดเรียงอาร์เรย์
ความซับซ้อนของเคสที่ดีที่สุด O(n):
ความซับซ้อนของเวลาจะเท่ากับขนาดของอาร์เรย์อินพุต ฉัน
t ใช้การเปรียบเทียบและสลับ n รายการเพื่อจัดเรียงรายการ n รายการ ตัวอย่างเช่น พิจารณาอาร์เรย์ขนาด 5 อัลกอริทึมจะทำการเปรียบเทียบและสลับห้ารายการเพื่อจัดเรียงอาร์เรย์
ความซับซ้อนของเคสเฉลี่ย O(n2):
ความซับซ้อนของเวลาอยู่ระหว่างความซับซ้อนของกรณีที่เลวร้ายที่สุดและดีที่สุดในกรณีนี้
มันต้องใช้เวลา n2 การเปรียบเทียบและสลับเพื่อจัดเรียงรายการ n รายการ
ดังนั้น การเรียงลำดับการแทรกจึงเป็นอัลกอริธึมการเรียงลำดับที่เสถียร
เหตุใดการเรียงลำดับการแทรกจึงเสถียร
การเรียงลำดับการแทรกมีความเสถียรเนื่องจากจะรักษาลำดับขององค์ประกอบที่เท่ากันในอาร์เรย์อินพุต
นี่เป็นสิ่งสำคัญสำหรับแอปพลิเคชันจำนวนมาก เช่น การดึงข้อมูลหรือการวิเคราะห์ทางการเงิน ตัวอย่างเช่น หากเรามีรายการตัวเลขสองรายการและต้องการเปรียบเทียบ เราจำเป็นต้องตรวจสอบให้แน่ใจว่าได้รักษาลำดับขององค์ประกอบไว้
หากรายชื่อไม่ถูกจัดเรียง เราจะไม่เปรียบเทียบให้ถูกต้อง
เขียนความเห็น