การเรียงลำดับเชลล์

Shellsort หรือที่เรียกว่า Shell sort หรือ Shell's method คือการเปรียบเทียบการเปรียบเทียบในสถานที่ มันสามารถมองเห็นได้เป็นอย่างใดอย่างหนึ่งโดยทั่วไปของการเรียงลำดับโดยการแลกเปลี่ยน (bubble sort) หรือการเรียงลำดับโดยการแทรก (insertion sort)  วิธีนี้เริ่มต้นด้วยการเรียงลำดับคู่ขององค์ประกอบที่ห่างกันซึ่งกันและกันแล้วค่อยลดช่องว่างระหว่างส่วนที่จะนำมาเปรียบเทียบ เริ่มต้นด้วยองค์ประกอบที่แยกออกจากกันทำให้สามารถเคลื่อนย้ายองค์ประกอบที่ไม่อยู่ในสถานที่ออกไปได้เร็วกว่าการแลกเปลี่ยนเพื่อนบ้านที่ใกล้ที่สุดเพียงอย่างเดียว โดนัลด์เชลล์ได้ตีพิมพ์ฉบับแรกในปีพศ. 2502  เวลาทำงานของ Shellsort ขึ้นอยู่กับลำดับช่องว่างที่ใช้มาก สำหรับตัวแปรที่เป็นประโยชน์หลายประการการกำหนดความซับซ้อนของเวลายังคงเป็นปัญหาที่เปิดอยู่

 ขั้นตอนการจัดเรียงแบบ Shellsort 

 เลือก Gap ตัวแรก โดยเราจะใช้ค่าครึ่งหนึ่งของ ข้อมูล Gap สมมติว่า ข้อมูลมี 10 ตัว ครึ่งหนึ่งคือ 5สูตรคือ Gap = n/2 ดังนั้น 10/2 = 5 ให้ทำการเรียงข้อมูล Gap ชุดแรกให้เสร็จสิ้น จากนั้นทำการหาค่าข้อมูล Gap ตัวใหม่ ซึ่งก็ต้อง n/2 จะได้ว่า 5/2 = 3 (มีเศษให้ปัดขึ้น) ทำไปเรื่อยๆจน Gap = 1

ตัวอย่างการจัดเรียงแบบ Shellsort
 1  2  3  4 5  6  7  8 9  10  11  12 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 ไม่เสถียร: อาจเปลี่ยนแปลงลำดับขององค์ประกอบที่มีค่าเท่ากัน เป็นอัลกอริธึมการจัดเรียงแบบปรับตัวที่ทำงานได้เร็วขึ้นเมื่อป้อนข้อมูลบางส่วน

อ้างอิง

หมวดหมู่:ขั้นตอนวิธีการเรียงลำดับ
หมวดหมู่:การเรียงแบบเปรียบเทียบ