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