ขั้นตอนวิธีการเรียงลำดับ

ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีการเรียงลำดับ (sorting algorithm) คือ ขั้นตอนวิธีที่จัดเรียงสมาชิกของรายการ (list) ให้เป็นไปตามรูปแบบของอันดับที่กำหนด ส่วนใหญ่อันดับที่ใช้กันคือ อันดับตัวเลข และอันดับตัวอักษร การเรียงลำดับที่มีประสิทธิภาพมีความสำคัญต่อขั้นตอนวิธีอื่นๆ (เช่น ขั้นตอนวิธีการค้นหา และ การผสาน) ซึ่งขั้นตอนวิธีเหล่านี้ต้องใช้รายการที่เรียงอย่างถูกต้อง
== ประเภทของการเรียง ==
ขั้นตอนวิธีการเรียงลำดับที่ใช้ในวิทยาการคอมพิวเตอร์ จำแนกประเภทได้ตามนี้
ความซับซ้อนในการคำนวณ (กรณีแย่สุด, กรณีเฉลี่ย และกรณีดีสุด) ในรูปของขนาดของรายการ (n) โดยทั่วไป กรณีที่ดีจะเป็น O(n&nbsp;log&nbsp;n) และกรณีที่แย่จะเป็น Ω(n2) ขั้นตอนวิธีการเรียงที่ใช้การเปรียบเทียบจะต้องใช้การเปรียบเทียบอย่างน้อย Ω(n&nbsp;log&nbsp;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)
การเรียงลำดับแบบผสาน (Merge sort) — O(n log n); และต้องใช้หน่วยความจำ O(n)
=== การเรียงแบบไม่เสถียร ===
การเรียงลำดับแบบเลือก (Selection sort) — O(n2)
== เชิงเปรียบเทียบ ==
{|class="wikitable sortable"
|+ ขั้นตอนวิธีการเรียงลำดับแบบอาศัยการเปรียบเทียบ
! ชื่อ !! กรณีดีที่สุด !! กรณีทั่วไป !! กรณีแย่ที่สุด !! การใช้หน่วยความจำ !! เสถียร
|- align = "center"
| การเรียงลำดับแบบเร็ว
| style="background:#ddffdd"|
| style="background:#ddffdd"|
| style="background:#ffdddd"|
| style="background:#ffffdd"|
| style="background:#ffffdd"|
|- align = "center"
| การเรียงลำดับแบบผสาน
| style="background:#ddffdd"|
| style="background:#ddffdd"|
| style="background:#ddffdd"|
| style="background:#ffdddd"|
| style="background:#ddffdd"| ใช่
|- align = "center"
| การเรียงลำดับแบบฮีป
| style="background:#ddffdd"|
| style="background:#ddffdd"|
| style="background:#ddffdd"|
| style="background:#ddffdd"|
| style="background:#ffdddd"| ไม่
|- align = "center"
| การเรียงลำดับแบบแทรก
| style="background:#ddffdd"|
| style="background:#ffdddd"|
| style="background:#ffdddd"|
| style="background:#ddffdd"|
| style="background:#ddffdd"| ใช่
|- align = "center"
| การเรียงลำดับแบบเลือก
| style="background:#ffdddd"|
| style="background:#ffdddd"|
| style="background:#ffdddd"|
| style="background:#ddffdd"|
| style="background:#ffffdd"| ไม่
|- align = "center"
| การเรียงลำดับแบบฟอง
| style="background:#ddffdd"|
| style="background:#ffdddd"|
| style="background:#ffdddd"|
| style="background:#ddffdd"|
| style="background:#ddffdd"| ใช่
|- align = "center"
| การเรียงลำดับด้วยต้นไม้ค้นหาแบบทวิภาค
| style="background:#ddffdd"|
| style="background:#ddffdd"|
| style="background:#ddffdd"|
| style="background:#ffdddd"|
| style="background:#ddffdd"| ใช่
|- align = "center"
|}
== ดูเพิ่ม ==
สัญกรณ์โอใหญ่
ขั้นตอนวิธีการเรียงลำดับ