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

จากวิกิพีเดีย สารานุกรมเสรี
ไบยังการนำทาง ไปยังการค้นหา
การเรียงลำดับเชลล์
Step-by-step visualisation of 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 หรือที่เรียกว่า 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 = 2 (มีเศษให้ปัดทิ้ง) ทำไปเรื่อยๆจน 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 ไม่เสถียร: อาจเปลี่ยนแปลงลำดับขององค์ประกอบที่มีค่าเท่ากัน เป็นอัลกอริธึมการจัดเรียงแบบปรับตัวที่ทำงานได้เร็วขึ้นเมื่อป้อนข้อมูลบางส่วน

อ้างอิง[แก้]