เนื้อหา

• แผนภูมิเปรียบเทียบ
• นิยามของ Bubble Sort
• ความหมายของการเรียงลำดับการเลือก
• ข้อสรุป

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

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

1. แผนภูมิเปรียบเทียบ
2. คำนิยาม
3. ความแตกต่างที่สำคัญ
4. ข้อสรุป

แผนภูมิเปรียบเทียบ

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

นิยามของ Bubble Sort

เรียงลำดับฟอง เป็นอัลกอริธึมการวนซ้ำที่ง่ายที่สุดที่ดำเนินการโดยการเปรียบเทียบแต่ละรายการหรือองค์ประกอบกับรายการถัดจากมันและสลับมันหากจำเป็น ในคำง่าย ๆ มันจะเปรียบเทียบองค์ประกอบที่หนึ่งและสองของรายการและสลับมันเว้นแต่พวกเขาจะออกคำสั่งที่เฉพาะเจาะจง ในทำนองเดียวกันองค์ประกอบที่สองและสามจะถูกเปรียบเทียบและสลับสับเปลี่ยนและการเปรียบเทียบและการแลกเปลี่ยนนี้จะไปยังจุดสิ้นสุดของรายการ จำนวนการเปรียบเทียบในการคำนวณซ้ำครั้งแรกคือ n-1 โดยที่ n คือองค์ประกอบจำนวนในอาร์เรย์ องค์ประกอบที่ใหญ่ที่สุดจะอยู่ที่ตำแหน่งที่ n หลังจากการทำซ้ำครั้งแรก และหลังจากการทำซ้ำแต่ละครั้งจำนวนการเปรียบเทียบจะลดลงและในการทำซ้ำครั้งสุดท้ายจะมีการเปรียบเทียบเพียงครั้งเดียว

อัลกอริทึมนี้เป็นอัลกอริทึมการเรียงลำดับช้าที่สุด ความซับซ้อนของกรณีที่ดีที่สุด (เมื่อรายการอยู่ในลำดับ) ของการเรียงลำดับของฟองคือลำดับ n (บน)) และความซับซ้อนของกรณีที่เลวร้ายที่สุดคือ บน²). ในกรณีที่ดีที่สุดมันเป็นลำดับ n เพราะมันเพิ่งเปรียบเทียบองค์ประกอบและไม่สลับมัน เทคนิคนี้ยังต้องการพื้นที่เพิ่มเติมเพื่อเก็บตัวแปรชั่วคราว

ความหมายของการเรียงลำดับการเลือก

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

ในการเรียงลำดับการเลือกอาร์เรย์ที่เรียงและไม่เรียงลำดับจะไม่สร้างความแตกต่างและใช้คำสั่ง n² (บน²)) ทั้งในกรณีที่ซับซ้อนและดีที่สุด การเรียงลำดับการเลือกนั้นเร็วกว่าการจัดเรียงฟอง

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

ข้อสรุป

อัลกอริธึมการจัดเรียงฟองถือว่าเป็นอัลกอริทึมที่ง่ายที่สุดและไม่มีประสิทธิภาพ แต่อัลกอริทึมการเรียงลำดับการเลือกมีประสิทธิภาพเมื่อเทียบกับการจัดเรียงฟอง การเรียงลำดับฟองยังใช้พื้นที่เพิ่มเติมสำหรับการจัดเก็บตัวแปรชั่วคราวและต้องการแลกเปลี่ยนมากขึ้น