ความแตกต่างระหว่าง Bubble Sort และ Sort Selection

• 2019

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

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

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

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

ความหมายของ Bubble Sort

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

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

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

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

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

ความแตกต่างที่สำคัญระหว่างการเรียงลำดับฟองและการเรียงลำดับการเลือก

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

ข้อสรุป

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