Loading AI tools
จากวิกิพีเดีย สารานุกรมเสรี
ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีการเรียงลำดับ (อังกฤษ: sorting algorithm) คือ ขั้นตอนวิธีที่จัดเรียงสมาชิกของรายการ (list) ให้เป็นไปตามรูปแบบของอันดับที่กำหนด ส่วนใหญ่อันดับที่ใช้กันคือ อันดับตัวเลข และอันดับตัวอักษร การเรียงลำดับที่มีประสิทธิภาพมีความสำคัญต่อขั้นตอนวิธีอื่นๆ (เช่น ขั้นตอนวิธีการค้นหา และ การผสาน) ซึ่งขั้นตอนวิธีเหล่านี้ต้องใช้รายการที่เรียงอย่างถูกต้อง
บทความนี้ไม่มีการอ้างอิงจากแหล่งที่มาใด |
ขั้นตอนวิธีการเรียงลำดับที่ใช้ในวิทยาการคอมพิวเตอร์ จำแนกประเภทได้ตามนี้
ในกรณีที่มีสมาชิกที่มีคีย์เท่ากัน และไม่สามารถแยกแยะได้ เช่น รายการของจำนวนเต็ม มันจะไม่ส่งผลต่อความเสถียร อย่างไรก็ตาม คู่อันดับของจำนวนเต็มดังต่อไปนี้ จะถูกเรียงโดยสมาชิกตัวหน้าของมัน:
(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 คือจำนวนของเรคอร์ดที่จะนำมาจัดเรียง
ชื่อ | กรณีดีที่สุด | กรณีทั่วไป | กรณีแย่ที่สุด | การใช้หน่วยความจำ | เสถียร |
---|---|---|---|---|---|
การเรียงลำดับแบบเร็ว | |||||
การเรียงลำดับแบบผสาน | กรณีแย่ที่สุดคือ | ใช่ | |||
การเรียงลำดับแบบฮีป | ไม่ | ||||
การเรียงลำดับแบบแทรก | ใช่ | ||||
การเรียงลำดับแบบเลือก | ไม่ | ||||
การเรียงลำดับแบบฟอง | ใช่ | ||||
การเรียงลำดับด้วยต้นไม้ค้นหาแบบทวิภาค | ใช่ | ||||
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.