ขั้นตอนวิธีการเรียงลำดับ ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีการเรียงลำดับ (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)ขอขอบคุณ วิกิพีเดีย สารานุกรมเสรีสิริสวัสดิ์จันทราร สิริมานปรีดิ์เกษมนะคะ Create Date :04 ธันวาคม 2553 Last Update :17 กุมภาพันธ์ 2554 14:01:06 น. Counter : Pageviews. Comments :0 twitter google