SHELL SORT

SHELL SORT

โดยปกติการเรียงข้อมูลแบบที่ใช้การเปรียบเทียบประมาณ n log2n จะต้องมีกระบวนการและขั้นตอนที่พิสดารกว่าการเรียงข้อมูลแบบที่ใช้การเปรียบเทียบประมาณ n2 ครั้ง แต่ถ้าจำนวนข้อมูลที่ต้องเรียงมีจำนวนน้อย หรือเกือบจะเรียงกันอยู่แล้ว การทำงานของแบบการคำนวณแบบ n2 นั้นจะทำงานได้ดีกว่าการเรียงแบบ n log2n การเรียงที่จะกล่าวต่อไปนี้ จะใช้แนวความคิดจากเรื่องนี้ นั่นคือแทนที่จะเรียงข้อมูลทั้งชุดโดยตรง เราจะแบ่งข้อมูลทั้งชุดหรือคีย์ที่แทนข้อมูลเหล่านี้ออกเป็นส่วนย่อย ๆ แล้วเรียงส่วนย่อย ๆ เหล่านั้นโดยใช้อัลกอริทึม n2 เช่น bubble sort หรือinsertion sort

จากชุดคีย์ที่กำหนดให้เราจะไม่แบ่งคีย์ชุดนั้นออกเป็นลิสต์ย่อยจริง ๆ แต่จะทำการแบ่งโดยกำหนดค่าที่จะอยู่ในลิสต์ย่อย อนึ่งแต่ละลิสต์ย่อยจะมีคีย์อยู่ประมาณ n/h ค่า จำนวนคีย์ในลิสต์ย่อยในแต่ละเที่ยวที่ทำการเรียงจะไม่เท่ากัน แต่จะถูกกำหนดโดยค่า h ต่อไปนี้ ht,h t - 1 ,…,h1 โดยที่ค่า h1 = 1 เสมอ การเรียงจะสิ้นสุดเมื่อทำการเรียงเป็นจำนวน t เที่ยว

การเลือกค่า hI
วิธีการเลือกค่า hI มีอยู่หลายแบบ ส่วนแบบที่จะกล่าวถึงในที่นี้มี 2 แบบ คือ
(1) ให้เลือก h i = 2 i - 1โดยที่ค่า i อยู่ระหว่างค่า 1 และ (log2n)
ถ้าเลือก hi โดยวิธีนี้ จำนวนครั้งที่ต้องมีการเปรียบเทียบคีย์
จะเป็น O(n 3/2) ซึ่งเป็นกรณีเลวร้ายที่สุด (2) ชุดค่า hi ที่ใช้ได้ดีอีกแบบหนึ่งกำหนดโดยสมการ

hi = (3 i - 1)/ 2
สำหรับค่าi อยู่ระหว่าง 1 และ t โดยที่ t เป็นค่าจำนวนเต็มน้อยที่สุดที่สอดคล้องกับอสมการ h t - 1 ณ n

สมมติให้ชุดคีย์ที่จะเรียงมีดังนี้
(37,32,14,45,92,18,34,31,35)

เราจะเลือกค่า hi จากแบบ(1) ที่กล่าวมาแล้ว เนื่องจาก n = 10 เราจะได้ว่า (log210) = 3
ดังนั้นค่า i ที่ใช้คือ 3,2,1 และจะได้ h3 = 7, h2 = 3, h1 = 1 ตามลำดับ จากสมการ h i = 2 i - 1


[Only admins are allowed to see this image]

การเรียงเที่ยวที่ 1 จะมี 3 ลิสต์ย่อย ดังที่แสดงโดยเส้นที่โยงไว้ 3 ลิสต์ย่อยนี้คือ (37,34)(32,31)(14,35) หลังจากการเรียงแต่ละลิสต์ย่อยแล้วจะได้ชุดตัวเลขดังนี้

[Only admins are allowed to see this image]

การเรียงเที่ยวที่ 2 จะประกอบด้วย 3 ลิสต์ย่อย คือ (34,45,19,35) (31,92,37) (14,18,32) หลังจากการเรียงแต่ละลิสต์ย่อยแล้วจะได้
19 31 14 34 37 18 35 92 32 45

การเรียงเที่ยวที่ 3 จะประกอบด้วยลิสต์เพียงลิสต์เดียว นั่นคือทุกค่าในลิสต์นี้ การเรียงเท่ากับการใช้ insertion sort หรือการเรียงแบบอื่น ๆ



เมื่อเรียงแล้วจะได้ 14 18 19 31 32 34 35 37 45 92
สังเกตดูข้อมูลจากการเรียงโดยวิธี shell นี้ การเลือกค่า hi อีกแบบที่มีประโยชน์ (และง่าย) ก็คือ ให้ hi = 1 แล้วให้ h i +1 = 3h i +1 และให้หยุดที่ h t เมื่อ h t +2 มีค่ามากกว่า n


*เครดิต [Only admins are allowed to see this link]