การเรียงลำดับของเชลล์เป็นอัลกอริทึมการเรียงลำดับ "วิเศษ" มีการกล่าวกันว่าเป็น "เวทมนตร์" เพราะไม่มีใครสามารถอธิบายได้อย่างชัดเจนว่าประสิทธิภาพของมันสามารถบรรลุได้อย่างชัดเจน การจัดเรียงฮิลล์เพราะ dl เชลล์ได้รับการตั้งชื่อตามมันถูกเสนอในปี 1959 เนื่องจาก Car Hoare เสนอการเรียงลำดับอย่างรวดเร็วในปี 1962 มันมักจะใช้การเรียงลำดับอย่างรวดเร็วเพราะมันง่ายกว่า อย่างไรก็ตามนักคณิตศาสตร์หลายคนยังคงมองหาความซับซ้อนที่ดีที่สุดของการเรียงลำดับบนเนินเขา ในฐานะโปรแกรมเมอร์ธรรมดาเราสามารถเรียนรู้แนวคิดของฮิลล์
โดยวิธีการก่อนที่การเรียงลำดับฮิลล์จะปรากฏขึ้นมีมุมมองทั่วไปในโลกคอมพิวเตอร์ว่า "การเรียงลำดับอัลกอริทึมไม่สามารถผ่าน o (n2)" การเกิดขึ้นของการเรียงลำดับของฮิลล์ทำให้คำสาปนี้แตกสลายและในไม่ช้าอัลกอริทึมเช่นการเรียงลำดับอย่างรวดเร็วก็ถูกปล่อยออกมาอีกครั้ง ในแง่นี้การเรียงลำดับฮิลล์นำเราไปสู่ยุคใหม่
ภาพรวมอัลกอริทึม/แนวคิด
ข้อเสนอของการเรียงลำดับฮิลล์ส่วนใหญ่ขึ้นอยู่กับสองจุดต่อไปนี้:
1. อัลกอริทึมการเรียงลำดับการแทรกสามารถบรรลุความซับซ้อนของ o (n) โดยประมาณและมีประสิทธิภาพอย่างมากเมื่อมีการสั่งอาร์เรย์โดยทั่วไป
2. อย่างไรก็ตามการเรียงลำดับการแทรกสามารถย้ายข้อมูลได้ทีละบิตเท่านั้นและประสิทธิภาพจะลดลงอย่างรวดเร็วเมื่ออาเรย์มีขนาดใหญ่และไม่เป็นระเบียบ
จากสิ่งนี้เราสามารถใช้วิธีการเรียงลำดับการเรียงลำดับซึ่งเป็นวิธีเฉพาะ: (ใช้อาร์เรย์ของ 16 องค์ประกอบเป็นตัวอย่าง)
1. เลือกเดลต้าที่เพิ่มขึ้นซึ่งมากกว่า 1 และเลือก subarray จากอาร์เรย์โดยการเพิ่มขึ้นนี้สำหรับการเรียงลำดับการแทรกโดยตรง ตัวอย่างเช่นหากเลือกการเพิ่มขึ้น 5 องค์ประกอบที่มีตัวห้อย 0, 5, 10, 15 จะถูกเรียงลำดับ
2. เก็บเดลต้าที่เพิ่มขึ้นและย้ายองค์ประกอบแรกเพื่อรับการแทรกและการเรียงลำดับจนกว่ารอบจะเสร็จสิ้น สำหรับตัวอย่างข้างต้นอาร์เรย์ [1, 6, 11], [2, 7, 12], [3, 8, 13], [4, 9, 14] ถูกจัดเรียงในทางกลับกัน
3. ลดการเพิ่มขึ้นและทำซ้ำกระบวนการข้างต้นอย่างต่อเนื่องจนกว่าการเพิ่มขึ้นจะลดลงเป็น 1 เห็นได้ชัดว่าครั้งสุดท้ายคือการเรียงลำดับโดยตรง
4. การเรียงลำดับเสร็จสมบูรณ์
ดังที่เห็นได้จากด้านบนการเพิ่มขึ้นอย่างต่อเนื่องลดลงอย่างต่อเนื่องดังนั้นการเรียงลำดับของฮิลล์จึงเรียกว่า "การเรียงลำดับที่ลดลง"
การใช้รหัส
การเรียงลำดับแพ็คเกจ; ShellsortTest ชั้นเรียนสาธารณะ {จำนวน int คงที่สาธารณะ = 0; โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int [] data = new int [] {5, 3, 6, 2, 1, 9, 4, 8, 7}; พิมพ์ (ข้อมูล); Shellsort (ข้อมูล); พิมพ์ (ข้อมูล); } โมฆะแบบคงที่สาธารณะ shellsort (int [] data) {// คำนวณค่าสูงสุด h h ค่า int h = 1; ในขณะที่ (h <= data.length / 3) {h = h * 3 + 1; } ในขณะที่ (h> 0) {สำหรับ (int i = h; i <data.length; i += h) {ถ้า (data [i] <data [i - h]) {int tmp = data [i]; int j = i - h; ในขณะที่ (j> = 0 && data [j]> tmp) {data [j + h] = data [j]; j -= h; } data [j + h] = tmp; พิมพ์ (ข้อมูล); }} // คำนวณค่า h ถัดไป h = (h - 1) / 3; }} การพิมพ์โมฆะคงที่สาธารณะ (int [] data) {สำหรับ (int i = 0; i <data.length; i ++) {system.out.print (data [i]+"/t"); } system.out.println (); - ผลการทำงาน:
5 3 6 2 1 9 4 8 7 1 3 6 2 5 9 4 8 7 1 2 3 6 5 9 4 8 7 1 2 3 5 6 9 4 8 7 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
ประสิทธิภาพ/ความซับซ้อนของอัลกอริทึม
ลำดับที่เพิ่มขึ้นเรียงลำดับโดยฮิลล์สามารถดำเนินการได้ตลอดเวลาและข้อกำหนดเพียงอย่างเดียวคือลำดับสุดท้ายต้องเป็น 1 (เพราะจำเป็นต้องตรวจสอบให้แน่ใจว่าได้รับคำสั่งโดย 1) อย่างไรก็ตามการเลือกลำดับที่แตกต่างกันจะมีผลกระทบอย่างมากต่อประสิทธิภาพของอัลกอริทึม รหัสข้างต้นแสดงให้เห็นถึงการเพิ่มขึ้นสองครั้ง
โปรดจำไว้ว่า: มันเป็นการดีที่สุดที่จะไม่มีปัจจัยทั่วไปนอกเหนือจาก 1 สำหรับทุกสององค์ประกอบในลำดับที่เพิ่มขึ้น! (เห็นได้ชัดว่าการเรียงลำดับ 2 ในลำดับไม่ได้มีความหมายมาก)
ด้านล่างนี้เป็นลำดับที่เพิ่มขึ้นทั่วไป
การเพิ่มขึ้นครั้งแรกคือการเสนอครั้งแรกโดย Donald Shell เช่นการพับจะลดลงเป็น 1 ตามการวิจัยโดยใช้การเพิ่มขึ้นของเนินเขาความซับซ้อนของเวลายังคงเป็น O (N2)
การเพิ่มขึ้นครั้งที่สอง Hibbard: {1, 3, ... , 2^k-1} ความซับซ้อนของเวลาของลำดับที่เพิ่มขึ้นนี้อยู่ที่ประมาณ o (n^1.5)
การเพิ่มขึ้นครั้งที่สามที่เพิ่มขึ้น Sedgewick: (1, 5, 19, 41, 109, ... ) ซึ่งสร้างลำดับทั้ง 9*4^i - 9*2^i + 1 หรือ 4^i - 3*2^i + 1
ความเสถียรของอัลกอริทึม
เราทุกคนรู้ว่าการเรียงลำดับการแทรกเป็นอัลกอริทึมที่เสถียร อย่างไรก็ตามการเรียงลำดับของเชลล์เป็นกระบวนการของการแทรกหลายครั้ง ในการแทรกครั้งเดียวเราสามารถมั่นใจได้ว่าลำดับขององค์ประกอบเดียวกันไม่ได้ถูกย้าย แต่ในการแทรกหลายครั้งมันเป็นไปได้ทั้งหมดที่องค์ประกอบเดียวกันจะถูกย้ายในรอบการแทรกที่แตกต่างกันและความเสถียรในที่สุดก็ถูกทำลาย ดังนั้นการเรียงลำดับของเชลล์จึงไม่ใช่อัลกอริทึมที่เสถียร
อัลกอริทึมสถานการณ์ที่ใช้งานได้
แม้ว่าการเรียงลำดับของเชลล์จะเร็ว แต่ก็มีการเรียงลำดับการเรียงลำดับและลำดับความสำคัญของมันไม่ดีเท่าดาวที่เพิ่มขึ้น - การเรียงลำดับอย่างรวดเร็ว O (NN) นั้นเร็ว การเรียงลำดับของเชลล์ไม่ใช่อัลกอริทึมที่ดีในการเผชิญกับข้อมูลจำนวนมาก อย่างไรก็ตามมันเป็นไปได้อย่างสมบูรณ์ที่จะใช้ข้อมูลขนาดเล็กและขนาดกลาง