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

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

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

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

ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด O(n log n)[2]
ประเภท Sorting algorithm
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป depends on gap sequence
โครงสร้างข้อมูล Array
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด О(n) total, O(1) auxiliary
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด O(n2) (worst known gap sequence)
O(n log2n) (best known gap sequence)[1]

ใกล้เคียง

การเรียนรู้ของเครื่อง การเร่งปฏิกิริยา การเรืองแสงของบรรยากาศ การเรียนรู้เชิงลึก การเร็นเดอร์ การเรียน การเรียกยานพาหนะคืนของโตโยต้า พ.ศ. 2552−2553 การเรียงลำดับแบบฟอง การเรียกชื่อสารเคมีตามระบบไอยูแพ็ก การเร่งโดยอาศัยแอนติบอดี