చొప్పించే క్రమబద్ధీకరణ సమయం సంక్లిష్టత

కింది సంఖ్యలను పరిగణించండి:

50 60 30 10 80 70 20 40

ఈ జాబితాను ఆరోహణ క్రమంలో క్రమబద్ధీకరించినట్లయితే, ఇది ఇలా ఉంటుంది:

10 20 30 40 50 60 70 80

ఇది అవరోహణ క్రమంలో క్రమబద్ధీకరించబడితే, అది ఇలా ఉంటుంది:

80 70 60 50 40 30 20 10

చొప్పించే క్రమబద్ధీకరణ అనేది జాబితాను ఆరోహణ క్రమంలో లేదా అవరోహణ క్రమంలో క్రమబద్ధీకరించడానికి ఉపయోగించే సార్టింగ్ అల్గోరిథం. ఈ కథనం ఆరోహణ క్రమంలో క్రమబద్ధీకరణతో మాత్రమే వ్యవహరిస్తుంది. అవరోహణ క్రమంలో క్రమబద్ధీకరించడం ఈ పత్రంలో ఇవ్వబడిన అదే తర్కాన్ని అనుసరిస్తుంది. ఈ వ్యాసం యొక్క లక్ష్యం చొప్పించే క్రమాన్ని వివరించడం. ప్రోగ్రామింగ్ C లో క్రింది ఉదాహరణలో చేయబడుతుంది. చొప్పించే క్రమాన్ని ఒక శ్రేణిని ఉపయోగించి ఇక్కడ వివరించబడింది.

చొప్పించే క్రమబద్ధీకరణ కోసం అల్గోరిథం

క్రమబద్ధీకరించని జాబితా ఇవ్వబడింది. అదే జాబితాను ఉపయోగించి జాబితాను ఆరోహణ క్రమంలో క్రమబద్ధీకరించడం లక్ష్యం. క్రమబద్ధీకరించని శ్రేణిని అదే శ్రేణిని ఉపయోగించి క్రమబద్ధీకరించడం అనేది స్థానంలో క్రమబద్ధీకరించడం అని చెప్పబడింది. సున్నా ఆధారిత ఇండెక్సింగ్ ఇక్కడ ఉపయోగించబడుతుంది. దశలు క్రింది విధంగా ఉన్నాయి:

• • జాబితా మొదటి నుండి స్కాన్ చేయబడింది.
  • స్కానింగ్ జరుగుతున్నప్పుడు, దాని ముందున్న సంఖ్య కంటే తక్కువ సంఖ్య దాని ముందున్నదానితో మార్చబడుతుంది.
  • ఈ ఇచ్చిపుచ్చుకోవడం ఇకపై మారడం సాధ్యం కానంత వరకు జాబితాతో పాటు కొనసాగుతుంది.
  • స్కానింగ్ ముగింపుకు చేరుకున్నప్పుడు, సార్టింగ్ పూర్తవుతుంది.

చొప్పించే క్రమబద్ధీకరణ దృష్టాంతం

సమయ సంక్లిష్టతతో వ్యవహరించేటప్పుడు, ఇది సాధారణంగా పరిగణించబడే చెత్త కేసు. మునుపటి జాబితా కోసం చెత్త ఏర్పాటు:

80 70 60 50 40 30 20 10

సున్నా నుండి 7 వరకు సూచికలతో ఎనిమిది మూలకాలు ఉన్నాయి.

ఇండెక్స్ జీరో వద్ద, స్కానింగ్ 80కి వెళుతుంది. ఇది ఒక కదలిక. ఈ ఒక్క ఉద్యమం ఒక ఆపరేషన్. ఇప్పటివరకు మొత్తం ఒక ఆపరేషన్ ఉంది (ఒక కదలిక, పోలిక లేదు మరియు స్వాప్ లేదు). ఫలితం:

| 80 70 60 50 40 30 20 10

ఇండెక్స్ వన్ వద్ద, 70కి కదలిక ఉంది. 80తో పోల్చితే 70. 70 మరియు 80 మార్పిడి చేయబడ్డాయి. ఒక ఉద్యమం ఒక ఆపరేషన్. ఒక పోలిక కూడా ఒక ఆపరేషన్. ఒక స్వాప్ కూడా ఒక ఆపరేషన్. ఈ విభాగం మూడు కార్యకలాపాలను అందిస్తుంది. ఇప్పటివరకు మొత్తం నాలుగు ఆపరేషన్లు ఉన్నాయి (1 + 3 = 4). ఫలితం క్రింది విధంగా ఉంది:

70 | 80 60 50 40 30 20 10

ఇండెక్స్ రెండు వద్ద, 60కి కదలిక ఉంది. 60ని 80తో పోల్చారు, తర్వాత 60 మరియు 80 మార్చబడతాయి. 60ని 70తో పోల్చారు, ఆపై 60 మరియు 70 మార్చబడతాయి. ఒక ఉద్యమం ఒక ఆపరేషన్. రెండు పోలికలు రెండు ఆపరేషన్లు. రెండు మార్పిడులు రెండు కార్యకలాపాలు. ఈ విభాగం ఐదు కార్యకలాపాలను అందిస్తుంది. ఇప్పటివరకు మొత్తం తొమ్మిది ఆపరేషన్లు ఉన్నాయి (4 + 5 = 9). ఫలితం క్రింది విధంగా ఉంది:

60 70 | 80 50 40 30 20 10

ఇండెక్స్ మూడు వద్ద, 50కి కదలిక ఉంది. 50ని 80తో పోల్చారు, తర్వాత 50 మరియు 80 మార్చబడతాయి. 50ని 70తో పోల్చారు, ఆ తర్వాత 50 మరియు 70 మార్చబడతాయి. 50ని 60తో పోల్చారు, ఆ తర్వాత 50 మరియు 60 మార్చబడతాయి. ఒక ఉద్యమం ఒక ఆపరేషన్. మూడు పోలికలు మూడు ఆపరేషన్లు. మూడు మార్పిడులు మూడు కార్యకలాపాలు. ఈ విభాగం ఏడు కార్యకలాపాలను అందిస్తుంది. ఇప్పటివరకు మొత్తం పదహారు ఆపరేషన్లు ఉన్నాయి (9 + 7 = 16). ఫలితం క్రింది విధంగా ఉంది:

50 60 70 | 80 40 30 20 10

ఇండెక్స్ నాలుగు వద్ద, 40కి కదలిక ఉంది. 40ని 80తో పోల్చారు, తర్వాత 40 మరియు 80 మార్చబడతాయి. 40ని 70తో పోల్చారు, ఆపై 40 మరియు 70 మార్చబడతాయి. 40ని 60తో పోల్చారు, ఆ తర్వాత 40 మరియు 60 మార్చబడతాయి. 40ని 50తో పోల్చారు, ఆ తర్వాత 40 మరియు 50 మార్చబడతాయి. ఒక ఉద్యమం ఒక ఆపరేషన్. నాలుగు పోలికలు నాలుగు ఆపరేషన్లు. నాలుగు మార్పిడులు నాలుగు కార్యకలాపాలు. ఈ విభాగం తొమ్మిది కార్యకలాపాలను అందిస్తుంది. ఇప్పటివరకు మొత్తం ఇరవై ఐదు ఆపరేషన్లు ఉన్నాయి (16 + 9 = 25). ఫలితం క్రింది విధంగా ఉంది:

40 50 60 70 80 | 30 20 10

ఇండెక్స్ ఐదు వద్ద, 30కి కదలిక ఉంది. 30ని 80తో పోల్చారు, తర్వాత 30 మరియు 80 మార్చబడతాయి. 30ని 70తో పోల్చారు, ఆ తర్వాత 30 మరియు 70 మార్చబడతాయి. 30ని 60తో పోల్చారు, ఆ తర్వాత 30 మరియు 60 మార్చబడతాయి. 30ని 50తో పోల్చారు, ఆ తర్వాత 30 మరియు 50 మార్చబడతాయి. 30ని 40తో పోల్చారు, ఆ తర్వాత 30 మరియు 40 మార్చబడతాయి. ఒక ఉద్యమం ఒక ఆపరేషన్. ఐదు పోలికలు ఐదు ఆపరేషన్లు. ఐదు మార్పిడులు ఐదు కార్యకలాపాలు. ఈ విభాగం పదకొండు కార్యకలాపాలను అందిస్తుంది. ఇప్పటివరకు మొత్తం ముప్పై ఆరు ఆపరేషన్లు ఉన్నాయి (25 + 11 = 36). ఫలితం క్రింది విధంగా ఉంది:

30 40 50 60 70 80 | 20 10

ఇండెక్స్ ఆరు వద్ద, 20కి కదలిక ఉంది. 20ని 80తో పోల్చారు, తర్వాత 20 మరియు 80 మార్చబడతాయి. 20ని 70తో పోల్చారు, ఆపై 20 మరియు 70 మార్చబడతాయి. 20ని 60తో పోల్చారు, ఆ తర్వాత 20 మరియు 60 మార్చబడతాయి. 20ని 50తో పోల్చారు, ఆ తర్వాత 20 మరియు 50 మార్చబడతాయి. 20ని 40తో పోల్చారు, ఆ తర్వాత 20 మరియు 40 మార్చబడతాయి. 20ని 30తో పోల్చారు, ఆ తర్వాత 20 మరియు 30 మార్చబడతాయి. ఒక ఉద్యమం ఒక ఆపరేషన్. ఆరు పోలికలు ఆరు ఆపరేషన్లు. ఆరు మార్పిడులు ఆరు కార్యకలాపాలు. ఈ విభాగం పదమూడు కార్యకలాపాలను అందిస్తుంది. ఇప్పటివరకు మొత్తం నలభై-తొమ్మిది ఆపరేషన్లు ఉన్నాయి (36 + 13 = 49). ఫలితం క్రింది విధంగా ఉంది:

20 30 40 50 60 70 80 | 10

ఇండెక్స్ ఏడు వద్ద, 10కి కదలిక ఉంది. 10ని 80తో పోల్చారు, తర్వాత 10 మరియు 80 మార్చబడతాయి. 10ని 70తో పోల్చారు, ఆపై 10 మరియు 70 మార్చబడతాయి. 10ని 60తో పోల్చారు, ఆపై 10 మరియు 60 మార్చబడతాయి. 10ని 50తో పోల్చారు, ఆపై 10 మరియు 50 మార్చబడతాయి. 10ని 30తో పోల్చారు, ఆపై 10 మరియు 40 మార్చబడతాయి. 10ని 30తో పోల్చారు, ఆపై 10 మరియు 30 మార్చబడతాయి. 10ని 20తో పోల్చారు, ఆపై 10 మరియు 20 మార్చబడతాయి. ఒక ఉద్యమం ఒక ఆపరేషన్. ఏడు పోలికలు ఏడు ఆపరేషన్లు. ఏడు మార్పిడులు ఏడు కార్యకలాపాలు. ఈ విభాగం పదిహేను కార్యకలాపాలను అందిస్తుంది. ఇప్పటివరకు మొత్తం అరవై నాలుగు ఆపరేషన్లు ఉన్నాయి (49 + 15 = 64). ఫలితం క్రింది విధంగా ఉంది:

10 20 30 40 50 60 70 80 10 |

పని పూర్తయింది! 64 ఆపరేషన్లు జరిగాయి.

64 = 8 x 8 = 8 ^{రెండు}

చొప్పించే క్రమబద్ధీకరణ కోసం సమయ సంక్లిష్టత

చొప్పించే క్రమబద్ధీకరణతో క్రమబద్ధీకరించడానికి n మూలకాలు ఉంటే, మునుపు ప్రదర్శించిన విధంగా గరిష్ట సంఖ్యలో సాధ్యమయ్యే ఆపరేషన్లు n2గా ఉంటాయి. చొప్పించే క్రమబద్ధీకరణ సమయం సంక్లిష్టత:

పై ^{రెండు} )

ఇది బిగ్-ఓ సంజ్ఞామానాన్ని ఉపయోగిస్తుంది. బిగ్-ఓ సంజ్ఞామానం O పెద్ద అక్షరంతో ప్రారంభమవుతుంది, ఆ తర్వాత కుండలీకరణాలు ఉంటాయి. కుండలీకరణాల లోపల గరిష్ట సంఖ్యలో ఆపరేషన్ల కోసం వ్యక్తీకరణ ఉంటుంది.

C లో కోడింగ్

స్కాన్ ప్రారంభంలో, మొదటి మూలకం దాని స్థానాన్ని మార్చదు. కార్యక్రమం తప్పనిసరిగా క్రింది విధంగా ఉంటుంది:

insertionSort() ఫంక్షన్ నిర్వచనం వివరించిన విధంగా అల్గోరిథంను ఉపయోగిస్తుంది. అయితే-లూప్ కోసం షరతులను గమనించండి. ఈ ప్రోగ్రామ్ కోసం తగిన C ప్రధాన విధి:

ముగింపు

చొప్పించే క్రమబద్ధీకరణ కోసం సమయ సంక్లిష్టత ఇలా ఇవ్వబడింది:

పై ^{రెండు} )

పాఠకుడు అధ్వాన్నమైన సమయ సంక్లిష్టత, సగటు-కేస్ సమయ సంక్లిష్టత మరియు ఉత్తమ-కేస్ సమయ సంక్లిష్టత గురించి విని ఉండవచ్చు. చొప్పించే క్రమబద్ధీకరణ సమయ సంక్లిష్టత యొక్క ఈ వైవిధ్యాలు మా వెబ్‌సైట్‌లోని తదుపరి కథనంలో చర్చించబడతాయి.