โปรแกรม C++ สำหรับการจัดเรียงหวี?

แนวคิดพื้นฐานของการเรียงหวีและการเรียงลำดับฟองนั้นเหมือนกัน กล่าวอีกนัยหนึ่งการจัดเรียงหวีเป็นการปรับปรุงการเรียงลำดับแบบฟอง ในเทคนิคการคัดแยกแบบฟองอากาศ รายการจะถูกเปรียบเทียบกับรายการถัดไปในแต่ละเฟส แต่สำหรับการจัดเรียงหวี รายการจะถูกจัดเรียงในช่องว่างเฉพาะ หลังจากเสร็จสิ้นแต่ละขั้นตอน ช่องว่างจะลดลง ปัจจัยการลดลงหรือปัจจัยการหดตัวสำหรับการจัดเรียงนี้คือ 1.3 หมายความว่าหลังจากเสร็จสิ้นแต่ละเฟสแล้ว ช่องว่างจะถูกหารด้วย 1.3 ความซับซ้อนของเวลาคือ O(n log n) สำหรับกรณีที่ดีที่สุด O(n ² /2n ^พี ) (p คือจำนวนที่เพิ่มขึ้น) สำหรับตัวพิมพ์เฉลี่ยและ O(n ² ) สำหรับกรณีที่เลวร้ายที่สุด

อัลกอริทึม

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