డౌ LLOYD: కాబట్టి CS50 లో మేము గురించి నేర్చుకున్నాడు సార్టింగ్ అండ్ సెర్చింగ్ వివిధ అల్గోరిథంలు. కొన్నిసార్లు ఉంటుంది ఉంచడానికి ఒక చిన్న గమ్మత్తైన ఏమి అల్గోరిథం యొక్క ట్రాక్ దేనిని. మమ్మల్ని మాత్రమే చేసిన చాలా ఉపరితల తీసే అనేక ఇతర శోధించడం ఉన్నాయి మరియు సార్టింగ్ అల్గోరిథంలు. సో ఈ వీడియో లో లెట్స్ కేవలం కొన్ని నిమిషాలు పట్టవచ్చు ప్రయత్నించండి మరియు ప్రతి అల్గోరిథం పరిశుద్ధం దాని కోర్ అంశాలు క్రిందికి కాబట్టి మీరు చాలా గుర్తుంచుకోగలరు వాటిని గురించి ముఖ్యమైన సమాచారం మరియు ఉచ్చరించు చేయగలరు తేడాలు, అవసరమైతే. 

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

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

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

కీవర్డ్ విధమైన విలీనం ఇక్కడ విడిపోయి కలిసిపోయినా. మేము అని, పూర్తి శ్రేణి విడిపోయారు ఇది ఆరు అంశాలు, ఎనిమిది అంశాలు వార్తలు, 10,000 మూలకాల మేము అది విడిపోయింది డౌన్ సగం, సగం ద్వారా సగానికి, మేము శ్రేణి కింద వరకు n ఒక మూలకం శ్రేణుల. N ఒక మూలకం శ్రేణుల సెట్. కాబట్టి మేము ఒక ప్రారంభించండి 1,000 మూలకం శ్రేణి, మరియు మేము పాయింట్ చోటే మేము 1,000 ఒక మూలకం శ్రేణుల ఉన్నాయి. అప్పుడు మేము ఆ ఉప శ్రేణుల విలీనం ప్రారంభమవుతుంది తిరిగి కలిసి సరైన క్రమంలో. కాబట్టి మేము రెండు ఒక మూలకం శ్రేణుల పడుతుంది మరియు ఒక రెండు మూలకం శ్రేణి సృష్టించండి. మేము రెండు రెండు మూలకం శ్రేణుల పడుతుంది మరియు నాలుగు-మూలకం శ్రేణి సృష్టించడానికి అందువలన మరియు అందువలన న మేము చేసిన వరకు మళ్ళీ ఒకటి n మూలకాల శ్రేణి పునర్నిర్మించబడింది. 

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

మేము రెండు గురించి మాట్లాడారు అల్గోరిథంలు శోధన. సో సరళ శోధన iterating గురించి. మేము శ్రేణి అంతటా వెళ్లండి ఒకసారి, ఎడమ నుండి కుడికి, సంఖ్య కనుగొనేందుకు ప్రయత్నిస్తున్న మేము చూస్తున్న. చెత్త-కేసు అమలు సమయం n యొక్క పెద్ద O ఉంది. ఇది iterating మాకు పడుతుంది ప్రతి మూలకం అంతటా మేము చూస్తున్న మూలకం కనుగొనేందుకు కోసం గాని చివరి స్థానం లో, లేదా అన్ని వద్ద. కానీ మేము వరకు నిర్ధారించలేము మేము ప్రతిదీ చూశారు చేసిన. ఉత్తమ కేసు రెడీ, మేము వెంటనే కనుగొనేందుకు. యొక్క ఉత్తమ కేసు అమలు సమయం సరళ శోధన 1 ఒమేగా ఉంది. 

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

మేము వెంటనే కలిగించే మొదటిసారి మేము ఒక విభాగం, అయితే మళ్ళీ, గుర్తుంచుకోవాలి బైనరీ శోధన అయితే సరళ శోధన కంటే గణనీయంగా మంచి లాగ్ ఉండటం ఉండటం ద్వారా N N వర్సెస్ మీరు పని ద్వారా వెళ్ళడానికి కలిగి ఉండవచ్చు మొదటి మీ వ్యూహం క్రమబద్ధీకరించేందుకు ఏ ఆధారపడి అది తక్కువ ప్రభావవంతంగా సంపాదించగలరు క్రమబద్ధీకరించబడింది iterating యొక్క పరిమాణం మీద. 

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