เชลล์ ซอร์ต

เทคนิคการเรียงลำดับเชลล์ขึ้นอยู่กับการเรียงลำดับการแทรก ในการเรียงลำดับการแทรก บางครั้งเราจำเป็นต้องเปลี่ยนบล็อกขนาดใหญ่เพื่อแทรกรายการในตำแหน่งที่ถูกต้อง การใช้การเรียงลำดับเชลล์ทำให้เราสามารถหลีกเลี่ยงการขยับจำนวนมากได้ การเรียงลำดับเสร็จสิ้นด้วยช่วงเวลาที่กำหนด หลังจากผ่านแต่ละรอบ ช่วงเวลาจะลดลงเพื่อให้เป็นช่วงที่เล็กลง

ความซับซ้อนของเทคนิคการจัดเรียงเปลือก

• ความซับซ้อนของเวลา:O(n log n) สำหรับกรณีที่ดีที่สุด และสำหรับกรณีอื่นๆ ขึ้นอยู่กับลำดับช่องว่าง
• ความซับซ้อนของอวกาศ:O(1)

อินพุตและเอาต์พุต

Input:The unsorted list:23 56 97 21 35 689 854 12 47 66Output:Array before Sorting:23 56 97 21 35 689 854 12 47 66Array after Sorting:12 21 23 35 47 56 66 97 689 854

อัลกอริทึม

shellSort(อาร์เรย์, ขนาด)

อินพุต - อาร์เรย์ของข้อมูลและจำนวนทั้งหมดในอาร์เรย์

ผลลัพธ์ − อาร์เรย์ที่เรียงลำดับ

เริ่มต้นสำหรับ gap :=size / 2 เมื่อ gap>
 0 และ gap ถูกอัพเดตด้วย gap / 2 do for j:=gap to size– 1 do for k :=j-gap to 0, ลดลงตามค่า gap do ถ้า array[k+gap]>=array[k] แตกอีกอัน สลับ array[k + gap] กับ array[k] เสร็จสิ้น เสร็จสิ้น doneEnd

ตัวอย่าง

#include โดยใช้เนมสเปซ std; void swapping (int &a, int &b) {// สลับเนื้อหาของ a และ b int temp; อุณหภูมิ =a; ก =ข; b =temp;} void display (int *array, int size) { for(int i =0; i 0; ช่องว่าง =ช่องว่าง / 2) {// ช่องว่างเริ่มต้น =n/2 ลดลงตามช่องว่าง /2 สำหรับ (j =ช่องว่าง; j=0; k -=gap) { if(arr[k+gap]>=arr[k]) แตก; การแลกเปลี่ยนอื่น (arr[k+gap], arr[k]); } } }}int main() { int n; cout <<"ป้อนจำนวนขององค์ประกอบ:"; ซิน>> น; int arr[n]; //สร้างอาร์เรย์ด้วยจำนวนองค์ประกอบที่กำหนด cout <<"ป้อนองค์ประกอบ:" <> arr[i]; } cout <<"อาร์เรย์ก่อนจัดเรียง:"; แสดง(arr, n); shellSort(arr, n); cout <<"อาร์เรย์หลังการเรียงลำดับ:"; display(arr, n);}

ผลลัพธ์

ป้อนจำนวนองค์ประกอบ:10ป้อนองค์ประกอบ:23 56 97 21 35 689 854 12 47 66อาร์เรย์ก่อนจัดเรียง:23 56 97 21 35 689 854 12 47 66อาร์เรย์หลังการเรียงลำดับ:12 21 23 35 47 56 66 97 689 854