อัลกอริทึมการเรียงลำดับ
จากวิกิพีเดีย สารานุกรมเสรี
ในวิทยาการคอมพิวเตอร์ อัลกอริทึมการเรียงลำดับ (sorting algorithm) คือ อัลกอริทึมที่จัดเรียงสมาชิกของรายการ (list) ให้เป็นไปตามรูปแบบของอันดับที่กำหนด ส่วนใหญ่อันดับที่ใช้กันคือ อันดับตัวเลข และอันดับตัวอักษร การเรียงลำดับที่มีประสิทธิภาพมีความสำคัญต่ออัลกอริทึมอื่นๆ (เช่น อัลกอริทึมการค้นหา และ การผสาน) ซึ่งอัลกอริทึมเหล่านี้ต้องใช้รายการที่เรียงอย่างถูกต้อง
สารบัญ |
[แก้] ประเภทของการเรียง
อัลกอริทึมการเรียงลำดับที่ใช้ในวิทยาการคอมพิวเตอร์ จำแนกประเภทได้ตามนี้
- ความซับซ้อนในการคำนวณ (กรณีแย่สุด, กรณีเฉลี่ย และกรณีดีสุด) ในรูปของขนาดของรายการ (n) โดยทั่วไป กรณีที่ดีจะเป็น O(n log n) และกรณีที่แย่จะเป็น Ω(n2) อัลกอริทึมการเรียงที่ใช้การเปรียบเทียบจะต้องใช้การเปรียบเทียบอย่างน้อย Ω(n log n) ครั้งโดยเฉลี่ย
- การใช้หน่วยความจำ (และทรัพยากรต่างๆของคอมพิวเตอร์)
- ความเสถียร (stability): อัลกอริทึมการเรียงที่เสถียร จะรักษาอันดับของเรคอร์ดที่มีคีย์เท่ากัน (มีค่าเท่ากัน) นั่นคือ อัลกอริทึมการเรียงลำดับจะ เสถียร ก็ต่อเมื่อ ถ้ามีเรคอร์ด R และ S ซึ่งมีคีย์เท่ากัน และ R ปรากฏอยู่ก่อน S ในรายการเริ่มต้นแล้ว R จะปรากฏอยู่ก่อน S ในรายการที่เรียงแล้วด้วย
- วิธีที่ใช้: การแทรก, การสับเปลี่ยน, การเลือก, การรวม ฯลฯ การเรียงแบบสับเปลี่ยน รวมถึง การเรียงแบบฟอง และการเรียงแบบเร็ว
ในกรณีที่มีสมาชิกที่มีคีย์เท่ากัน และไม่สามารถแยกแยะได้ เช่น รายการของจำนวนเต็ม มันจะไม่ส่งผลต่อความเสถียร อย่างไรก็ตาม คู่อันดับของจำนวนเต็มดังต่อไปนี้ จะถูกเรียงโดยสมาชิกตัวหน้าของมัน:
(4, 1) (3, 1) (3, 7) (5, 6)
ในกรณีนี้ จะให้ผลลัพธ์ได้สองแบบ แบบแรกจะรักษาอันดับของเรคอร์ดซึ่งมีคีย์เท่ากัน แต่อีกแบบจะไม่รักษาอันดับ:
(3, 1) (3, 7) (4, 1) (5, 6) (รักษาอันดับ) (3, 7) (3, 1) (4, 1) (5, 6) (อันดับเปลี่ยนแปลง)
การเรียงแบบไม่เสถียรอาจเปลี่ยนอันดับของเรคอร์ดที่มีคีย์เท่ากันได้ แต่การเรียงแบบเสถียรจะไม่เปลี่ยน เราอาจใช้การเรียงแบบไม่เสถียรในการเรียงลำดับให้เสถียรได้ โดยการใช้วิธีการเทียบคีย์แบบใหม่ เมื่อเราทำการเปรียบเทียบเรคอร์ด 2 เรคอร์ดที่มีคีย์เท่ากัน เราจะใช้อันดับของเรคอร์ดเป็นตัวตัดสิน อย่างไรก็ตาม มันต้องใช้หน่วยความจำมากขึ้น
[แก้] อัลกอริทึมการเรียง
ในตารางนี้ n คือจำนวนของเรคอร์ดที่จะนำมาจัดเรียง
[แก้] การเรียงแบบเสถียร
- การเรียงแบบฟอง (Bubble sort) — O(n2)
- การเรียงแบบแทรก (Insertion sort) — O(n2)
- การเรียงแบบผสาน — O(n log n); และต้องใช้หน่วยความจำ O(n)
[แก้] การเรียงแบบไม่เสถียร
- การเรียงแบบเลือก (Selection sort) — O(n2)
