การเรียงฟองและการแทรก
Bubble sort เป็นอัลกอริธึมการจัดเรียงที่ทำงานโดยผ่านรายการเพื่อจัดเรียงซ้ำๆ ขณะเปรียบเทียบคู่ขององค์ประกอบที่อยู่ติดกัน หากคู่ขององค์ประกอบอยู่ในลำดับที่ไม่ถูกต้อง พวกมันจะถูกสลับเพื่อจัดวางในลำดับที่ถูกต้อง การข้ามผ่านนี้จะทำซ้ำจนกว่าจะไม่มีการสลับเพิ่มเติม การเรียงลำดับการแทรกยังเป็นอัลกอริธึมการเรียงลำดับ ซึ่งทำงานโดยการแทรกองค์ประกอบในรายการอินพุตในตำแหน่งที่ถูกต้องในรายการที่จัดเรียงแล้ว กระบวนการนี้ถูกนำไปใช้ซ้ำๆ จนกว่าจะจัดเรียงรายการ
Bubble Sort คืออะไร
Bubble sort เป็นอัลกอริธึมการจัดเรียงที่ทำงานโดยผ่านรายการเพื่อจัดเรียงซ้ำๆ ขณะเปรียบเทียบคู่ขององค์ประกอบที่อยู่ติดกัน หากองค์ประกอบคู่หนึ่งอยู่ในลำดับที่ไม่ถูกต้อง พวกมันจะถูกสลับเพื่อจัดวางในลำดับที่ถูกต้อง การข้ามผ่านนี้จะทำซ้ำจนกว่าจะไม่มีการสลับเพิ่มเติม (ซึ่งหมายความว่ารายการถูกจัดเรียง) เนื่องจากองค์ประกอบที่เล็กกว่าในรายการมาที่ด้านบนเมื่อฟองมาถึงพื้นผิว มันจึงตั้งชื่อการเรียงลำดับฟอง Bubble sort เป็นอัลกอริธึมการเรียงลำดับที่ง่ายมาก แต่มีความซับซ้อนของเวลาเฉลี่ยของ O(n2) เมื่อเรียงลำดับรายการที่มี n องค์ประกอบ ด้วยเหตุนี้ การเรียงลำดับแบบฟองจึงไม่เหมาะสำหรับการจัดเรียงรายการที่มีองค์ประกอบจำนวนมาก แต่เนื่องจากความเรียบง่าย การจัดเรียงแบบฟองสบู่จึงได้รับการสอนในระหว่างการแนะนำอัลกอริทึม
การจัดเรียงการแทรกคืออะไร
Insertion sort เป็นอัลกอริธึมการจัดเรียงอื่นซึ่งทำงานโดยการแทรกองค์ประกอบในรายการอินพุตในตำแหน่งที่ถูกต้องในรายการ (ที่จัดเรียงแล้ว)กระบวนการนี้ถูกนำไปใช้ซ้ำๆ จนกว่าจะมีการเรียงลำดับรายการ ในการเรียงลำดับแบบแทรก การเรียงลำดับจะดำเนินการแบบแทนที่ ดังนั้นหลังจากการวนซ้ำของอัลกอริทึม รายการ i+1 รายการแรกในรายการจะถูกจัดเรียงและรายการที่เหลือจะไม่ถูกจัดเรียง ในการทำซ้ำแต่ละครั้ง องค์ประกอบแรกในส่วนที่ไม่เรียงลำดับของรายการจะถูกนำและแทรกลงในตำแหน่งที่ถูกต้องในส่วนที่จัดเรียงของรายการ การเรียงลำดับการแทรกมีความซับซ้อนของเวลากรณีเฉลี่ย O(n2) ด้วยเหตุนี้ การเรียงลำดับการแทรกจึงไม่เหมาะสำหรับการจัดเรียงรายการขนาดใหญ่
Bubble Sort และ Insertion Sort ต่างกันอย่างไร
แม้ว่าอัลกอริธึมการเรียงลำดับแบบฟองและการเรียงลำดับการแทรกจะมีความซับซ้อนของเวลากรณีเฉลี่ยของ O(n2) แต่การเรียงลำดับแบบฟองนั้นมักจะทำได้ดีกว่าการจัดเรียงการแทรกเกือบตลอดเวลา นี่เป็นเพราะจำนวนของการสลับที่อัลกอริธึมทั้งสองต้องการ (การเรียงลำดับฟองต้องการการสลับเพิ่มเติม) แต่เนื่องจากความเรียบง่ายของการจัดเรียงแบบฟอง ขนาดของโค้ดจึงเล็กมากนอกจากนี้ยังมีการเรียงลำดับการแทรกแบบต่างๆ ที่เรียกว่าการเรียงลำดับเชลล์ ซึ่งมีความซับซ้อนของเวลาเป็น O(n3/2) ซึ่งจะทำให้สามารถใช้งานได้จริง นอกจากนี้ การเรียงลำดับการแทรกยังมีประสิทธิภาพมากสำหรับการจัดเรียงรายการ "เกือบจัดเรียง" เมื่อเปรียบเทียบกับการเรียงลำดับแบบฟอง
