[సంగీతాన్ని] డౌ LLOYD: అన్ని కుడి, కాబట్టి బబుల్ సార్ట్ ఒక అల్గోరిథం మీరు మూలకాల ఒక సమితి క్రమం ఉపయోగించవచ్చు. యొక్క ఇది ఎలా పనిచేస్తుంది పరిశీలించి లెట్. 

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

మేము ఎలా చేయాలి? బాగా pseudocode కోడ్ లో, మేము చేసుకుందాం చెప్పగల్గినవి కాని సున్నా విలువ ఒక స్వాప్ కౌంటర్ సెట్. మేము రెండవ అలా ఎందుకు చూస్తారు. మరియు తర్వాత మేము క్రింది పునరావృతం స్వాప్ కౌంటర్ 0 వరకు ప్రక్రియ లేదా మేము అస్సలు మార్పిడులు చేయటం వరకు. 

స్వాప్ కౌంటర్ రీసెట్ 0 ఇది ఇప్పటికే 0 కాదు. అప్పుడు ప్రతి చూడండి అంశాల ప్రక్కనే జంట. ఆ రెండు అంశాలు ఉంటే కాదు క్రమంలో వాటిని మార్పిడి, మరియు స్వాప్ కౌంటర్ 1 జోడించండి. మీరు గురించి ఆలోచిస్తూ ఉంటే ఈ మీరు ఊహించడానికి ముందు, ఈ తక్కువ తరలించడానికి ఉంటుంది గమనించే ఎడమ విలువైన అంశాలు మరియు అధిక, కుడి అంశాలు విలువైన ప్రభావవంతంగా మేము చేయాలనుకుంటున్నారా ఏమి, ఇది ఆ సమూహాలకు తరలించడానికి ఉంది ఆ విధంగా అంశాల. ఎలా ఈ ఊహించడానికి లెట్ మా శ్రేణి ఉపయోగించి చూడండి ఉండవచ్చు మేము పరీక్షించడానికి ఉపయోగించిన ఈ అల్గోరిథంలు బయటకు. మేము మళ్ళీ ఇక్కడ ఒక క్రమబద్ధీకరించనిది శ్రేణి కలిగి అన్ని మూలకాల ద్వారా సూచించిన ఎరుపు లో ఉండటం. నేను నా స్వాప్ కౌంటర్ సెట్ ఒక సున్నా విలువ. నేను ఏకపక్ష ఎంచుకున్నాడు ప్రతికూల 1 కలిగి అది 0 కాదు. మేము ఈ విధానాన్ని పునరుక్తి చేయడానికి కావలసిన స్వాప్ కౌంటర్ వరకు 0. నా స్వాప్ సెట్ ఎందుకు ఈ ఉంది కొన్ని కాని సున్నా విలువను కౌంటర్, లేకపోతే ఎందుకంటే స్వాప్ కౌంటర్ 0 ఉంటుంది. మేము కూడా ప్రారంభం కాదు అల్గోరిథం యొక్క ప్రక్రియ. మరలా, దశలను are-- స్వాప్ కౌంటర్ రీసెట్ 0, ఆపై ప్రతి ప్రక్కనే చూడండి యుగ్మము, మరియు వారు క్రమంలో బయటకు అయితే, వాటిని మార్పిడి మరియు 1 జోడించండి స్వాప్ కౌంటర్. కాబట్టి యొక్క ఈ ప్రక్రియను ప్రారంభించడానికి వీలు. కాబట్టి మేము మొదటి విషయం ఉంది మేము, 0 స్వాప్ కౌంటర్ సెట్ ఆపై మేము చూడటం మొదలు ప్రతి ప్రక్కనే జత వద్ద. 

కాబట్టి మేము మొదటి 5 మరియు 2 చూడటం మొదలు. మేము వారు బయటకు ఉన్నాయని చూడండి ఆర్డర్ మరియు కాబట్టి మేము వాటిని మార్పిడి. మరియు మేము స్వాప్ కౌంటర్ 1 జోడించండి. కాబట్టి ఇప్పుడు మా swap కౌంటర్ 1, మరియు 2 మరియు 5 మొగ్గు చేశారు. ఇప్పుడు మేము మళ్ళీ విధానాన్ని పునరుక్తి. 

మేము తదుపరి ప్రక్కనే జత చూడండి, 5 మరియు వారు కూడా క్రమం లేదు 1 కలిగి, కాబట్టి మేము వాటిని మార్పిడి మరియు జోడించడానికి స్వాప్ కౌంటర్ 1. అప్పుడు మేము 5 మరియు 3 వద్ద చూడండి. వారు క్రమం ఉంటాయి, కాబట్టి మేము స్వాప్ వాటిని మరియు మేము స్వాప్ కౌంటర్ 1 జోడించండి. అప్పుడు మేము 5 మరియు 6 చూడండి. వారు క్రమంలో ఉన్నారు, కాబట్టి మేము నిజానికి లేదు ఏదైనా ఈ సమయం మార్పిడి అవసరం. అప్పుడు మేము 6 మరియు 4 చూడండి. వారు క్రమం కూడా ఉన్నాము, కాబట్టి మేము స్వాప్ వాటిని మరియు మేము స్వాప్ కౌంటర్ 1 జోడించండి. 

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

అందువలన మేము ఇప్పుడు ప్రకటించవచ్చు ఆ క్రమబద్ధీకరించబడింది ఆ, మరియు భవిష్యత్తులో iterations-- అర్రే ద్వారా వెళుతున్న మళ్ళీ మేము ఇకపై 6 పరిగణలోకి లేదు. మేము మాత్రమే పరిగణించాలి క్రమబద్ధీకరించనిది అంశాలను మేము ప్రక్కనే ఉన్న జతల శోధిస్తున్న. కాబట్టి మేము ఒక ముగించిన బబుల్ సార్ట్ గుండా. కాబట్టి ఇప్పుడు మేము ప్రశ్న తిరిగి వెళ్ళు స్వాప్ కౌంటర్ 0 వరకు పునరావృతం. బాగా స్వాప్ కౌంటర్ 4, కాబట్టి మేము వెళుతున్న మళ్ళీ ఈ పద్ధతిని పునరావృతం ఉంచేందుకు. 

మేము స్వాప్ కౌంటర్ రీసెట్ చూడాలని 0, మరియు ప్రతి ప్రక్కనే జత చూడండి. కాబట్టి మేము వారు ఉన్నారు 1 కలిగి 2 ప్రారంభం మరియు ఆర్డర్ బయటకు, కాబట్టి మేము వాటిని మార్పిడి మరియు మేము స్వాప్ కౌంటర్ 1 జోడించండి. 2 మరియు 3, వారు క్రమంలో ఉన్నారు. మేము ఏమీ చేయాల్సిన అవసరం లేదు. 3 మరియు 5 క్రమంలో ఉంటాయి. మేము అక్కడ చేయవలసిన అవసరం లేదు. 

5 మరియు 4, వారు బయటకు ఉంటాయి ఆర్డర్ ఆఫ్, అందువలన మేము వాటిని మార్పిడి మరియు జోడించడానికి అవసరం స్వాప్ కౌంటర్ 1. ఇప్పుడు మేము 5 తరలించారు తరువాతి అతిపెద్ద మూలకం, క్రమబద్ధీకరించనిది భాగం యొక్క చివర. కాబట్టి మేము ఇప్పుడు ఆ కాల్ చేయవచ్చు క్రమబద్ధీకరించబడతాయి భాగం భాగం. 

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

కాబట్టి మేము ఒక పాస్ పూర్తి చేసిన. స్వాప్ కౌంటర్ 2. కాబట్టి మేము పునరుక్తి చూడాలని మళ్లీ ఈ ప్రక్రియ, స్వాప్ కౌంటర్ 0 వరకు పునరావృతం. 0 స్వాప్ కౌంటర్ రీసెట్. కాబట్టి మేము అది రీసెట్ చేస్తాము. 

ఇప్పుడు ప్రతి ప్రక్కనే జత చూడండి. ఆ క్రమంలో 1 మరియు 2. 2 మరియు 3 క్రమంలో ఉంటాయి. 3 మరియు 4 క్రమంలో ఉంటాయి. కాబట్టి ఈ సమయంలో, మేము పూర్తి చేసిన గమనిస్తారు ప్రతి ప్రక్కనే జంట చూడటం, కానీ స్వాప్ కౌంటర్ ఇప్పటికీ 0. 

మేము మారడానికి లేకపోతే ఏ అంశాలు, అవి అప్పుడు ద్వారా క్రమంలో ఉండాలి ఈ ప్రక్రియలో ఉండటం. కాబట్టి అన్నిరకాల సామర్థ్యం, మేము కంప్యూటర్ శాస్త్రవేత్తలు ప్రేమ, మేము ఇప్పుడు ప్రకటించవచ్చు ఉంది మొత్త తప్పక మేము లేదు ఎందుకంటే వేరు ఏ అంశాలు మారడానికి. అతను చాలా మంచిది. 

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

కాబట్టి ఆ అర్థం ఏమిటి? సో వాట్ చెత్త దృష్టాంత వార్తలు బబుల్ సార్ట్ కోసం, మరియు ఏమి బబుల్ సార్ట్ ఉత్తమ దృష్టాంత? మీరు ఈ అంచనా తెలుసా? చెత్త సందర్భంలో మీరు iterate ఉంటుంది అన్ని n మూలకాలు n సార్లు అంతటా. కాబట్టి చెత్త సందర్భంలో స్క్వేర్డ్ n. 

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

నేను డౌ లాయిడ్ ఉన్నాను. ఈ CS50 ఉంది.