สารบัญ
- การแนะนำ
- Merge Sort ใน C++ คืออะไร
- แนวทางการแบ่งแยกและพิชิต
- อัลกอริทึมการเรียงลำดับผสาน
- การใช้งาน Merge Sort ใน C++
- บทสรุป
1. บทนำ
อัลกอริทึมการเรียงลำดับในวิทยาการคอมพิวเตอร์ใช้เพื่อจัดเรียงข้อมูลในลำดับจากน้อยไปหามากหรือจากมากไปน้อย มีอัลกอริธึมการเรียงลำดับหลายแบบพร้อมคุณสมบัติที่แตกต่างกัน Merge sort เป็นหนึ่งในวิธีการใน C ++ ซึ่งสามารถเรียงลำดับอาร์เรย์ได้
2. Merge Sort ใน C++ คืออะไร
Merge sort ใช้เทคนิคการหารและพิชิตที่สามารถจัดเรียงองค์ประกอบของอาร์เรย์ นอกจากนี้ยังสามารถจัดเรียงรายการองค์ประกอบใน C ++ โดยจะแบ่งอินพุตออกเป็นสองซีก จัดเรียงแต่ละครึ่งแยกกัน แล้วรวมเข้าด้วยกันตามลำดับที่ถูกต้อง
3. วิธีการแบ่งแยกและพิชิต
อัลกอริทึมการเรียงลำดับใช้กลยุทธ์การหารและพิชิต ซึ่งนำมาซึ่งการแบ่งพาร์ติชันอาร์เรย์อินพุตเป็นอาร์เรย์ย่อยที่เล็กลง แก้ปัญหาแยกกัน แล้วรวมผลลัพธ์เพื่อสร้างเอาต์พุตที่เรียงลำดับ ในกรณีของการเรียงลำดับแบบผสาน อาร์เรย์จะถูกแบ่งซ้ำเป็นสองส่วนจนกว่าจะเหลือองค์ประกอบเดียวในแต่ละครึ่ง
4. ผสานอัลกอริทึมการเรียงลำดับ
อัลกอริทึมการเรียงลำดับการผสานประกอบด้วยสองขั้นตอนหลัก: การหารและการผสาน ขั้นตอนมีดังนี้:
4.1 การแบ่ง
อัลกอริทึมการเรียงลำดับผสานเป็นไปตามกลยุทธ์การหารและพิชิตสำหรับการเรียงลำดับองค์ประกอบในอาร์เรย์
- ขั้นตอนแรกในอัลกอริทึมจะตรวจสอบองค์ประกอบอาร์เรย์ หากประกอบด้วยองค์ประกอบเดียว ก็จะถือว่าเรียงลำดับแล้ว และอัลกอริทึมจะส่งคืนอาร์เรย์เดิมโดยไม่มีการเปลี่ยนแปลงใดๆ
- หากอาร์เรย์มีองค์ประกอบมากกว่าหนึ่งรายการ อัลกอริทึมจะดำเนินการแบ่งองค์ประกอบออกเป็นสองซีก: ครึ่งซ้ายและครึ่งขวา
- อัลกอริธึมการเรียงลำดับแบบผสานจะถูกนำไปใช้ซ้ำกับซีกซ้ายและขวาของอาร์เรย์ แบ่งพวกมันออกเป็นอาร์เรย์ย่อยขนาดเล็กอย่างมีประสิทธิภาพและเรียงลำดับทีละรายการ
- กระบวนการเรียกซ้ำนี้จะดำเนินต่อไปจนกว่า subarrays จะมีเพียงหนึ่งองค์ประกอบในแต่ละองค์ประกอบ (ตามขั้นตอนที่ 1) ซึ่งสามารถรวมเข้าด้วยกันเพื่อสร้างอาร์เรย์เอาต์พุตสุดท้ายที่เรียงลำดับได้
4.2 ผสาน
ตอนนี้เราจะเห็นขั้นตอนการรวมอาร์เรย์:
- ขั้นตอนแรกสำหรับอัลกอริทึมการเรียงลำดับผสานเกี่ยวข้องกับการสร้างอาร์เรย์ว่าง
- จากนั้นอัลกอริทึมจะดำเนินการเปรียบเทียบองค์ประกอบแรกของซีกซ้ายและขวาของอาร์เรย์อินพุต
- องค์ประกอบที่เล็กกว่าของทั้งสองจะถูกเพิ่มลงในอาร์เรย์ใหม่ จากนั้นจึงลบออกจากครึ่งหนึ่งของอาร์เรย์อินพุตตามลำดับ
- ทำซ้ำขั้นตอนที่ 2-3 จนกว่าจะหมดครึ่งหนึ่ง
- องค์ประกอบที่เหลืออยู่ในครึ่งที่ไม่ว่างจะถูกเพิ่มไปยังอาร์เรย์ใหม่
- อาร์เรย์ที่เป็นผลลัพธ์จะถูกจัดเรียงอย่างสมบูรณ์และแสดงผลลัพธ์สุดท้ายของอัลกอริธึมการเรียงลำดับการผสาน
5. การใช้งาน Merge Sort ใน C++
หากต้องการใช้การเรียงลำดับการผสานใน C ++ จะมีการปฏิบัติตามสองวิธีที่แตกต่างกัน ความซับซ้อนของเวลาของทั้งสองวิธีนั้นเท่ากัน แต่การใช้ subarrays ชั่วคราวนั้นแตกต่างกัน
วิธีแรกสำหรับการเรียงลำดับการผสานใน C++ ใช้สองแถบย่อยชั่วคราว ในขณะที่วิธีที่สองใช้เพียงหนึ่งเดียว เป็นที่น่าสังเกตว่าขนาดทั้งหมดของ subarrays ชั่วคราวทั้งสองในวิธีแรกจะเท่ากับขนาดของ array ดั้งเดิมในวิธีที่สอง ดังนั้นความซับซ้อนของพื้นที่จึงคงที่
วิธีที่ 1 – การใช้ Temp Subarrays สองอัน
ต่อไปนี้คือตัวอย่างโปรแกรมสำหรับการเรียงลำดับการผสานใน C++ โดยใช้วิธีที่ 1 ซึ่งใช้สองอาร์เรย์ย่อยชั่วคราว:
#รวมถึงใช้เนมสเปซมาตรฐาน ;
เป็นโมฆะ ผสาน ( นานาชาติ อร๊ายยย [ ] , นานาชาติ ล , นานาชาติ ม , นานาชาติ ร )
{
นานาชาติ n1 = ม - ล + 1 ;
นานาชาติ n2 = ร - ม ;
นานาชาติ แอล [ n1 ] , ร [ n2 ] ;
สำหรับ ( นานาชาติ ฉัน = 0 ; ฉัน < n1 ; ฉัน ++ )
แอล [ ฉัน ] = อร๊ายยย [ ล + ฉัน ] ;
สำหรับ ( นานาชาติ เจ = 0 ; เจ < n2 ; เจ ++ )
ร [ เจ ] = อร๊ายยย [ ม + 1 + เจ ] ;
นานาชาติ ฉัน = 0 , เจ = 0 , เค = ล ;
ในขณะที่ ( ฉัน < n1 && เจ < n2 ) {
ถ้า ( แอล [ ฉัน ] <= ร [ เจ ] ) {
อร๊ายยย [ เค ] = แอล [ ฉัน ] ;
ฉัน ++;
}
อื่น {
อร๊ายยย [ เค ] = ร [ เจ ] ;
เจ ++;
}
เค ++;
}
ในขณะที่ ( ฉัน < n1 ) {
อร๊ายยย [ เค ] = แอล [ ฉัน ] ;
ฉัน ++;
เค ++;
}
ในขณะที่ ( เจ < n2 ) {
อร๊ายยย [ เค ] = ร [ เจ ] ;
เจ ++;
เค ++;
}
}
เป็นโมฆะ ผสานการจัดเรียง ( นานาชาติ อร๊ายยย [ ] , นานาชาติ ล , นานาชาติ ร )
{
ถ้า ( ล < ร ) {
นานาชาติ ม = ล + ( ร - ล ) / 2 ;
ผสานการจัดเรียง ( อร๊ายยย , ล , ม ) ;
ผสานการจัดเรียง ( อร๊ายยย , ม + 1 , ร ) ;
ผสาน ( อร๊ายยย , ล , ม , ร ) ;
}
}
นานาชาติ หลัก ( )
{
นานาชาติ อร๊ายยย [ ] = { 12 , สิบเอ็ด , 13 , 5 , 6 , 7 } ;
นานาชาติ arr_size = ขนาดของ ( อร๊ายยย ) / ขนาดของ ( อร๊ายยย [ 0 ] ) ;
ศาล << 'กำหนดอาร์เรย์คือ \n ' ;
สำหรับ ( นานาชาติ ฉัน = 0 ; ฉัน < arr_size ; ฉัน ++ )
ศาล << อร๊ายยย [ ฉัน ] << ' ' ;
ผสานการจัดเรียง ( อร๊ายยย , 0 , arr_size - 1 ) ;
ศาล << ' \n อาร์เรย์ที่เรียงลำดับคือ \n ' ;
สำหรับ ( นานาชาติ ฉัน = 0 ; ฉัน < arr_size ; ฉัน ++ )
ศาล << อร๊ายยย [ ฉัน ] << ' ' ;
กลับ 0 ;
}
ในโปรแกรมนี้ ฟังก์ชันการผสานใช้อาร์กิวเมนต์สามตัว arr, l และ r ซึ่งแทนอาร์เรย์ที่จะจัดเรียงและแสดงดัชนีของ subarray ที่จำเป็นต้องผสาน อันดับแรก ฟังก์ชันจะค้นหาขนาดของสองบาร์เรย์ย่อยที่จะผสาน จากนั้นสร้างสองบาร์เรย์ย่อยชั่วคราว L และ R เพื่อจัดเก็บองค์ประกอบของบาร์เรย์ย่อยเหล่านี้ จากนั้นจะเปรียบเทียบองค์ประกอบใน L และ R และรวมเข้ากับอาร์เรย์เดิมที่ตั้งชื่อไว้ อร๊ายยย จากน้อยไปหามาก
เทคนิคการหารและพิชิตถูกใช้โดยฟังก์ชัน mergeSort เพื่อแบ่งอาร์เรย์ออกเป็นสองส่วนแบบวนซ้ำจนกว่าจะเหลือองค์ประกอบเดียวใน subarray จากนั้นจะรวมแถบย่อยทั้งสองเข้าด้วยกันเป็นแถบย่อยที่เรียงลำดับ ฟังก์ชันยังคงผสาน subarrays ต่อไป เว้นแต่จะเรียงลำดับอาร์เรย์ทั้งหมด
ในฟังก์ชันหลัก เรากำหนดอาร์เรย์ arr ด้วย 6 อิลิเมนต์ และเรียกใช้ฟังก์ชัน mergeSort เพื่อจัดเรียง ในตอนท้ายของรหัส อาร์เรย์ที่เรียงลำดับจะถูกพิมพ์
วิธีที่ 2 – การใช้ One Temp Subarray
ต่อไปนี้คือตัวอย่างโปรแกรมสำหรับการรวมการเรียงลำดับใน C++ โดยใช้วิธีที่ 2 ซึ่งใช้หนึ่งแถบย่อยชั่วคราว:
#รวมถึงใช้เนมสเปซมาตรฐาน ;
เป็นโมฆะ ผสาน ( นานาชาติ อร๊ายยย [ ] , นานาชาติ ล , นานาชาติ ม , นานาชาติ ร )
{
นานาชาติ ฉัน , เจ , เค ;
นานาชาติ n1 = ม - ล + 1 ;
นานาชาติ n2 = ร - ม ;
// สร้าง subarrays ชั่วคราว
นานาชาติ แอล [ n1 ] , ร [ n2 ] ;
// คัดลอกข้อมูลไปยัง subarrays
สำหรับ ( ฉัน = 0 ; ฉัน < n1 ; ฉัน ++ )
แอล [ ฉัน ] = อร๊ายยย [ ล + ฉัน ] ;
สำหรับ ( เจ = 0 ; เจ < n2 ; เจ ++ )
ร [ เจ ] = อร๊ายยย [ ม + 1 + เจ ] ;
// รวม subarrays ชั่วคราวกลับเข้าไปใน array เดิม
ฉัน = 0 ;
เจ = 0 ;
เค = ล ;
ในขณะที่ ( ฉัน < n1 && เจ < n2 ) {
ถ้า ( แอล [ ฉัน ] <= ร [ เจ ] ) {
อร๊ายยย [ เค ] = แอล [ ฉัน ] ;
ฉัน ++;
}
อื่น {
อร๊ายยย [ เค ] = ร [ เจ ] ;
เจ ++;
}
เค ++;
}
// คัดลอกองค์ประกอบที่เหลือของ L[]
ในขณะที่ ( ฉัน < n1 ) {
อร๊ายยย [ เค ] = แอล [ ฉัน ] ;
ฉัน ++;
เค ++;
}
// คัดลอกองค์ประกอบที่เหลือของ R[]
ในขณะที่ ( เจ < n2 ) {
อร๊ายยย [ เค ] = ร [ เจ ] ;
เจ ++;
เค ++;
}
}
เป็นโมฆะ ผสานการจัดเรียง ( นานาชาติ อร๊ายยย [ ] , นานาชาติ ล , นานาชาติ ร )
{
ถ้า ( ล < ร ) {
นานาชาติ ม = ล + ( ร - ล ) / 2 ;
// เรียงลำดับซีกซ้ายและขวาซ้ำ
ผสานการจัดเรียง ( อร๊ายยย , ล , ม ) ;
ผสานการจัดเรียง ( อร๊ายยย , ม + 1 , ร ) ;
// รวมสองส่วนที่เรียงกัน
ผสาน ( อร๊ายยย , ล , ม , ร ) ;
}
}
นานาชาติ หลัก ( )
{
นานาชาติ อร๊ายยย [ ] = { 12 , สิบเอ็ด , 13 , 5 , 6 , 7 } ;
นานาชาติ arr_size = ขนาดของ ( อร๊ายยย ) / ขนาดของ ( อร๊ายยย [ 0 ] ) ;
ศาล << 'กำหนดอาร์เรย์คือ \n ' ;
สำหรับ ( นานาชาติ ฉัน = 0 ; ฉัน < arr_size ; ฉัน ++ )
ศาล << อร๊ายยย [ ฉัน ] << ' ' ;
ผสานการจัดเรียง ( อร๊ายยย , 0 , arr_size - 1 ) ;
ศาล << ' \n อาร์เรย์ที่เรียงลำดับคือ \n ' ;
สำหรับ ( นานาชาติ ฉัน = 0 ; ฉัน < arr_size ; ฉัน ++ )
ศาล << อร๊ายยย [ ฉัน ] << ' ' ;
กลับ 0 ;
}
โปรแกรมนี้เหมือนกับโปรแกรมก่อนหน้านี้ แต่แทนที่จะใช้สองแถบย่อยชั่วคราว L และ R โปรแกรมจะใช้ชั่วคราวหนึ่งแถบน้อยชั่วคราว ฟังก์ชันผสานทำงานในลักษณะเดียวกับก่อนหน้านี้ แต่แทนที่จะคัดลอกข้อมูลไปยัง L และ R ฟังก์ชันจะคัดลอกไปยัง temp จากนั้นจะรวมองค์ประกอบอาร์เรย์ temp กลับเข้าไปใน อร๊ายยย ซึ่งเป็นอาร์เรย์เดิม
ฟังก์ชัน mergeSort เหมือนเดิม ยกเว้นว่าจะใช้ temp แทน L และ R เพื่อจัดเก็บ subarray ชั่วคราว
ในฟังก์ชันหลัก เรากำหนดอาร์เรย์ arr ด้วย 6 อิลิเมนต์ และเรียกใช้ฟังก์ชัน mergeSort เพื่อจัดเรียง การดำเนินการโค้ดสิ้นสุดลงด้วยการพิมพ์อาร์เรย์ที่เรียงลำดับบนหน้าจอ
บทสรุป
Merge sort เป็นอัลกอริทึมที่เรียงลำดับองค์ประกอบอาร์เรย์ และใช้เทคนิคการหารและพิชิต และทำการเปรียบเทียบระหว่างองค์ประกอบต่างๆ Merge sort ใน C++ มีความซับซ้อนของเวลาเท่ากับ O(n log n) และมีประสิทธิภาพอย่างยิ่งสำหรับการเรียงลำดับอาร์เรย์ขนาดใหญ่ แม้ว่าจะต้องใช้หน่วยความจำเพิ่มเติมเพื่อจัดเก็บ subarrays ที่ผสานรวม ความเสถียรทำให้เป็นตัวเลือกยอดนิยมสำหรับการเรียงลำดับ