MARK GROZEN-SMITH హాయ్, నేను మార్క్ రెడీ -స్మిత్ Grozen, మరియు ఈ Quicksort ఉంది. కేవలం చొప్పించడం విధమైన మరియు బబుల్ వంటి విధమైన, Quicksort కోసం ఒక అల్గోరిథం జాబితా లేదా విషయాలు వ్యూహం క్రమబద్ధీకరించేందుకు. సాధారణంగా, యొక్క ఊహించుకోవటం తెలియజేయండి ఆ విషయాలు కేవలం పూర్ణ, కానీ Quicksort కోసం పనిచేస్తుంది తెలుసు కేవలం ఎక్కువమంది. శీఘ్రప్రారంభ ఒక బిట్ మరింత క్లిష్టంగా ఉంటుంది కంటే చొప్పించడం లేదా బుడగ, కానీ ఉంది ఆ చాలా సమర్థవంతంగా చాలా సందర్భాలలో. తను. అతను కేవలం "చెప్పడానికి తెలుసా కేసులు, "కాదు" అన్ని "? ఆసక్తికరంగా, ఏ. అన్ని సందర్భాలలో ఒకటే. ఈ వివరాలు గురించి ఆందోళన లేదు మీరు ఉంటే ఇంకా పెద్ద O సంజ్ఞామానం చూసిన, కానీ లేదు Quicksort ఒక O (n స్క్వేర్డ్) అల్గోరిథం ఘోరంగా, కేవలం వంటి చొప్పించడం లేదా బబుల్ సార్ట్. అయితే, ఇది సాధారణంగా మరింత పనిచేస్తుంది పాత అనలాగ్ m అల్గోరిథం వంటి. ఎందుకు? మేము తరువాత ఆ పొందుతారు. కానీ ఇప్పుడు కోసం, యొక్క కేవలం నేర్చుకుందాము Quicksort ఎలా పని. 

కాబట్టి యొక్క ఈ Quicksorting నడవడానికి వీలు చిన్న నుండి పూర్ణాంకాల శ్రేణి అతిపెద్ద. ఇక్కడ మేము, పూర్ణ 6 కలిగి 5, 1, 3, 8, 4, 7, 9, మరియు 2. మొదటి, మేము చివరి మూలకం యొక్క ఎంచుకోండి ఈ శ్రేణి - ఈ సందర్భంలో, రెండు - మరియు ఆ "ఇరుసు." కాల్ తరువాత, మేము రెండు విషయాలు చూడండి మొదలుపెట్టిన - ఒక, నేను చూడండి చేస్తాము అత్యల్ప ఇండెక్స్, హక్కు ఉండిపోయారు వంటి గోడ, మరియు, రెండు, ఎడమవైపున నేను "ప్రస్తుత పిలుస్తాను ఇది మూలకం, మూలకం. "మనం చేయబోతున్నామని ఉంది ఇతర అన్ని ఇతర మూలకాలను, చూడండి ఇరుసు కంటే, మరియు అన్ని అంశాలు ఉంచారు ఇరుసు కంటే చిన్న గోడ వదిలి మరియు అన్ని ఇరుసు కంటే పెద్ద గోడ యొక్క కుడి. అప్పుడు, చివరకు, మేము ఇరుసు డ్రాప్ చేస్తాము కుడి మధ్య ఉంచండి ఆ గోడపై ఇది కంటే చిన్న అన్ని సంఖ్యలు మరియు అన్ని సంఖ్యలు. 

కాబట్టి యొక్క ఆ తెలియజేసేలా. 2 ఎంచుకొని, గోడ చాలు ప్రారంభమై, 6 "ప్రస్తుత కాల్ మూలకం. "కాబట్టి మేము వద్ద చూడవచ్చు మా ప్రస్తుత మూలకం, 6. మరియు అది కంటే పెద్ద నుండి 2, మేము అక్కడ వదిలి గోడ యొక్క కుడి. అప్పుడు, మేము వంటి 5 చూడండి కొనసాగండి మా ప్రస్తుత మూలకం మరియు చూసే ఈ , మళ్ళీ, 'స్టయిల్ కంటే పెద్ద, కాబట్టి మేము అది కుడి ఉన్న వదిలి గోడ వైపు. మేము కొనసాగండి. మా ప్రస్తుత అంశం ఇప్పుడు 1, - ఓహ్. ఈ ఆడేది. ప్రస్తుత మూలకం ఇప్పుడు తక్కువైతే ఇరుసు, కాబట్టి మేము ఉంచండి మీరు గోడ ఎడమ. ఇది చేయుటకు, యొక్క కేవలం వెళతాను అత్యల్ప ఇండెక్స్ తో ప్రస్తుత మూలకం గోడ యొక్క కుడి కూర్చొని. ఇప్పుడు, మేము ఒక ఇండెక్స్ అప్ గోడ తరలించడానికి కాబట్టి 1 ఎడమవైపు ఇప్పుడు గోడ వైపు. 

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

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

మేము అప్పుడు కోసం ఈ విధానాన్ని పునరుక్తి subarrays వదిలి మరియు ఇరుసు కుడి. గత subarray మాత్రమే ఉంటుంది ఎందుకంటే మూలకం పొడవుగా, మేము ఇప్పటికే తెలుసు క్రమబద్ధీకరించబడతాయి ఎలా మీరు బయటకు ఉంటుంది ఎందుకంటే మీరు ఒకే ఒక అయితే ఆర్డర్? Subarray కుడివైపు, మేము ఇరుసు గోడ 5, మరియు చూడండి కేవలం 6 వదిలేస్తే. మరియు ప్రస్తుత మూలకం కూడా 6 వంటి మొదలవుతుంది. కాబట్టి 6 5 కంటే ఎక్కువ. దానిపై ఉన్న మేము వదిలి గోడ యొక్క కుడి వైపు. ఇప్పుడు, వెళ్లడానికి, 3 5 కంటే తక్కువ. కాబట్టి మేము మొదటి మూలకం తో స్విచ్ గోడ సరైన. ఇప్పుడు నేను ఒక గోడ అప్ తరలించబడింది. ఇప్పుడు, 8 వెళ్ళేముందు. 8, 5 కంటే ఎక్కువ అందువలన మేము వదిలి. 4 కంటే తక్కువ 5, కాబట్టి మేము ఇది మారడం. మరియు. మరియు. 

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

ఈ పద్ధతి బాగా పనిచేస్తుంది ఉంటే ఎంపిక ఇరుసు విలువ ఉంది సుమారు మధ్యలో జాబితాలో విలువలు పరిధి. మేము తరలించడానికి తర్వాత ఈ, అర్థం అనేక గురించి చుట్టూ అంశాలను, ఇరుసు ఎడమవైపున అంశాలు కుడి ఉన్నాయి. మరియు యొక్క విభజన మరియు జయించటానికి ప్రకృతి Quicksort అల్గోరిథం తర్వాత తీసుకుంటారు పూర్తి ప్రయోజనం. ఈ O ఒక runtime సృష్టిస్తుంది (n లాగ్ n,) మేము n మైనస్ 1 n ఎందుకంటే ప్రతి తరం మరియు లాగ్ న పోలికలు మేము జాబితా విభజించడానికి కలిగి n ఎందుకంటే n సార్లు లాగ్. అయితే, చెత్త సందర్భాలలో, ఈ క్రమసూత్ర పద్ధతి నిజానికి O (n ఉంటుంది స్క్వేర్డ్.) ప్రతి తరం మీద ఊహించు, ఇరుసు కేవలం నిర్మాణము చిన్న లేదా పెద్ద మేము క్రమబద్ధీకరించేందుకు చేస్తున్నారు సంఖ్యలు. ఈ జాబితా విడగొట్టి అర్థం సార్లు మరియు మేకింగ్ n మైనస్ 1 n పోలికలు ప్రతి సమయం. అందువలన, n ఓ స్క్వేర్డ్. 

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

నా పేరు, మార్క్ Grozen-స్మిత్ ఉంది మరియు ఈ CS50 ఉంది. 

సాధారణంగా, యొక్క ఊహించుకోవటం తెలియజేయండి ఆ విషయాలు కేవలం పూర్ణ, కానీ ఆ Quicksert తెలుసు - Quicksert? క్షమించాలి. 

ఇక్కడ మేము పూర్ణాంకాల కలిగి 6, 5, 1, 3, 8, 4, 9. 

SPEAKER 1: రియల్లీ? 

SPEAKER 2: అక్కడ స్టాప్ లేదు. 

SPEAKER 1: రియల్లీ?