ຜະສົມຜະສານ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ Boomerang ການຄ້າ Goldman Sachs Grofers Microsoft Oracle Paytm Qualcomm Snapdeal ບໍລິສັດເປົ້າ ໝາຍ
ແບ່ງແລະເອົາຊະນະ ຮຽງລໍາດັບ

ການຮວບຮວມເຂົ້າກັນແມ່ນຫຍັງ?

ຜະສົມຜະສານ ເປັນ ຂັ້ນຕອນການເອີ້ນຄືນ. ມັນກໍ່ແມ່ນກ ແບ່ງແລະເອົາຊະນະ ສູດການຄິດໄລ່. ຕອນນີ້ພວກເຮົາຕ້ອງຮູ້ວ່າການແບ່ງແຍກແລະເອົາຊະນະລະບົບ algorithm ແມ່ນຫຍັງ? ມັນແມ່ນປະເພດຂອງຂັ້ນຕອນໃນການທີ່ພວກເຮົາແບ່ງປັນບັນຫາອອກເປັນໂຄງການຍ່ອຍແລະແບ່ງພວກມັນຈົນກວ່າພວກເຮົາຈະເຫັນຮູບແບບຍ່ອຍທີ່ຖືກແກ້ໄຂທີ່ສັ້ນທີ່ສຸດ. ໂດຍການລວມເອົາເຄື່ອງຍ່ອຍຍ່ອຍທີ່ຖືກແກ້ໄຂທີ່ສັ້ນທີ່ສຸດພວກເຮົາຊອກຫາວິທີແກ້ໄຂບັນຫາໃຫຍ່ / ຕົ້ນຕໍ. ໃຫ້ຂອງເບິ່ງ ຂັ້ນຕອນວິທີ ສຳ ລັບ merge_sort.

ລະບົບວິເຄາະ

ຂັ້ນຕອນ: 1 ແບ່ງປັນບັນຫາອອກເປັນ 2 ໂຄງການຍ່ອຍ.

ຂັ້ນຕອນ: 2 ເຄື່ອງຍ່ອຍຍ່ອຍເອີ້ນຫາແບບບັງຄັບຈົນກວ່າມັນຈະຮອດຂະ ໜາດ ຂັ້ນຕ່ ຳ ສຸດ (ເຄື່ອງມືຍ່ອຍທີ່ຖືກແກ້ໄຂ).

ຂັ້ນຕອນ: 3 ຜະສົມຜະສານເຄື່ອງ ໝາຍ ຍ່ອຍທີ່ຖືກແກ້ໄຂ.

ຕອນນີ້, ຍ້າຍໄປທີ່ຕົວຢ່າງ ສຳ ລັບ ເຂົ້າໃຈວິທີການເຮັດວຽກແບບນີ້?

ຄໍາອະທິບາຍສໍາລັບ ຜະສົມຜະສານ

ຂໍໃຫ້ພວກເຮົາມີແຖວ A ທີ່ມີເລກ N ຢູ່ໃນຊຸດທີ່ບໍ່ຖືກຄັດເລືອກ. A = {9,1,4,2,5,3,7,2,6,17}

ຜະສົມຜະສານ

ຜະສົມຜະສານ

ຜະສົມຜະສານ

ຜະສົມຜະສານ

ຜະສົມຜະສານ

ຜະສົມຜະສານ

ໃນຂັ້ນຕອນທີ 8 ພວກເຮົາໄດ້ຮັບຂັ້ນສຸດທ້າຍ ຈັດລຽງຕາມແຖວ ການ ນຳ ໃຊ້ລະບົບ algorithm 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 * log N) ບ່ອນທີ່ N ແມ່ນຕົວເລກທັງ ໝົດ ໃນປະຈຸບັນໃນແຖວ. ການພົວພັນກັບການເກີດຂື້ນຂອງການຈັດຕັ້ງປະຕິບັດຂ້າງເທິງແມ່ນ T (N) = 2 * T (N / 2) + O (1).

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ໃນທີ່ນີ້ພວກເຮົາບໍ່ໄດ້ສ້າງພື້ນທີ່ພິເສດໃດໆຍົກເວັ້ນແຕ່ອາເລທີ່ຈັດໃຫ້ດັ່ງນັ້ນ, ຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນ O (1) ເຊິ່ງຄົງທີ່.

ປະເພດຂອງສູດການຄິດໄລ່ທີ່ ນຳ ໃຊ້

ໃນທີ່ນີ້ພວກເຮົາໃຊ້ວິທີການແບ່ງແຍກແລະເອົາຊະນະວິທີການເພື່ອແກ້ໄຂບັນຫາການໂຮມເຂົ້າກັນ.

ເອກະສານ