విషయము

• పోలిక చార్ట్
• త్వరిత క్రమబద్ధీకరణ యొక్క నిర్వచనం
• విలీనం క్రమబద్ధీకరణ యొక్క నిర్వచనం
• ముగింపు

శీఘ్ర క్రమబద్ధీకరణ మరియు విలీన క్రమబద్ధీకరణ అల్గోరిథంలు విభజన మరియు జయించే అల్గోరిథం మీద ఆధారపడి ఉంటాయి, ఇది చాలా సారూప్యంగా పనిచేస్తుంది. శీఘ్ర మరియు విలీన క్రమబద్ధీకరణ మధ్య ముందు వ్యత్యాసం ఏమిటంటే శీఘ్ర క్రమబద్ధీకరణలో పైవట్ మూలకం సార్టింగ్ కోసం ఉపయోగించబడుతుంది. మరోవైపు, విలీనం క్రమబద్ధీకరణ సార్టింగ్ చేయడానికి పైవట్ మూలకాన్ని ఉపయోగించదు.

సార్టింగ్ టెక్నిక్స్, క్విక్ సార్ట్ మరియు విలీన సార్ట్ రెండూ డివైడ్ అండ్ కాంక్వెర్ పద్దతిపై నిర్మించబడ్డాయి, దీనిలో మూలకాల సమితి విడిపోయి, పునర్వ్యవస్థీకరణ తర్వాత కలుపుతారు. శీఘ్ర క్రమబద్ధీకరణకు సాధారణంగా పెద్ద మూలకాల క్రమబద్ధీకరణ కోసం విలీన క్రమబద్ధీకరణ కంటే ఎక్కువ పోలికలు అవసరం.

1. 1. పోలిక చార్ట్
   2. నిర్వచనం
   3. కీ తేడాలు
   4. ముగింపు

పోలిక చార్ట్

పోలిక కోసం ఆధారం	త్వరిత క్రమబద్ధీకరణ	విధమైన విలీనం
శ్రేణిలోని మూలకాల విభజన	మూలకాల జాబితాను విభజించడం తప్పనిసరిగా సగానికి విభజించబడదు.	శ్రేణి ఎల్లప్పుడూ సగం (n / 2) గా విభజించబడింది.
చెత్త కేసు సంక్లిష్టత	పై2)	O (n లాగ్ n)
బాగా పనిచేస్తుంది	చిన్న శ్రేణి	ఏ రకమైన శ్రేణిలోనైనా బాగా పనిచేస్తుంది.
స్పీడ్	చిన్న డేటా సెట్ కోసం ఇతర సార్టింగ్ అల్గోరిథంల కంటే వేగంగా.	అన్ని రకాల డేటా సెట్లలో స్థిరమైన వేగం.
అదనపు నిల్వ స్థలం అవసరం	తక్కువ	మరింత
సమర్థత	పెద్ద శ్రేణుల కోసం అసమర్థమైనది.	మరింత సమర్థవంతంగా.
సార్టింగ్ పద్ధతి	అంతర్గత	బాహ్య

త్వరిత క్రమబద్ధీకరణ యొక్క నిర్వచనం

త్వరిత క్రమబద్ధీకరణ చిన్న శ్రేణుల కోసం వేగంగా ఉన్నందున సార్టింగ్ అల్గోరిథం విస్తృతంగా ఉపయోగించబడుతుంది. మూలకాల సమితిని మరింతగా విభజించడం సాధ్యం కాని వరకు పదేపదే భాగాలుగా విభజించబడింది. త్వరిత క్రమబద్ధీకరణను కూడా అంటారు విభజన మార్పిడి విధమైన. ఇది మూలకాలను విభజించడానికి ఒక కీ మూలకాన్ని (పివట్ అని పిలుస్తారు) ఉపయోగిస్తుంది. ఒక విభజన కీ మూలకం కంటే చిన్నదిగా ఉండే అంశాలను కలిగి ఉంటుంది. మరొక విభజనలో కీ మూలకం కంటే ఎక్కువ ఉన్న అంశాలు ఉన్నాయి. అంశాలు పునరావృతంగా క్రమబద్ధీకరించబడతాయి.

A అనేది శ్రేణి A, A, A, …… .., క్రమబద్ధీకరించాల్సిన n సంఖ్య యొక్క A అని అనుకుందాం. శీఘ్ర క్రమబద్ధీకరణ అల్గోరిథం క్రింది దశలను కలిగి ఉంటుంది.

1. మొదటి మూలకం లేదా ఏదైనా యాదృచ్ఛిక మూలకం కీగా ఎంచుకోబడితే, కీ = A (1) అనుకోండి.
2. “తక్కువ” పాయింటర్ రెండవ వద్ద ఉంచబడుతుంది మరియు “పైకి” పాయింటర్ శ్రేణి యొక్క చివరి మూలకం వద్ద ఉంచబడుతుంది, అనగా తక్కువ = 2 మరియు పైకి = n;
3. (A> కీ) వరకు “తక్కువ” పాయింటర్‌ను ఒక స్థానం ద్వారా పెంచండి.
4. నిరంతరం, (A <= key) వరకు “పైకి” పాయింటర్‌ను ఒక స్థానం ద్వారా తగ్గించండి.
5. A తో తక్కువ ఇంటర్‌చేంజ్ A కంటే ఎక్కువగా ఉంటే.
6. 5 వ దశలోని పరిస్థితి విఫలమయ్యే వరకు 3,4, మరియు 5 దశలను పునరావృతం చేయండి (అనగా పైకి <= తక్కువ) ఆపై కీతో A ని మార్చుకోండి.
7. కీ యొక్క ఎడమ మూలకాలు కీ కంటే చిన్నవి మరియు కీ యొక్క కుడి మూలకాలు కీ కంటే ఎక్కువగా ఉంటే, శ్రేణి రెండు ఉప-శ్రేణులుగా విభజించబడింది.
8. పై శ్రేణి మొత్తం శ్రేణి క్రమబద్ధీకరించబడే వరకు పదేపదే సబ్‌రేలకు వర్తించబడుతుంది.

   

   
   

ప్రయోజనాలు మరియు అప్రయోజనాలు

ఇది మంచి సగటు కేసు ప్రవర్తనను కలిగి ఉంటుంది. శీఘ్ర క్రమబద్ధీకరణ యొక్క నడుస్తున్న సమయ సంక్లిష్టత మంచిది, ఇది బబుల్ సార్ట్, చొప్పించడం క్రమబద్ధీకరణ మరియు ఎంపిక క్రమబద్ధీకరణ వంటి అల్గోరిథంల కంటే వేగంగా ఉంటుంది. అయినప్పటికీ, ఇది సంక్లిష్టమైనది మరియు చాలా పునరావృతమవుతుంది, ఇది పెద్ద శ్రేణులకు తగినది కాదు.

విలీనం క్రమబద్ధీకరణ యొక్క నిర్వచనం

విధమైన విలీనం బాహ్య అల్గోరిథం, ఇది విభజన మరియు జయించే వ్యూహంపై కూడా ఆధారపడి ఉంటుంది. ఒక మూలకం మాత్రమే మిగిలిపోయే వరకు మూలకాలను ఉప-శ్రేణులు (n / 2) గా విభజించారు, ఇది సార్టింగ్ సమయాన్ని గణనీయంగా తగ్గిస్తుంది. ఇది సహాయక శ్రేణిని నిల్వ చేయడానికి అదనపు నిల్వను ఉపయోగిస్తుంది. విలీన క్రమబద్ధీకరణ మూడు శ్రేణులను ఉపయోగిస్తుంది, ఇక్కడ ప్రతి సగం నిల్వ చేయడానికి రెండు ఉపయోగించబడతాయి మరియు మూడవది తుది క్రమబద్ధీకరించబడిన జాబితాను నిల్వ చేయడానికి ఉపయోగించబడుతుంది. ప్రతి శ్రేణి అప్పుడు పునరావృతమవుతుంది. చివరికి, శ్రేణి యొక్క n మూలకం పరిమాణంగా చేయడానికి సబ్‌రేలు విలీనం చేయబడతాయి. జాబితా ఎల్లప్పుడూ త్వరిత క్రమబద్ధీకరణకు భిన్నంగా సగం (n / 2) గా విభజించబడింది.

A, A, ………, A. క్రమబద్ధీకరించవలసిన మూలకాల సంఖ్య యొక్క శ్రేణిగా ఉండనివ్వండి. విలీన క్రమబద్ధీకరణ ఇచ్చిన దశలను అనుసరిస్తుంది.

1. శ్రేణి A ని సుమారు n / 2 క్రమబద్ధీకరించిన ఉప-శ్రేణిగా 2 ద్వారా విభజించండి, అంటే (A, A), (A, A), (A, A), (A, A) ఉప శ్రేణులలోని మూలకాలు తప్పనిసరిగా ఉండాలి క్రమబద్ధీకరించిన క్రమంలో ఉండండి.
2. పరిమాణం 4 యొక్క క్రమబద్ధీకరించబడిన సబ్‌రేల జాబితాను పొందడానికి ప్రతి జత జతలను కలపండి; (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A) క్రమబద్ధీకరించిన క్రమంలో కూడా సబ్‌రేలలోని అంశాలు ఉంటాయి.
3. పరిమాణం 2 యొక్క క్రమబద్ధీకరించబడిన శ్రేణి మాత్రమే ఉండే వరకు దశ 2 పదేపదే జరుగుతుంది.

   

ప్రయోజనాలు మరియు అప్రయోజనాలు

విలీన క్రమబద్ధీకరణ అల్గోరిథం సార్టింగ్‌లో పాల్గొన్న అంశాల సంఖ్యతో సంబంధం లేకుండా ఖచ్చితమైన మరియు ఖచ్చితమైన పద్ధతిలో పనిచేస్తుంది. పెద్ద డేటా సెట్‌తో కూడా ఇది బాగా పనిచేస్తుంది. అయితే, ఇది మెమరీలో ఎక్కువ భాగాన్ని వినియోగిస్తుంది.

1. విలీన క్రమబద్ధీకరణలో, శ్రేణిని కేవలం రెండు భాగాలుగా విభజించాలి (అనగా n / 2). దీనికి విరుద్ధంగా, త్వరితగతిన, జాబితాను సమాన మూలకాలుగా విభజించాల్సిన అవసరం లేదు.
2. శీఘ్ర క్రమబద్ధీకరణ యొక్క చెత్త కేసు సంక్లిష్టత O (n²) చెత్త స్థితిలో చాలా ఎక్కువ పోలికలు పడుతుంది. దీనికి విరుద్ధంగా, విలీన క్రమబద్ధీకరణకు అదే చెత్త కేసు మరియు సగటు కేసు సంక్లిష్టతలు ఉన్నాయి, అంటే O (n log n).
3. విలీన క్రమబద్ధీకరణ పెద్దది లేదా చిన్నది అయినా ఏ రకమైన డేటా సెట్‌లలోనైనా బాగా పనిచేస్తుంది. దీనికి విరుద్ధంగా, శీఘ్ర క్రమబద్ధీకరణ పెద్ద డేటాసెట్‌లతో బాగా పనిచేయదు.
4. చిన్న డేటా సెట్ల వంటి కొన్ని సందర్భాల్లో విలీనం క్రమబద్ధీకరణ కంటే శీఘ్ర క్రమబద్ధీకరణ వేగంగా ఉంటుంది.
5. విలీన క్రమబద్ధీకరణకు సహాయక శ్రేణులను నిల్వ చేయడానికి అదనపు మెమరీ స్థలం అవసరం. మరోవైపు, శీఘ్ర క్రమబద్ధీకరణకు అదనపు నిల్వ కోసం ఎక్కువ స్థలం అవసరం లేదు.
6. శీఘ్ర క్రమబద్ధీకరణ కంటే విలీన క్రమబద్ధీకరణ మరింత సమర్థవంతంగా ఉంటుంది.
7. శీఘ్ర క్రమబద్ధీకరణ అనేది అంతర్గత సార్టింగ్ పద్ధతి, ఇక్కడ క్రమబద్ధీకరించాల్సిన డేటా ప్రధాన మెమరీలో ఒక సమయంలో సర్దుబాటు చేయబడుతుంది. దీనికి విరుద్ధంగా, విలీన క్రమబద్ధీకరణ బాహ్య సార్టింగ్ పద్ధతి, దీనిలో క్రమబద్ధీకరించవలసిన డేటాను ఒకే సమయంలో మెమరీలో ఉంచలేము మరియు కొన్ని సహాయక మెమరీలో ఉంచాలి.

ముగింపు

శీఘ్ర క్రమబద్ధీకరణ వేగవంతమైన సందర్భాలు కాని కొన్ని సందర్భాల్లో అసమర్థంగా ఉంటుంది మరియు విలీన క్రమబద్ధీకరణతో పోలిస్తే చాలా పోలికలను కూడా చేస్తుంది. విలీన క్రమబద్ధీకరణకు తక్కువ పోలిక అవసరం అయినప్పటికీ, అదనపు శ్రేణిని నిల్వ చేయడానికి దీనికి 0 (n) అదనపు మెమరీ స్థలం అవసరం, అయితే శీఘ్ర క్రమబద్ధీకరణకు O (log n) స్థలం అవసరం.