รวมอาร์เรย์ที่เรียงลำดับแล้วสองอันอย่างรวดเร็วด้วย std::merge() ใน C++ STL

ในบทความนี้ เราจะอภิปรายว่าจะรวมอาร์เรย์ที่เรียงลำดับแล้วสองอันอย่างรวดเร็วอย่างไรโดยใช้ฟังก์ชัน std::merge() ใน C++ STL

ก่อนแก้ปัญหา มาพูดถึง std::merge() ใน C++ STL ก่อน

std::merge() คืออะไร?

ฟังก์ชัน std::merge() เป็นฟังก์ชันสำเร็จรูปใน C++ STL ซึ่งถูกกำหนดในไฟล์หัวข้อ <algorithm> merge() ใช้สำหรับรวมสองช่วงหรือลำดับที่เรียงลำดับแล้ว ฟังก์ชันนี้รวมสองช่วงที่เรียงลำดับแล้วเพื่อทำให้เป็นช่วงเดียวที่เรียงลำดับ องค์ประกอบทั้งหมดถูกเปรียบเทียบโดยใช้ตัวดำเนินการน้อยกว่า (<) ดังนั้นช่วงที่สามก็จะถูกเรียงลำดับด้วยตัวมันเอง

เราจะรวมอาร์เรย์ที่เรียงลำดับแล้วสองอันอย่างรวดเร็วด้วย std::merge() อย่างไร?

เราได้รับอาร์เรย์ที่เรียงลำดับแล้วสองอันคือ arr1[] และ arr2[] และงานคือรวมอาร์เรย์ที่เรียงลำดับแล้วสองอันนั้นและเก็บไว้ในอีกอาร์เรย์ว่างหนึ่งซึ่งอาจเป็น arr3[] โดยใช้ฟังก์ชัน merge() ที่มีอยู่ใน C++ STL

• ก่อนอื่น เราจะคำนวณขนาดของอาร์เรย์ทั้งสอง arr[size_arr] และ brr[size_brr] และกำหนดอาร์เรย์ที่สามซึ่งขนาดเป็นผลรวมของขนาดของทั้งสองอาร์เรย์ final[size_arr+size_brr]

• จากนั้นเราจะรวมสองอาร์เรย์เข้าไปในอาร์เรย์ที่สามโดยใช้ฟังก์ชัน merge() เหมือน merge(arr, (arr + size_arr), brr, (brr + size_brr), final);

ตัวอย่าง

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {1, 2, 3};
    int size_arr = sizeof(arr)/sizeof(arr[0]);
    int brr[] = {4, 5, 6};
    int size_brr = sizeof(brr)/sizeof(brr[0]);
    int final[size_arr + size_brr];
    merge(arr, (arr + size_arr), brr, (brr + size_brr), final);
    cout << "Final array after merging the elements is: ";
    for (int i = 0; i < (size_brr + size_arr); i++)
        cout << final[i] << " ";
    return 0;
}

ผลลัพธ์

Final array after merging the elements is: 1 2 3 4 5 6