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

ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีการเรียงลำดับ (อังกฤษ: sorting algorithm) คือ ขั้นตอนวิธีที่จัดเรียงสมาชิกของรายการ (list) ให้เป็นไปตามรูปแบบของที่กำหนด ส่วนใหญ่อันดับที่ใช้กันคือ อันดับตัวเลข และ การเรียงลำดับที่มีประสิทธิภาพมีความสำคัญต่อขั้นตอนวิธีอื่นๆ (เช่น ขั้นตอนวิธีการค้นหา และ ) ซึ่งขั้นตอนวิธีเหล่านี้ต้องใช้รายการที่เรียงอย่างถูกต้อง

ประเภทของการเรียง

ขั้นตอนวิธีการเรียงลำดับที่ใช้ในวิทยาการคอมพิวเตอร์ จำแนกประเภทได้ตามนี้

• ความซับซ้อนในการคำนวณ (กรณีแย่สุด, กรณีเฉลี่ย และกรณีดีสุด) ในรูปของขนาดของรายการ (n) โดยทั่วไป กรณีที่ดีจะเป็น O(n log n) และกรณีที่แย่จะเป็น Ω(n²) ขั้นตอนวิธีการเรียงที่ใช้การเปรียบเทียบจะต้องใช้การเปรียบเทียบอย่างน้อย Ω(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(n²)
• การเรียงลำดับแบบแทรก (Insertion sort) — O(n²)
• การเรียงลำดับแบบผสาน (Merge sort) — O(n log n); และต้องใช้หน่วยความจำ O(n)

การเรียงแบบไม่เสถียร

• การเรียงลำดับแบบเลือก (Selection sort) — O(n²)

เชิงเปรียบเทียบ

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

ชื่อ	กรณีดีที่สุด	กรณีทั่วไป	กรณีแย่ที่สุด	การใช้หน่วยความจำ	เสถียร
	20 !${\displaystyle {\mathcal {}}n\log n}$	20 !${\displaystyle {\mathcal {}}n\log n}$	25 !${\displaystyle {\mathcal {}}n^{2}}$	05 !${\displaystyle {\mathcal {}}\log n}$
การเรียงลำดับแบบผสาน	20 !${\displaystyle {\mathcal {}}{n\log n}}$	20 !${\displaystyle {\mathcal {}}{n\log n}}$	20 !${\displaystyle {\mathcal {}}{n\log n}}$	15 !กรณีแย่ที่สุดคือ ${\displaystyle {\mathcal {}}n}$	ใช่
	20 !${\displaystyle {\mathcal {}}{n\log n}}$	20 !${\displaystyle {\mathcal {}}{n\log n}}$	20 !${\displaystyle {\mathcal {}}{n\log n}}$	00 !${\displaystyle {\mathcal {}}{1}}$	ไม่
การเรียงลำดับแบบแทรก	15 !${\displaystyle {\mathcal {}}n}$	25 !${\displaystyle {\mathcal {}}n^{2}}$	25 !${\displaystyle {\mathcal {}}n^{2}}$	00 !${\displaystyle {\mathcal {}}{1}}$	ใช่
การเรียงลำดับแบบเลือก	25 !${\displaystyle {\mathcal {}}n^{2}}$	25 !${\displaystyle {\mathcal {}}n^{2}}$	25 !${\displaystyle {\mathcal {}}n^{2}}$	00 !${\displaystyle {\mathcal {}}{1}}$	ไม่
การเรียงลำดับแบบฟอง	15 !${\displaystyle {\mathcal {}}n}$	25 !${\displaystyle {\mathcal {}}n^{2}}$	25 !${\displaystyle {\mathcal {}}n^{2}}$	00 !${\displaystyle {\mathcal {}}{1}}$	ใช่
	15 !${\displaystyle {\mathcal {}}n}$	20 !${\displaystyle {\mathcal {}}{n\log n}}$	20 !${\displaystyle {\mathcal {}}{n\log n}}$	15 !${\displaystyle {\mathcal {}}n}$	ใช่

ดูเพิ่ม

• สัญกรณ์โอใหญ่