[Powered by Google Translate] [బబుల్ సార్ట్] [JACKSON STEINKAMP హార్వర్డ్ విశ్వవిద్యాలయం] [ఈ CS50 IS. CS50TV] బబుల్ సార్ట్ వేరు అల్గోరిథం యొక్క ఒక ఉదాహరణ - ఆ, మూలకాల ఒక సమితి లో క్రమీకరించడానికి ప్రక్రియ ఆరోహణ లేదా అవరోహణ క్రమంలో. మీరు ఒక అర్రే క్రమం కోరుకుంటే ఉదాహరణకు, సంఖ్యలు ఉంటాయి [3, 5, 2, 9], బబుల్ సార్ట్ ఒక సరైన అమలు చేరాడు పేర్చిన అమరిక [2, 3, 5, 9] క్రమంలో. ఇప్పుడు నేను అల్గోరిథం ఎలా పనిచేస్తుంది pseudocode వివరించండి వెళుతున్న. 

3, 2, 9, 6, మరియు 5 - లెట్ యొక్క మేము 5 పూర్ణాంకాల యొక్క జాబితా క్రమబద్ధీకరించేందుకు చేస్తున్నారు అనుకోండి. అల్గోరిథం, మొదటి రెండు అంశాలను 3 మరియు 2 చూడటం ద్వారా మొదలవుతుంది వారు పరస్పర ఆర్డర్ బయటకు అయితే తనిఖీ. అవి - 3 2 కంటే ఎక్కువ. ఆరోహణ క్రమంలో, అవి చుట్టూ ఇతర మార్గం ఉండాలి. కాబట్టి, మేము వాటిని మార్పిడి. [2, 3, 9, 6, 5]: ఇప్పుడు జాబితా ఈ కనిపిస్తోంది. 

తరువాత, మేము రెండవ మరియు మూడవ అంశాలు, 3 మరియు 9 చూడండి. వారు పరస్పర సరైన క్రమంలో ఉన్నారు. అల్గారిథమ్ వాటికి స్వాప్ లేదు 9 కంటే తక్కువగా ఉంటుంది, 3. తరువాత, మేము 9 మరియు 6 చూడండి. వారు క్రమం లేదు. 

అందుకే, ఈ 9 6 కంటే ఎక్కువగా ఉంటుంది ఎందుకంటే వాటిని మార్పిడి అవసరం. చివరగా, మేము గత రెండు పూర్ణాంకాల, 9 మరియు 5 చూడండి. వారు క్రమం లేదు, కాబట్టి వారు మార్చుకున్నారు ఉండాలి. జాబితా ద్వారా మొదటి పూర్తి పాస్ తరువాత, [2, 3, 6, 5, 9]: ఈ కనిపిస్తోంది. చెడు లేదు. ఇది దాదాపు క్రమబద్ధీకరించబడతాయి యొక్క. కాని మనము దానిని పూర్తిగా క్రమబద్ధీకరించబడతాయి పొందడం మళ్లీ జాబితా ద్వారా అమలు చేయాలి. రెండు 3 కంటే తక్కువ, కాబట్టి మేము వాటిని మార్చవద్దు. 

మూడు 6 కంటే తక్కువ, కాబట్టి మేము వాటిని మార్చవద్దు. ఆరు 5 కంటే ఎక్కువగా ఉంటుంది. మేము మార్చుకున్నారు. ఆరు 9 కంటే తక్కువగా ఉంది. మేము మార్చవద్దు. ద్వారా రెండవ పాస్ తర్వాత, ఈ కనిపిస్తోంది: [2, 3, 5, 6, 9]. పర్ఫెక్ట్. ఇప్పుడు, pseudocode రచన యొక్క అనుమతిస్తాయి. సాధారణంగా, జాబితాలో ప్రతి మూలకం కోసం, మేము దాన్ని చూడవలసిన అవసరం మరియు నేరుగా దాని కుడి మూలకం. వారు క్రమం యొక్క పరస్పర వెలుపల ఉంటే - ఆ, ఉంటే ఎడమవైపు మూలకం కుడివైపు ఒకటి కంటే ఎక్కువ ఉంటుంది - మేము రెండు అంశాలను మార్పిడి చేయాలి. 

మేము జాబితాలో ప్రతి మూలకం కోసం దీన్ని, మరియు మేము ద్వారా ఒక పాస్ చేసిన. ఇప్పుడు మేము జాబితా నిర్ధారించడానికి ఉత్తీర్ణత ద్వారా తగినంత సార్లు లేదు పూర్తిగా, సరిగ్గా క్రమబద్ధీకరించబడింది. కానీ మేము జాబితా గుండా ఎన్ని సార్లు ఉన్నాయి మేము పూర్తి చేసిన హామీ? మేము పూర్తిగా వెనక్కి జాబితా ఉంటే సరే, చెత్త దృష్టాంత ఉంది. అప్పుడు సంఖ్య సమానంగా ఉత్తీర్ణత throughs అనేక పడుతుంది అంశాలను n-1 యొక్క. ఈ intuitively సమంజసం అనిపించుకోదు ఉంటే, ఒక సాధారణ విషయం యొక్క ఆలోచన - జాబితా [2, 1]. 

ఈ క్రమం సరిగా ఒక ఉత్తీర్ణత ద్వారా తీసుకోవాలని అన్నారు. [3, 2, 1] - విషయంలో, 3 అంశాలతో వెనుకకు క్రమబద్ధీకరించబడతాయి ఉంది ఇది విధమైన 2 నిద్రావస్థ తీసుకోవాలని చెప్పారు. ఒక పునరుక్తి తర్వాత, [, 3 1 2] ఉంది. రెండవ దిగుబడి క్రమబద్ధీకరించబడతాయి శ్రేణి [1, 2, 3]. కాబట్టి మీరు, మీరు సాధారణంగా, అర్రే ద్వారా వెళ్ళడానికి లేదు తెలుసు n శ్రేణి లోని ఎలిమెంట్స్ సంఖ్య n-1 టైమ్స్, కంటే ఎక్కువ. అతిపెద్ద అంశాలను 'బుడగ అప్' ఉంటాయి ఎందుకంటే ఇది బబుల్ సార్ట్ అని అందంగా త్వరగా కుడివైపు. నిజానికి, ఈ అల్గోరిథం ఆసక్తికరమైన ప్రవర్తన కలిగి ఉంది. 

మొత్త ద్వారా m నిద్రావస్థ తర్వాత, కుడివైపు m అంశాలను హామీ వాటి సరైన స్థానంలో వేరు చేయడానికి. మీరు, మీ కోసం ఈ చూడాలనుకుంటే మేము పూర్తిగా వెనక్కి జాబితా [9, 6, 5, 3, 2] ఇది ప్రయత్నించవచ్చు. మొత్తం జాబితా ద్వారా ఒక పాస్ తరువాత, [రచన ధ్వని] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] కుడివైపు మూలకం 9 దాని సరైన స్థానంలో ఉంది. ఉత్తీర్ణత ద్వారా రెండవ తరువాత, 6 'bubbled అప్' ఉంటుంది రెండవ స్థానంలో కుడివైపు. 6 మరియు 9 - - కుడి రెండు అంశాలను వాటి సరైన ప్రదేశాలలో ఉంటుంది మొదటి రెండు ఉత్తీర్ణత throughs తర్వాత. 

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

మీరు n మూలకాల శ్రేణిని క్రమబద్ధీకరించేందుకు చేసిన అయితే, మొదటి మళ్ళా న - you'll అన్ని మూలకాల క్రమం ఉంటుంది - మొదటి n-0. రెండవ పునరుక్తి, మీరు అన్ని మూలకాల కానీ గత చూడండి ఉంటుంది - n-1 మొదటి. మరో ఆప్టిమైజేషన్ జాబితా ఇప్పటికే క్రమబద్ధీకరించబడింది లేదో తనిఖీ చేయడానికి కావచ్చు ప్రతి పునరావృతం తరువాత. ఇది ఇప్పటికే క్రమబద్ధీకరించబడతాయి అయితే, మేము ఏ నిద్రావస్థ తయారు లేదు జాబితా ద్వారా. దీన్ని మేము ఎలా చేయగలరు? Well, మేము ఒక జాబితా యొక్క ఉత్తీర్ణత ద్వారా ఏ మార్పిడులు చేయటం లేదు ఉంటే, అది మేము ఏదైనా మార్పిడి ఎందుకంటే జాబితా ఇప్పటికే క్రమబద్ధీకరించబడతాయి అని స్పష్టమవుతుంది. కాబట్టి మేము ఖచ్చితంగా మళ్ళీ క్రమం లేదు. 

బహుశా మీకు 'వర్గీకరించరు' అనే జెండా వేరియబుల్ ప్రారంభించడం కాలేదు మీరు ఏ అంశాలు మారడానికి ఉంటే తప్పుడు మరియు నిజమైన దానిని మార్చడానికి అర్రే ద్వారా ఒక పునరుక్తి. లేదా ఇదే విధంగా, మీరు ఎలా అనేక మార్పిడులు లెక్కించడానికి ఒక కౌంటర్ తయారు ఏ మళ్ళా న. ఒక పునరావృతం తరువాత, మీరు అంశాలను ఏ స్వాప్ లేదు ఉంటే, మీరు జాబితా ఇప్పటికే క్రమబద్ధీకరించబడింది మరియు మీరు పూర్తి చేసిన తెలుసు. బబుల్ సార్ట్, ఇతర సార్టింగ్ అల్గోరిథంలు వంటి ఉంటుంది ఒక క్రమం పద్ధతి ఏ అంశాలకు పని tweaked. 

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

ఏ ఎంతో చక్కగా లేదా ఫాస్ట్ సార్టింగ్ అల్గోరిథం అర్థం ద్వారా బబుల్ సార్ట్ ఉంది. ఘోరమైన-runtime కేసు n యొక్క బిగ్ O ఉంది ² మీరు జాబితా ద్వారా n నిద్రావస్థ తయారు చేసుకోవాలి ఎందుకంటే ప్రతి ఉత్తీర్ణత ద్వారా అన్ని n మూలకాలు తనిఖీ, nxn = n ². ఈ అమలు సమయం అంశాల సంఖ్య మీరు, పెరుగుదల క్రమబద్ధీకరించేందుకు చేస్తున్న అర్థం రన్ టైం quadratically పెంచుతుంది. 

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