ผสานการเรียง


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน แอปเปิล บูมเมอแรงคอมเมิร์ซ แซคส์โกลด์แมน Grofers ไมโครซอฟท์ คำพยากรณ์ Paytm วอลคอมม์ Snapdeal บริษัท เป้าหมาย
หารและพิชิต การเรียงลำดับ

merge sort คืออะไร?

ผสานการเรียง คือ ขั้นตอนการเรียกซ้ำ. มันยังเป็น แบ่งแยกและพิชิต อัลกอริทึม ตอนนี้เราต้องรู้แล้วว่าอัลกอริทึมการแบ่งและพิชิตคืออะไร? เป็นขั้นตอนประเภทหนึ่งที่เราแบ่งปัญหาออกเป็นปัญหาย่อยและแบ่งปัญหาเหล่านั้นจนกว่าเราจะพบปัญหาย่อยที่แก้ไขได้สั้นที่สุด ด้วยการรวมปัญหาย่อยที่แก้ไขแล้วที่สั้นที่สุดเราจะพบวิธีแก้ปัญหาใหญ่ / ปัญหาหลัก มาดู ขั้นตอนวิธี สำหรับ merge_sort

ขั้นตอนวิธี

ขั้นตอนที่: 1 แบ่งปัญหาออกเป็น 2 ปัญหาย่อย

ขั้นตอนที่: 2 ปัญหาย่อยจะเรียกซ้ำจนกว่าจะถึงขนาดต่ำสุด (แก้ไขปัญหาย่อย)

ขั้นตอนที่: 3 รวมปัญหาย่อยที่แก้ไขแล้ว

ตอนนี้ย้ายไปที่ตัวอย่างสำหรับ เข้าใจว่าอัลกอริทึมนี้ทำงานอย่างไร?

คำอธิบายสำหรับ ผสานการเรียง

สมมติว่าเรามีอาร์เรย์ A ที่มีหมายเลข N ไม่เรียงลำดับ ก = {9,1,4,2,5,3,7,2,6,17}

ผสานการเรียง

ผสานการเรียง

ผสานการเรียง

ผสานการเรียง

ผสานการเรียง

ผสานการเรียง

ในขั้นตอนที่ 8 เราได้เข้ารอบชิงชนะเลิศ อาร์เรย์ที่จัดเรียง โดยใช้อัลกอริทึม merge_sort

การใช้งานสำหรับการเรียงลำดับการผสาน 

/*C++ Implementation of Merge Sort*/ 
#include<bits/stdc++.h>
#define max_v 100000
using namespace std;
void add_subproblems(int a[],int l,int mid,int r)
{
    int start_1=l;//starting index of subproblem 1;
    int start_2=mid+1;//strating index of subproblem 2;
    int store=l;//used to store the no in array a with O(1) space complexity. 
    /*compare the element from begining of both subproblems and choose the minimum element from them
      and increment the index wrt minimum value by 1.*/
    while(start_1<=mid&&start_2<=r)
    {
        if((a[start_1]%max_v)<=(a[start_2]%max_v))
        {
            a[store]+=(a[start_1]%max_v)*max_v;
            store++;
            start_1++;
        }
        else
        {
            a[store]+=(a[start_2]%max_v)*max_v;
            store++;
            start_2++;
        }
    }
    /*if some elements are remaining in subproblem 1*/
    while(start_1<=mid)
    {
        a[store]+=(a[start_1]%max_v)*max_v;
        store++;
        start_1++; 
    }
    /*if some elements are remaining in subproblem 2*/
    while(start_2<=r)
    {
        a[store]+=(a[start_2]%max_v)*max_v;
        store++;
        start_2++;
    }
    /*now change the elements into their oroginal values*/
    for(int i=l;i<=r;i++)
    {
        a[i]/=max_v;
    }
}
void merge(int a[],int l,int r)
{
    if(l<r)
    {
        int mid=(l+r)/2;
        merge(a,l,mid);
        merge(a,mid+1,r);
        add_subproblems(a,l,mid,r);
    }
}
int main() 
{ 
    int number;
    /*total numbers which we want to sort*/
    cin>>number;
    int a[number];
    /*take input*/
    for(int i=0;i<number;i++)
    {
        cin>>a[i];
    }
    cout<<"Array before sorting: ";
    /*print the array*/
    for(int i=0;i<number;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<"\n";
    /*call merge function*/
    merge(a,0,number-1);
    cout<<"Array after sorting: ";
    /*print the array*/
    for(int i=0;i<number;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<"\n";
    return 0; 
}
10
9 1 4 2 5 3 7 2 6 17
Array before sorting: 9 1 4 2 5 3 7 2 6 17 
Array after sorting: 1 2 2 3 4 5 6 7 9 17

ความซับซ้อนของเวลา

O (N * บันทึก N) โดยที่ N คือจำนวนทั้งหมดที่มีอยู่ในอาร์เรย์ ความสัมพันธ์การเกิดซ้ำของการใช้งานข้างต้นคือ T (N) = 2 * T (N / 2) + O (1).

ความซับซ้อนของอวกาศ

O (1) ที่นี่เราไม่ได้สร้างช่องว่างเพิ่มเติมยกเว้นอาร์เรย์ที่กำหนดดังนั้นความซับซ้อนของพื้นที่คือ O (1) ซึ่งเป็นค่าคงที่

ประเภทของอัลกอริทึมที่ใช้

ที่นี่เราใช้วิธีหารและพิชิตเพื่อแก้ปัญหาการเรียงลำดับการผสาน

อ้างอิง