หวีเรียง

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

ความซับซ้อนของเทคนิคการเรียงหวี

• ความซับซ้อนของเวลา: O(n log n) สำหรับกรณีที่ดีที่สุด O(n^2/2^p) (p คือจำนวนที่เพิ่มขึ้น) สำหรับตัวพิมพ์เฉลี่ยและ O(n^2) สำหรับกรณีที่แย่ที่สุด
• ความซับซ้อนของอวกาศ: O(1)

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

Input:รายการของข้อมูลที่ไม่ได้เรียงลำดับ:108 96 23 74 12 56 85 42 13 47Output:Array before Sorting:108 96 23 74 12 56 85 42 13 47Array after Sorting:12 13 23 42 47 56 74 85 96 108

อัลกอริทึม

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

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

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

Begin gap :=size flag :=true while the gap ≠ 1 OR flag =true do gap =floor(gap/1.3) // the floor value after division if gap <1 then gap :=1 flag =false สำหรับ i :=0 ถึงขนาด – ช่องว่าง -1 ทำถ้า array[i]> array[i+gap] จากนั้นสลับ array[i] ด้วย array[i+gap] flag =true; เสร็จแล้วจบ

ตัวอย่าง

#include#includeusing เนมสเปซ std;void display(int *array, int size) { for(int i =0; i array[i+gap]) { swap(array[i], array[i+gap] ); ธง =จริง; } } }}int main() { int n; cout <<"ป้อนจำนวนขององค์ประกอบ:"; ซิน>> น; int arr[n]; //สร้างอาร์เรย์ด้วยจำนวนองค์ประกอบที่กำหนด cout <<"ป้อนองค์ประกอบ:" <> arr[i]; } cout <<"อาร์เรย์ก่อนจัดเรียง:"; แสดง(arr, n); combSort(arr, n); cout <<"อาร์เรย์หลังการเรียงลำดับ:"; display(arr, n);}

ผลลัพธ์

ป้อนจำนวนองค์ประกอบ:10ป้อนองค์ประกอบ:108 96 23 74 12 56 85 42 13 47อาร์เรย์ก่อนเรียงลำดับ:108 96 23 74 12 56 85 42 13 47อาร์เรย์หลังการเรียงลำดับ:12 13 23 42 47 56 74 85 96 108