[Powered by Google Translate] [చేర్పు క్రమీకరించు] [టామీ MacWilliam] [హార్వర్డ్ విశ్వవిద్యాలయం] [ఈ CS50.TV ఉంది] యొక్క ప్రవేశాన్ని విధమైన పరిశీలించి, సంఖ్యల జాబితా తీసుకుని వాటిని క్రమబద్ధీకరించేందుకు ఒక అల్గోరిథం తీసుకుందాం. యాంత్రిక పద్ధతి గుర్తుంచుకోండి కేవలం ఒక పని పూర్తి చేయుటకు ఒక అడుగు వారీ ప్రక్రియ. చొప్పించడం విధమైన వెనుక ప్రధాన ఆలోచన, రెండు భాగాలు గా మా జాబితా విభజించాలనే ఉంది ఒక క్రమబద్ధీకరించబడతాయి భాగం మరియు ఒక క్రమబద్ధీకరించనిది భాగం. 

అల్గోరిథం యొక్క ప్రతి దశ, అనేక కదులుతుంది క్రమబద్ధీకరించనిది భాగం నుండి పేర్చిన భాగానికి చివరికి వరకు మొత్తం జాబితా క్రమీకరించబడింది. 23, 42, 4, 16, 8, మరియు 15 - ఇక్కడ ఆరు క్రమబద్ధీకరించనిది సంఖ్యల జాబితా ఉంది. ఈ సంఖ్యలు క్రమంలో అన్ని కనుక, వారు క్రమబద్ధీకరించనిది చేస్తున్నారు. మేము ఇంకా క్రమబద్ధీకరించేందుకు ప్రారంభించారు కాబట్టి, మేము అన్ని ఆరు అంశాలు మా క్రమబద్ధీకరించనిది భాగం పరిగణలోకి చేస్తాము. 

ఒకసారి మేము క్రమబద్ధీకరించేందుకు ప్రారంభం, మేము ఈ ఎడమ వైపున ఈ విభజించిన సంఖ్యలు ఉంచుతాము. కాబట్టి, యొక్క 23, మా జాబితా లో మొదటి మూలకం తో ప్రారంభిద్దాం. మేము, మా ఇంకా క్రమబద్ధీకరించబడతాయి భాగంలో ఏ అంశాలు లేవు కాబట్టి యొక్క కేవలం మా క్రమబద్ధీకరించబడతాయి భాగం యొక్క ప్రారంభ మరియు ముగింపు ఉండాలి 23 పరిగణలోకి తెలియజేయండి. ఇప్పుడు, మా క్రమబద్ధీకరించబడతాయి భాగం ఒక సంఖ్య, 23, ఉంది మరియు మా క్రమబద్ధీకరించనిది భాగం ఈ ఐదు సంఖ్యలు ఉన్నాయి. యొక్క ఇప్పుడు క్రమబద్ధీకరించబడతాయి భాగంలోకి మా క్రమబద్ధీకరించనిది భాగం, 42, తదుపరి సంఖ్య ఇన్సర్ట్ లెట్. 

అలా చేయుటకు, మేము 23 వరకు 42 పోల్చడానికి చేయాలి - మా క్రమబద్ధీకరించబడతాయి భాగంలో మాత్రమే మూలకం ఇప్పటివరకు. నలభై రెండు 23 కంటే పెద్ద, కాబట్టి మేము కేవలం చివర 42 కలపవచ్చు జాబితా యొక్క క్రమబద్ధీకరించబడతాయి భాగం. గ్రేట్! ఇప్పుడు మా క్రమబద్ధీకరించబడతాయి భాగం రెండు అంశాలను కలిగి ఉంది, మరియు మా క్రమబద్ధీకరించనిది భాగం నాలుగు అంశాలను కలిగి ఉంది. కాబట్టి, క్రమబద్ధీకరించనిది భాగంలో తదుపరి మూలకం, ప్రస్తుతం 4 తరలించడానికి అనుమతిస్తాయి. కాబట్టి, ఈ విభజించిన భాగంలో పేరు పెట్టాలి? 

గుర్తుంచుకోండి, మేము క్రమబద్ధీకరించబడతాయి క్రమంలో ఈ సంఖ్య ఉంచాలనుకుంటే మన క్రమబద్ధీకరించబడతాయి భాగం సరిగ్గా అన్ని సమయాల్లో క్రమబద్ధీకరించబడతాయి ఉంది. మేము 42 కుడివైపున 4 ఉంచండి, అప్పుడు మా జాబితా ఆర్డర్ బయటకు ఉంటుంది. కాబట్టి, మా యొక్క విధమైన భాగంలో కుడి నుంచి ఎడమ కదిలే చెయ్యనివ్వండి. మేము ప్రయాణంలో, కొత్త సంఖ్య కల్పించడం కోసం ఒక స్థలం డౌన్ ప్రతి సంఖ్య మారవచ్చు తెలియజేయండి. సరే, 4 కూడా కంటే తక్కువ 23, కాబట్టి మేము గాని ఇక్కడ చేయలేము. యొక్క 23 కుడివైపు ఒకే చోట తరలించడానికి లెట్. 

మేము క్రమబద్ధీకరించబడతాయి భాగంలో మొదటి స్లాట్ లోకి 4 ఉంచడానికి కావలసిన అనగా. జాబితాలో ఈ స్థలం ఇప్పటికే ఖాళీ ఎంత గమనించండి, మేము వాటిని ఎదుర్కొన్న వంటి మేము క్రమబద్ధీకరించబడతాయి అంశాలను డౌన్ కదిలే చేసిన ఎందుకంటే. అన్ని కుడి. అందుకే, ఈ సగం అక్కడ ఉన్నారు. యొక్క క్రమబద్ధీకరించబడతాయి భాగంలోకి 16 చేర్చడం ద్వారా మా అల్గోరిథం చెయ్యనివ్వండి. పదహారు తక్కువ 42 కంటే, కాబట్టి కుడివైపు 42 మార్చేందుకు వీలు ఉంటుంది. పదహారు తక్కువ 23 కంటే, కాబట్టి యొక్క కూడా ఆ మూలకం బదిలీ అనుమతిస్తాయి కూడా ఉంది. 

ఇప్పుడు, 16 4 కంటే ఎక్కువ. మేము 4 మరియు 23 మధ్య 16 ఇన్సర్ట్ చెయ్యడానికి కావలసిన వంటి కాబట్టి, కనిపిస్తోంది. కుడి నుండి ఎడమ జాబితా యొక్క క్రమబద్ధీకరించబడతాయి భాగం ద్వారా తరలిస్తున్నప్పుడు, 4 సంఖ్య కంటే తక్కువగా ఉంటుంది మేము చూసిన మొదటి సంఖ్య మేము ఇన్సర్ట్ చెయ్యడానికి ప్రయత్నిస్తున్నారు. కాబట్టి, ఇప్పుడు మేము ఈ ఖాళీ స్లాట్ లోకి 16 ఇన్సర్ట్ చేయవచ్చు ఇది గుర్తుంచుకోండి, మేము పైగా విధమైన భాగంలో కదిలే అంశాలు సృష్టించిన మేము వాటిని ఎదుర్కొన్న వంటి. 

అన్ని కుడి. ఇప్పుడు మేము నాలుగు క్రమబద్ధీకరించబడతాయి అంశాలు మరియు రెండు క్రమబద్ధీకరించనిది అంశాలను కలిగి ఉంటుంది. కాబట్టి, యొక్క క్రమబద్ధీకరించబడతాయి భాగంలోకి 8 తరలించడానికి అనుమతిస్తాయి. ఎనిమిది కంటే తక్కువ 42 ఉంది. ఎనిమిది కంటే తక్కువ 23 ఉంది. మరియు 8 కంటే తక్కువ 16 ఉంది. కానీ 8 4 కంటే ఎక్కువ. కాబట్టి, మేము 4 మరియు 16 మధ్య 8 ఇన్సర్ట్ చెయ్యడానికి ఎంచుకోండి. 15 - మరియు ఇప్పుడు మేము క్రమం చేయడానికి ఒక్క మరింత మూలకం ఉన్నాయి. పదిహేను, కంటే తక్కువ 42 పదిహేను కంటే తక్కువ 23 ఉంది. మరియు 15 కన్నా తక్కువ 16 ఉంది. కానీ 15 8 కంటే ఎక్కువగా ఉంటుంది. 

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

పంక్తి 1 న, మేము జాబితాలో ప్రతి మూలకం పైగా iterate చేయాలి అని చూడగలరు మొదటి తప్ప, క్రమబద్ధీకరించనిది భాగంలో మొదటి మూలకం నుండి కేవలం అవుతుంది క్రమబద్ధీకరించబడింది భాగంలో మొదటి మూలకం. పంక్తులు 2 మరియు 3 న, క్రమబద్ధీకరించనిది భాగంలో మా ప్రస్తుత స్థానం యొక్క ట్రాక్ ఉంచుతున్నారు. ఎలిమెంట్ మేము ప్రస్తుతం క్రమబద్ధీకరించబడతాయి భాగంలోకి తరలిస్తున్న సంఖ్య సూచిస్తుంది మరియు j క్రమబద్ధీకరించనిది భాగంలోకి మా ఇండెక్స్ సూచిస్తుంది. 

లైన్ 4 న, కుడి నుండి ఎడమ క్రమబద్ధీకరించబడతాయి భాగం ద్వారా iterating చేస్తున్నారు. మేము మా ప్రస్తుత స్థితి ఎడమ మూలకం ఒకసారి iterating ఆపివేయాలనుకుంటున్నారా మేము ఇన్సర్ట్ చెయ్యడానికి ప్రయత్నిస్తున్న మూలకం కంటే తక్కువగా ఉంది. లైన్ 5 న, మేము ఒక ఖాళీ ఎదుర్కునే ప్రతి మూలకం బదిలీ చేస్తున్నారు. మేము మొదటి మూలకం చూసినప్పుడు ఆ విధంగా, మేము ఇన్సర్ట్ స్పష్టమైన ఖాళీ స్థలం ఉంటుంది మేము కదిలే చేస్తున్న మూలకం కంటే తక్కువ. లైన్ 6 న, క్రమబద్ధీకరించబడింది భాగం ద్వారా ఎడమ వెళ్లడం కొనసాగింది మా కౌంటర్ అప్ డేట్ చేస్తున్నాము. చివరగా, లైన్ 7 న, జాబితా యొక్క క్రమబద్ధీకరించబడతాయి భాగంలోకి మూలకం ఇన్సర్ట్ చేస్తున్నారు. 

మేము, అది స్థానం j ఇన్సర్ట్ తప్పు అని తెలుసు మేము ఇప్పటికే కుడి అక్కడ ఒక స్థలం కలిగిన మూలకం తరలించారు ఎందుకంటే. గుర్తుంచుకోండి, మేము, కుడి నుండి పేర్చిన భాగం కదులుతున్న చేస్తున్నారు కానీ మేము ఎడమ నుండి కుడికి క్రమబద్ధీకరించనిది భాగం కదులుతున్న చేస్తున్నారు. అన్ని కుడి. యొక్క ఇప్పుడు అల్గోరిథం పట్టింది నడుస్తున్న ఎంత పరిశీలించి చూద్దాం. మేము ఈ అల్గోరిథం విషయంలో అమలు చేయడానికి ఎంత సమయం అది పడుతుంది ప్రశ్న అడుగుతాము. మేము బిగ్ O సంజ్ఞామానం ఈ నడుస్తున్న సమయంలో ప్రాతినిధ్యం గుర్తుచేసుకున్నారు. మా జాబితా క్రమం చేయడానికి, మేము, క్రమబద్ధీకరించనిది భాగంలో అంశాలను పైగా iterate వచ్చింది మరియు శక్తివంతంగా క్రమబద్ధీకరించబడతాయి భాగం అన్ని మూలకాల కంటే ఆ అంశాలను ప్రతి కోసం. Intuitively, ఒక O (n ^ 2) ఆపరేషన్ వంటి ఈ శబ్దాలు. 

మా pseudocode వద్ద గురించి, మేము మరో లూప్ లోపల యున్న ఒక లూప్ కలిగి ఇది నిజానికి ఒక O (n ^ 2) ఆపరేషన్ లాగా ఉంటుంది. అయితే, జాబితా యొక్క క్రమబద్ధీకరించబడతాయి భాగం చాలా చివరి వరకు మొత్తం జాబితా కలిగి లేదు. ఇంకా, మీరు సమర్థవంతంగా క్రమబద్ధీకరించబడతాయి భాగం చాలా ప్రారంభంలో ఒక కొత్త మూలకం ఇన్సర్ట్ చేయవచ్చు అల్గోరిథం యొక్క ప్రతి మళ్ళా న, ఇది మేము క్రమబద్ధీకరించబడతాయి భాగంలో ప్రస్తుతం ప్రతి మూలకం కు భావిస్తాను అర్థం. కాబట్టి, మేము సమర్థవంతంగా, రెండవ మూలకం కోసం ఒక పోలికను తయారు చేయగలవు అని దీని అర్థం మూడవ మూలకం కోసం రెండు పోలికలు, అందువలన న. కాబట్టి, దశలను మొత్తం 1 నుండి జాబితా మైనస్ 1 యొక్క పొడవు పూర్ణాంకాల మొత్తం. మేము ఒక సమ్మషన్ ఈ సూచిస్తుంది. 

మేము ఇక్కడ summations వెళ్ళాలని, కాని అది ఈ సమ్మషన్ సమానంగా ఉంటుంది అవుతుంది n / 2 - సమానమైన n ^ 2/2 ఇది 2 పైగా - n (1 n). Asymptotic runtime గురించి మాట్లాడుతున్నప్పుడు, ఈ n ^ 2 పదం ఈ పదం n ఆధిపత్యం అన్నారు. కాబట్టి, చొప్పించడం విధమైన బిగ్ O (n ^ 2) ఉంది. మనం ఇప్పటికే క్రమబద్ధీకరించబడతాయి జాబితాలో చొప్పించడం విధమైన నడిచింది ఉంటే. ఆ సందర్భంలో, మనం కేవలం ఎడమ నుండి కుడికి క్రమబద్ధీకరించబడతాయి భాగాన్ని నిర్మించేందుకు కావలసిన. కాబట్టి, మేము మాత్రమే n దశలను యొక్క ఆర్డర్ మీద ఉంటుంది. 

ఆ, చొప్పించడం విధమైన n యొక్క ఉత్తమ కేసు ప్రదర్శన ఉంది అంటే ఇది మేము Ω (n) తో సూచిస్తాయి. మరియు ఆ, చొప్పించడం విధమైన కోసం ఇది అనేక అల్గోరిథంలు యొక్క ఒక మేము ఒక జాబితాను క్రమబద్దీకరించేందుకు ఉపయోగించవచ్చు. నా పేరు టామీ, మరియు ఈ CS50 ఉంది. [CS50.TV] ఓహ్, మీరు దీనిని ఒకసారి ప్రారంభమయ్యే కాంట్ స్టాప్. ఓహ్, ఆ చేశాడు - >> బూమ్!