การจัดเรียงแบบ Shell Sort

Shell Sort

การจัดเรียงข้อมูลแบบ Shell Sort เป็นวิธีการที่ช่วยปรับปรุง Insertion Sort ให้มีจำนวนครั้งการสับเปลี่ยนข้อมูลลดลง เนื่องจากวิธีการ Insertion Sort อาจจะเกิด Worst-Case ในกรณีเลวร้าย ที่ค่าตัวเลขเล็กๆ ดันไปอยู่ที่ข้างท้ายๆ ทำให้การสแกนหาตำแหน่งที่เหมาะสม ต้องใช้วิธีนานมาก

วิธีการ Shell Sort ปรับปรุงโดยทำการจัดเรียงชุดย่อย โดยแต่ละชุดย่อยเรียกว่า k-sorted โดย k จะเป็นเลขลำดับที่เพิ่มมากขึ้นเรื่อยๆ เช่น k อาจจะเป็นเลข {1, 3, 5} หมายถึง ครั้งแรกที่ทำ 5-sorted จะจัดเรียงตัวเลขทุกตัวที่ห่างกันทีละ 5 ช่อง  เมื่อเรียงเสร็จแล้วจะทำ 3-sorted โดยจัดเรียงตัวเลขทุกตัวที่ห่างกันทีละ 3 ช่อง และสุดท้ายจะทำ 1-sorted โดยจัดเรียงตัวเลขทุกตัวที่ติดกันอยู่ ซึ่งในรอบสุดท้ายที่ 1-sorted จะเป็นวิธีการเดียวกับ Insertion Sort นั่นเอง

เราเรียกค่า k = {1, 3, 5} นี้ว่า increment sequence และบางครั้งเรียกวิธีการจัดเรียง Shell Sort นี้ว่า diminishing increment sort

ตัวอย่างเช่น ถ้ามีเลขอยู่ 13 ตัวดังนี้ และให้ k = {1, 3, 5}

ถ้าจะจัดเรียงแบบ Shell Sort รอบแรกเราจะทำ 5-sorted ก่อน โดยจัดเรียงเฉพาะเลขที่ห่างกันไปทีละ 5 ดังนี้

ในแต่ละรอบย่อย เราจัดเรียงแบบ Insertion Sort เช่น ในรอบบนสุด เราจัดเรียงเลข 81, 35, 41 แบบ Insertion Sort และใช้จำนวนครั้งในการสับเปลี่ยนตำแหน่งเป็น 2 ครั้ง

ในรอบย่อยต่อมาเราจัดเรียงเลข 94, 17, 75 และใช้จำนวนครั้งที่สับเปลี่ยนตำแหน่งเป็น 2 ครั้งเช่นกัน

เมื่อทำไปเรื่อยๆจนกระทั่งไม่ตัวให้เปรียบเทียบจะถือว่าเสร็จสิ้น 5-sorted ซึ่งจะได้ตามค่าแถวล่างสุด และมีจำนวนครั้งการสับเปลี่ยนทั้งหมดรวม 5 ครั้ง

เมื่อขึ้นรอบใหม่ของ 3-sorted เราจะแบ่งกลุ่มเลขทีละ 3 ตำแหน่ง และนำมาจัดเรียงแบบ Insertion Sort เช่นเดิม ซึ่งจะได้ผลลัพธ์ดังนี้

เมื่อเสร็จสิ้น 3-sorted เราจะได้จำนวนครั้งการสับเปลี่ยน รวมทั้งหมด 5 ครั้ง และตัวเลขทั้งหมดเกือบจะเรียงกันหมดแล้ว

สังเกตว่าวิธีการของ Shell Sort จะทำให้เลขใกล้สู่การเรียงลำดับขึ้นสุดท้ายมากยิ่งขึ้นเรื่อยๆ ทุกครั้งที่ผ่าน k-sorted ตามหลักการของ Insertion Sort ปกติแล้วถ้าไพ่ในมือในจัดเรียงไว้ดีอยู่แล้ว การรับไพ่ใบใหม่เข้ามาเพื่อแทรกเข้าไปในกองจะทำใช้เวลาลดลงเรื่อยๆ ด้วยเหตุผลนี่เอง Shell Sort จึงพยายามทำให้เลขเรียงลำดับดีขึ้นเรื่อยๆ เมื่อมาถึง 1-sorted ก็เกือบจะเรียงกันหมดแล้ว ซึ่งจะมีผลทำให้ Insertion Sort ใช้เวลาน้อยมากกว่า Insertion Sort ปกติ

เราจะจัดเรียงเลขชุดนี้ใน 1-sorted ตามแบบ Insertion Sort ปกติ ดังนี้

สังเกตว่าเมื่อจบ 1-sorted เราใช้จำนวนครั้งการสับเปลี่ยนไปทั้งหมด 12 ครั้ง เมื่อรวมการสับเปลี่ยนทั้งหมด ตั้งแต่ 5-sorted, 3-sorted และ 1-sorted เราใช้การสับเปลี่ยนไปทั้งหมด 5+5+12 = 22 ครั้ง

เทียบกับ Insertion Sort แบบปกติ

จากชุดข้อมูลข้างต้นถ้าเรานำตัวเลขมาจัดเรียงแบบ Insertion Sort ตามปกติจะได้ขั้นตอนดังนี้

สังเกตว่า Insertion Sort ปกติ จะใช้การสับเปลี่ยนทั้งหมด 39 ครั้ง ซึ่งเมื่อเทียบกับ Shell Sort ที่ใช้เพียง 22 ครั้ง ถือว่า Shell Sort มีประสิทธิภาพสูงกว่า

การเลือก Increment Sequence

ถ้าเราเลือก Increment Sequence ไม่ดีพออาจจะทำให้ Shell Sort ใช้ Big O ถึง O(N²) แต่ถ้าเราเลือก sequence ที่ดีพอจะทำให้ได้ Big O ที่ต่ำกว่า

ตัวอย่างของนักคิดที่ให้ Increment Sequence ไว้ดังนี้

o    Hibbard’s increment อ้างว่าสามารถทำได้ที่ O(N^5/4)

o    Pratt แสดงให้เห็นว่าสามารถทำได้ที่ O(N^3/2) ด้วยชุด increment sequence ที่กว้างมาก

o    Sedgewick ให้ sequence ไว้ที่ {1, 5, 19, 41, 109, ... } ซึ่งมาจากสูตร 9(4ⁱ) – 9(2ⁱ) + 1 หรือ 4ⁱ – 3(2ⁱ) + 1 ซึ่งจะทำให้ได้ Worst-Case ที่ O(N^4/3) และคาดว่าโดยเฉลี่ยอาจจะได้ถึง O(N^7/6)