การเรียงลำดับเชลล์
Shellsort หรือที่เรียกว่า Shell sort หรือ Shell's method คือการเปรียบเทียบการเปรียบเทียบในสถานที่ มันสามารถมองเห็นได้เป็นอย่างใดอย่างหนึ่งโดยทั่วไปของการเรียงลำดับโดยการแลกเปลี่ยน (bubble sort) หรือการเรียงลำดับโดยการแทรก (insertion sort) วิธีนี้เริ่มต้นด้วยการเรียงลำดับคู่ขององค์ประกอบที่ห่างกันซึ่งกันและกันแล้วค่อยลดช่องว่างระหว่างส่วนที่จะนำมาเปรียบเทียบ เริ่มต้นด้วยองค์ประกอบที่แยกออกจากกันทำให้สามารถเคลื่อนย้ายองค์ประกอบที่ไม่อยู่ในสถานที่ออกไปได้เร็วกว่าการแลกเปลี่ยนเพื่อนบ้านที่ใกล้ที่สุดเพียงอย่างเดียว โดนัลด์เชลล์ได้ตีพิมพ์ฉบับแรกในปีพศ. 2502 เวลาทำงานของ Shellsort ขึ้นอยู่กับลำดับช่องว่างที่ใช้มาก สำหรับตัวแปรที่เป็นประโยชน์หลายประการการกำหนดความซับซ้อนของเวลายังคงเป็นปัญหาที่เปิดอยู่
 Shellsort with gaps 23, 10, 4, 1 in action. | |
| ประเภท | Sorting algorithm |
|---|---|
| โครงสร้างข้อมูล | Array |
| ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด | O(n2) (worst known gap sequence) O(n log2n) (best known gap sequence)[1] |
| ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด | O(n log n)[2] |
| ประสิทธิภาพเมื่อเกิดกรณีทั่วไป | depends on gap sequence |
| ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด | О(n) total, O(1) auxiliary |
ขั้นตอนการจัดเรียงแบบ Shellsort แก้
- เลือก Gap ตัวแรก โดยเราจะใช้ค่าครึ่งหนึ่งของ ข้อมูล Gap สมมติว่า ข้อมูลมี 10 ตัว ครึ่งหนึ่งคือ 5สูตรคือ Gap = n/2 ดังนั้น 10/2 = 5 ให้ทำการเรียงข้อมูล Gap ชุดแรกให้เสร็จสิ้น จากนั้นทำการหาค่าข้อมูล Gap ตัวใหม่ ซึ่งก็ต้อง n/2 จะได้ว่า 5/2 = 3 (มีเศษให้ปัดขึ้น) ทำไปเรื่อยๆจน Gap = 1
ตัวอย่างการจัดเรียงแบบ Shellsort
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 | a11 | a12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Input data | 62 | 83 | 18 | 53 | 07 | 17 | 95 | 86 | 47 | 69 | 25 | 28 |
| After 5-sorting | 17 | 28 | 18 | 47 | 07 | 25 | 83 | 86 | 53 | 69 | 62 | 95 |
| After 3-sorting | 17 | 07 | 18 | 47 | 28 | 25 | 69 | 62 | 53 | 83 | 86 | 95 |
| After 1-sorting | 07 | 17 | 18 | 25 | 28 | 47 | 53 | 62 | 69 | 83 | 86 | 95 |
การเรียงลำดับครั้งแรกจะดำเนินการเรียงลำดับการแทรกในห้าอาร์เรย์ย่อย (a1, a6, a11), a1, a7, a3, ยกตัวอย่างเช่นมันจะเปลี่ยน อาร์เรย์ย่อย (a1, a6, a11) จาก (62, 17, 25) เป็น (17, 25, 62) การเรียงลำดับถัดไปจะเรียงลำดับตามรูปแบบ อาร์เรย์ย่อย สามชุด (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12) รหัสผ่านสุดท้ายคือ 1-sorting คือการเรียงลำดับแบบธรรมดาของอาร์เรย์ทั้งหมด (a1, ... , a12)
เป็นตัวอย่างแสดงให้เห็นว่า อาร์เรย์ย่อย ที่ Shellsort ดำเนินการอยู่ในระยะแรกสั้น; ต่อมาพวกเขาจะยาว แต่เกือบจะสั่ง ในทั้งสองกรณีการจัดเรียงแทรกทำงานได้อย่างมีประสิทธิภาพ
Shellsort ไม่เสถียร: อาจเปลี่ยนแปลงลำดับขององค์ประกอบที่มีค่าเท่ากัน เป็นอัลกอริธึมการจัดเรียงแบบปรับตัวที่ทำงานได้เร็วขึ้นเมื่อป้อนข้อมูลบางส่วน
อ้างอิง แก้
- ↑ Pratt, Vaughan Ronald (1979). Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences). Garland. ISBN 0-8240-4406-1.[ลิงก์เสีย]
- ↑ "Shellsort & Comparisons". คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2019-12-20. สืบค้นเมื่อ 2018-05-07.