విషయ సూచిక
- పరిచయం
- C++లో విలీన క్రమబద్ధీకరణ అంటే ఏమిటి
- డివైడ్ అండ్ కాంకర్ అప్రోచ్
- క్రమబద్ధీకరణ అల్గారిథమ్‌ను విలీనం చేయండి
- C++లో విలీన క్రమబద్ధీకరణ అమలు
- ముగింపు
1. పరిచయం
కంప్యూటర్ సైన్స్‌లో సార్టింగ్ అల్గారిథమ్‌లు డేటాను ఆరోహణ లేదా అవరోహణ క్రమంలో అమర్చడానికి ఉపయోగిస్తారు. విభిన్న లక్షణాలతో బహుళ సార్టింగ్ అల్గారిథమ్‌లు అందుబాటులో ఉన్నాయి. శ్రేణులను క్రమబద్ధీకరించగల C++లో మెర్జ్ సార్ట్ ఒకటి.
2. C++లో మెర్జ్ సార్ట్ అంటే ఏమిటి
విలీన క్రమబద్ధీకరణ అనేది శ్రేణి యొక్క మూలకాలను అమర్చగల విభజన మరియు జయించే సాంకేతికతను ఉపయోగిస్తుంది. ఇది C++లోని మూలకాల జాబితాను కూడా క్రమబద్ధీకరించగలదు. ఇది ఇన్‌పుట్‌ను రెండు భాగాలుగా విభజిస్తుంది, ప్రతి సగాన్ని స్వతంత్రంగా క్రమబద్ధీకరిస్తుంది, ఆపై వాటిని సరైన క్రమంలో విలీనం చేస్తుంది.
3. డివైడ్ అండ్ కాంకర్ అప్రోచ్
సార్టింగ్ అల్గోరిథం డివైడ్ అండ్ కాంక్వెర్ స్ట్రాటజీని వర్తింపజేస్తుంది, ఇది ఇన్‌పుట్ శ్రేణిని చిన్న సబ్‌రేలుగా విభజించడం, వాటిని విడిగా పరిష్కరించడం, ఆపై ఫలితాలను విలీనం చేయడం ద్వారా క్రమబద్ధీకరించబడిన అవుట్‌పుట్‌ను ఉత్పత్తి చేస్తుంది. విలీన క్రమబద్ధీకరణ విషయంలో, ప్రతి అర్ధ భాగంలో ఒక మూలకం మాత్రమే మిగిలిపోయే వరకు శ్రేణి పునరావృతంగా రెండు భాగాలుగా విభజించబడింది.
4. క్రమబద్ధీకరణ అల్గోరిథం విలీనం
విలీన క్రమబద్ధీకరణ అల్గోరిథం రెండు ప్రధాన దశలను కలిగి ఉంటుంది: విభజించడం మరియు విలీనం చేయడం. దశలు క్రింది విధంగా ఉన్నాయి:
4.1 విభజించండి
విలీన క్రమబద్ధీకరణ అల్గోరిథం ఒక శ్రేణిలోని మూలకాలను క్రమబద్ధీకరించడానికి విభజించి-విజయించే వ్యూహాన్ని అనుసరిస్తుంది.
- అల్గారిథమ్‌లోని మొదటి దశ శ్రేణి మూలకాలను తనిఖీ చేస్తుంది. ఇది ఒక మూలకాన్ని కలిగి ఉంటే, అది ఇప్పటికే క్రమబద్ధీకరించబడినదిగా పరిగణించబడుతుంది మరియు అల్గోరిథం ఎటువంటి మార్పు లేకుండా అదే శ్రేణిని అందిస్తుంది.
- శ్రేణి ఒకటి కంటే ఎక్కువ మూలకాలను కలిగి ఉన్నట్లయితే, అల్గోరిథం దానిని రెండు భాగాలుగా విభజించడానికి కొనసాగుతుంది: ఎడమ సగం మరియు కుడి సగం.
- విలీన క్రమబద్ధీకరణ అల్గోరిథం శ్రేణి యొక్క ఎడమ మరియు కుడి భాగాలకు పునరావృతంగా వర్తించబడుతుంది, వాటిని ప్రభావవంతంగా చిన్న సబ్‌రేలుగా విభజించి వాటిని ఒక్కొక్కటిగా క్రమబద్ధీకరిస్తుంది.
- సబ్‌రేలు ఒక్కొక్క మూలకాన్ని మాత్రమే కలిగి ఉండే వరకు ఈ పునరావృత ప్రక్రియ కొనసాగుతుంది (దశ 1 ప్రకారం), ఆ సమయంలో అవి తుది, క్రమబద్ధీకరించబడిన అవుట్‌పుట్ శ్రేణిని ఉత్పత్తి చేయడానికి విలీనం చేయబడతాయి.
4.2 విలీనం
ఇప్పుడు మనం శ్రేణులను విలీనం చేసే దశలను చూస్తాము:
- విలీన క్రమబద్ధీకరణ అల్గోరిథం కోసం మొదటి దశ ఖాళీ శ్రేణిని సృష్టించడం.
- ఇన్‌పుట్ శ్రేణి యొక్క ఎడమ మరియు కుడి భాగాల యొక్క మొదటి మూలకాలను పోల్చడానికి అల్గోరిథం కొనసాగుతుంది.
- రెండు మూలకాలలో చిన్నవి కొత్త శ్రేణికి జోడించబడతాయి మరియు ఇన్‌పుట్ శ్రేణి యొక్క సంబంధిత సగం నుండి తీసివేయబడతాయి.
- 2-3 దశల్లో ఒకటి ఖాళీ అయ్యే వరకు పునరావృతమవుతుంది.
- ఖాళీ కాని సగంలో మిగిలి ఉన్న ఏవైనా మూలకాలు కొత్త శ్రేణికి జోడించబడతాయి.
- ఫలిత శ్రేణి ఇప్పుడు పూర్తిగా క్రమబద్ధీకరించబడింది మరియు విలీన క్రమబద్ధీకరణ అల్గోరిథం యొక్క తుది అవుట్‌పుట్‌ను సూచిస్తుంది.
5. C++లో విలీన క్రమబద్ధీకరణ అమలు
C++లో విలీన క్రమాన్ని అమలు చేయడానికి రెండు వేర్వేరు పద్ధతులు అనుసరించబడతాయి. రెండు పద్ధతుల యొక్క సమయ సంక్లిష్టత సమానంగా ఉంటుంది, అయితే వాటి తాత్కాలిక ఉపబరేల వినియోగం భిన్నంగా ఉంటుంది.
C++లో విలీన క్రమబద్ధీకరణ కోసం మొదటి పద్ధతి రెండు తాత్కాలిక సబ్‌రేలను ఉపయోగిస్తుంది, రెండవది ఒకదాన్ని మాత్రమే ఉపయోగిస్తుంది. మొదటి పద్ధతిలోని రెండు తాత్కాలిక ఉపబారుల మొత్తం పరిమాణం రెండవ పద్ధతిలో అసలైన శ్రేణి పరిమాణానికి సమానంగా ఉంటుంది, కాబట్టి స్థలం సంక్లిష్టత స్థిరంగా ఉంటుంది.
విధానం 1 - రెండు టెంప్ సబ్‌రేలను ఉపయోగించడం
రెండు తాత్కాలిక సబ్‌రేలను ఉపయోగించే పద్ధతి 1ని ఉపయోగించి C++లో విలీన క్రమబద్ధీకరణ కోసం ఇక్కడ ఒక ఉదాహరణ ప్రోగ్రామ్ ఉంది:
#నేమ్‌స్పేస్ stdని ఉపయోగిస్తోంది ;
శూన్యం విలీనం ( int అరె [ ] , int ఎల్ , int m , int ఆర్ )
{
int n1 = m - ఎల్ + 1 ;
int n2 = ఆర్ - m ;
int ఎల్ [ n1 ] , ఆర్ [ n2 ] ;
కోసం ( int i = 0 ; i < n1 ; i ++ )
ఎల్ [ i ] = అరె [ ఎల్ + i ] ;
కోసం ( int జె = 0 ; జె < n2 ; జె ++ )
ఆర్ [ జె ] = అరె [ m + 1 + జె ] ;
int i = 0 , జె = 0 , కె = ఎల్ ;
అయితే ( i < n1 && జె < n2 ) {
ఉంటే ( ఎల్ [ i ] <= ఆర్ [ జె ] ) {
అరె [ కె ] = ఎల్ [ i ] ;
i ++;
}
లేకపోతే {
అరె [ కె ] = ఆర్ [ జె ] ;
జె ++;
}
కె ++;
}
అయితే ( i < n1 ) {
అరె [ కె ] = ఎల్ [ i ] ;
i ++;
కె ++;
}
అయితే ( జె < n2 ) {
అరె [ కె ] = ఆర్ [ జె ] ;
జె ++;
కె ++;
}
}
శూన్యం విలీనం క్రమబద్ధీకరించు ( int అరె [ ] , int ఎల్ , int ఆర్ )
{
ఉంటే ( ఎల్ < ఆర్ ) {
int m = ఎల్ + ( ఆర్ - ఎల్ ) / 2 ;
విలీనం క్రమబద్ధీకరించు ( అరె , ఎల్ , m ) ;
విలీనం క్రమబద్ధీకరించు ( అరె , m + 1 , ఆర్ ) ;
విలీనం ( అరె , ఎల్ , m , ఆర్ ) ;
}
}
int ప్రధాన ( )
{
int అరె [ ] = { 12 , పదకొండు , 13 , 5 , 6 , 7 } ;
int arr_size = పరిమాణం ( అరె ) / పరిమాణం ( అరె [ 0 ] ) ;
కోట్ << 'ఇచ్చిన శ్రేణి \n ' ;
కోసం ( int i = 0 ; i < arr_size ; i ++ )
కోట్ << అరె [ i ] << '' ;
విలీనం క్రమబద్ధీకరించు ( అరె , 0 , arr_size - 1 ) ;
కోట్ << ' \n క్రమబద్ధీకరించబడిన శ్రేణి \n ' ;
కోసం ( int i = 0 ; i < arr_size ; i ++ )
కోట్ << అరె [ i ] << '' ;
తిరిగి 0 ;
}
ఈ ప్రోగ్రామ్‌లో, విలీన ఫంక్షన్ మూడు ఆర్గ్యుమెంట్‌లను తీసుకుంటుంది arr, l మరియు r, ఇది క్రమబద్ధీకరించాల్సిన శ్రేణిని సూచిస్తుంది మరియు విలీనం చేయాల్సిన సబ్‌రే యొక్క సూచికలను చూపుతుంది. ఫంక్షన్ మొదట రెండు సబ్‌రేల పరిమాణాలను విలీనం చేస్తుంది, ఆపై ఈ సబ్‌రేల మూలకాలను నిల్వ చేయడానికి రెండు తాత్కాలిక సబ్‌రేలను L మరియు R సృష్టిస్తుంది. ఇది L మరియు R లోని మూలకాలను సరిపోల్చుతుంది మరియు వాటిని పేరు పెట్టబడిన అసలు శ్రేణిలో విలీనం చేస్తుంది అరె ఆరోహణ క్రమంలో.
సబ్‌రేలో ఒక మూలకం మాత్రమే మిగిలిపోయే వరకు శ్రేణిని పునరావృతంగా రెండు భాగాలుగా విభజించడానికి విలీనం మరియు జయించే సాంకేతికత మెర్జ్‌సార్ట్ ఫంక్షన్ ద్వారా ఉపయోగించబడుతుంది. ఇది రెండు సబ్‌రేలను క్రమబద్ధీకరించిన సబ్‌రేలో విలీనం చేస్తుంది. ఫంక్షన్ పూర్తి శ్రేణిని క్రమబద్ధీకరించకపోతే సబ్‌రేలను విలీనం చేయడం కొనసాగుతుంది.
ప్రధాన ఫంక్షన్‌లో, మేము 6 మూలకాలతో అర్రే arrని నిర్వచించాము మరియు దానిని క్రమబద్ధీకరించడానికి mergeSort ఫంక్షన్‌ని కాల్ చేస్తాము. కోడ్ చివరిలో, క్రమబద్ధీకరించబడిన శ్రేణి ముద్రించబడుతుంది.
విధానం 2 - ఒక టెంప్ సుబారేని ఉపయోగించడం
పద్ధతి 2ని ఉపయోగించి C++లో విలీన క్రమబద్ధీకరణ కోసం ఇక్కడ ఒక ఉదాహరణ ప్రోగ్రామ్ ఉంది, ఇది ఒకే తాత్కాలిక ఉపబరేని ఉపయోగిస్తుంది:
#నేమ్‌స్పేస్ stdని ఉపయోగిస్తోంది ;
శూన్యం విలీనం ( int అరె [ ] , int ఎల్ , int m , int ఆర్ )
{
int i , జె , కె ;
int n1 = m - ఎల్ + 1 ;
int n2 = ఆర్ - m ;
// తాత్కాలిక సబ్‌రేలను సృష్టించండి
int ఎల్ [ n1 ] , ఆర్ [ n2 ] ;
// డేటాను సబ్‌రేలకు కాపీ చేయండి
కోసం ( i = 0 ; i < n1 ; i ++ )
ఎల్ [ i ] = అరె [ ఎల్ + i ] ;
కోసం ( జె = 0 ; జె < n2 ; జె ++ )
ఆర్ [ జె ] = అరె [ m + 1 + జె ] ;
// తాత్కాలిక సబ్‌రేలను తిరిగి అసలు శ్రేణిలోకి విలీనం చేయండి
i = 0 ;
జె = 0 ;
కె = ఎల్ ;
అయితే ( i < n1 && జె < n2 ) {
ఉంటే ( ఎల్ [ i ] <= ఆర్ [ జె ] ) {
అరె [ కె ] = ఎల్ [ i ] ;
i ++;
}
లేకపోతే {
అరె [ కె ] = ఆర్ [ జె ] ;
జె ++;
}
కె ++;
}
// L[] యొక్క మిగిలిన మూలకాలను కాపీ చేయండి
అయితే ( i < n1 ) {
అరె [ కె ] = ఎల్ [ i ] ;
i ++;
కె ++;
}
// R[] యొక్క మిగిలిన మూలకాలను కాపీ చేయండి
అయితే ( జె < n2 ) {
అరె [ కె ] = ఆర్ [ జె ] ;
జె ++;
కె ++;
}
}
శూన్యం విలీనం క్రమబద్ధీకరించు ( int అరె [ ] , int ఎల్ , int ఆర్ )
{
ఉంటే ( ఎల్ < ఆర్ ) {
int m = ఎల్ + ( ఆర్ - ఎల్ ) / 2 ;
// ఎడమ మరియు కుడి భాగాలను పునరావృతంగా క్రమబద్ధీకరించండి
విలీనం క్రమబద్ధీకరించు ( అరె , ఎల్ , m ) ;
విలీనం క్రమబద్ధీకరించు ( అరె , m + 1 , ఆర్ ) ;
// క్రమబద్ధీకరించబడిన రెండు భాగాలను విలీనం చేయండి
విలీనం ( అరె , ఎల్ , m , ఆర్ ) ;
}
}
int ప్రధాన ( )
{
int అరె [ ] = { 12 , పదకొండు , 13 , 5 , 6 , 7 } ;
int arr_size = పరిమాణం ( అరె ) / పరిమాణం ( అరె [ 0 ] ) ;
కోట్ << 'ఇచ్చిన శ్రేణి \n ' ;
కోసం ( int i = 0 ; i < arr_size ; i ++ )
కోట్ << అరె [ i ] << '' ;
విలీనం క్రమబద్ధీకరించు ( అరె , 0 , arr_size - 1 ) ;
కోట్ << ' \n క్రమబద్ధీకరించబడిన శ్రేణి \n ' ;
కోసం ( int i = 0 ; i < arr_size ; i ++ )
కోట్ << అరె [ i ] << '' ;
తిరిగి 0 ;
}
ఈ ప్రోగ్రామ్ మునుపటి మాదిరిగానే ఉంది, కానీ రెండు తాత్కాలిక ఉపబారులు L మరియు Rని ఉపయోగించకుండా, ఇది ఒకే తాత్కాలిక ఉపబరే టెంప్‌ని ఉపయోగిస్తుంది. విలీన ఫంక్షన్ మునుపటి మాదిరిగానే పని చేస్తుంది, అయితే డేటాను L మరియు Rకి కాపీ చేయడానికి బదులుగా, అది టెంప్‌కి కాపీ చేస్తుంది. ఇది తాత్కాలిక శ్రేణి మూలకాలను తిరిగి దానిలోకి విలీనం చేస్తుంది అరె ఇది అసలు శ్రేణి.
mergeSort ఫంక్షన్ మునుపటి మాదిరిగానే ఉంటుంది, ఇది తాత్కాలిక సబ్‌రేను నిల్వ చేయడానికి L మరియు R బదులుగా టెంప్‌ని ఉపయోగిస్తుంది.
ప్రధాన ఫంక్షన్‌లో, మేము 6 మూలకాలతో అర్రే arrని నిర్వచించాము మరియు దానిని క్రమబద్ధీకరించడానికి mergeSort ఫంక్షన్‌ని కాల్ చేస్తాము. స్క్రీన్‌పై క్రమబద్ధీకరించబడిన శ్రేణిని ముద్రించడం ద్వారా కోడ్ అమలు ముగుస్తుంది.
ముగింపు
విలీన క్రమబద్ధీకరణ అనేది శ్రేణి మూలకాలను క్రమబద్ధీకరించే అల్గోరిథం, మరియు ఇది విభజించు మరియు జయించే సాంకేతికతను ఉపయోగిస్తుంది మరియు మూలకాల మధ్య పోలికలను చేస్తుంది. C++లో విలీన క్రమానికి O(n log n) యొక్క సమయ సంక్లిష్టత ఉంటుంది మరియు పెద్ద శ్రేణులను క్రమబద్ధీకరించడానికి ఇది ప్రభావవంతంగా ఉంటుంది. విలీనమైన సబ్‌రేలను నిల్వ చేయడానికి దీనికి అదనపు మెమరీ అవసరం అయినప్పటికీ, దాని స్థిరత్వం దానిని సార్టింగ్‌కు ప్రముఖ ఎంపికగా చేస్తుంది.