[இசை] டக் LLOYD: தேர்வு வகையான ஆகிறது நீங்கள் எதிர்பார்ப்பது போல என்று, வழிமுறை, கூறுகளை ஒரு தொகுப்பு படுகின்றன. மற்றும் வழிமுறை நினைவு ஒரு படி மூலம் படி தொகுப்பு ஆகும் ஒரு பணி முடித்த வழிமுறைகளை. 

தேர்வு தீர்த்துக்கொள்ள அடிப்படை கருத்து, இந்த ஆகிறது சிறிய வரிசையாக்கம் செய்யப்படாத உறுப்பு கண்டுபிடிக்க வேண்டும் வரிசைப்படுத்தப்பட்ட பட்டியலை இறுதியில் அதை சேர்க்க. திறம்பட இந்த என்ன உருவாக்க உள்ளது ஒரு வரிசைப்படுத்தப்பட்ட பட்டியலை, ஒரு நேரத்தில் ஒரு உறுப்பு. சூடோகுறியீடு அதை உடைக்கும் நாம் இந்த வழிமுறை கூற முடியும் பின்வருமாறு வரை இந்த திரும்பவும் எந்த வரிசையாக்கம் செய்யப்படாத கூறுகள் இருக்கின்றன. வரிசையாக்கம் செய்யப்படாத மூலம் தேட தரவு சிறிய மதிப்பு கண்டுபிடிக்க, பின்னர் கொண்ட சிறிய மதிப்பு இடமாற்றம் வரிசையாக்கம் செய்யப்படாத பகுதி முதல் உறுப்பு. 

அது, இந்த கற்பனை உதவலாம் எனவே இந்த பாருங்கள் நாம். எனவே இந்த நான் வாதிடுவேன், ஒரு ஆகிறது வரிசையாக்கம் செய்யப்படாத வரிசை மற்றும் நான் அனைத்து எனக் காட்டுவது அது சுட்டிக்காட்டப்படுத்தது உறுப்புகள், சிவப்பு நிற அவர்கள் இன்னும் சரியாகவில்லை. இந்த முழு ஆகிறது வரிசை வரிசையாக்கம் செய்யப்படாத பகுதி. 

எனவே படிகள் வழியாக செல்லலாம் தேர்வு வகையான இந்த வரிசையில் அடுக்க. எனவே மீண்டும், நாம் செய்ய போகிறோம் மீண்டும் இருக்கிறோம் எந்த வரிசையாக்கம் செய்யப்படாத கூறுகள் இருக்கின்றன வரை. நாம் மூலம் போகிறேன் தேடல் இருக்கிறோம் தரவு சிறிய மதிப்பு கண்டுபிடிக்க, பின்னர் அந்த மதிப்பு இடமாற்றம் வரிசையாக்கம் செய்யப்படாத பகுதி முதல் உறுப்பு. 

இப்போது, மீண்டும், முழு வரிசை வரிசையாக்கம் செய்யப்படாத பகுதியாக உள்ளது. சிவப்பு கூறுகள் அனைத்து வரிசையாக்கம் செய்யப்படாத உள்ளன. எனவே நாம் மூலம் தேட மற்றும் நாங்கள் சிறிய மதிப்பை கண்டுபிடிக்க. நாம் ஆரம்பத்தில் தொடங்க நாம் இறுதியில் செல்ல நாங்கள் சிறிய மதிப்பு, ஒன்றாகும் கண்டுபிடிக்கிறோம். எனவே அந்த பகுதி ஒன்று தான். பின்னர் இரண்டு பகுதியாக, அந்த மதிப்பு இடமாற்றம் வரிசையாக்கம் செய்யப்படாத பகுதி முதல் உறுப்பு, அல்லது முதல் சிவப்பு உறுப்பு. 

இந்த வழக்கில் இருக்கும் என்று ஐந்து, நாம் ஒன்று முதல் ஐந்து பரிமாறிக்கொள்ளலாம். நாங்கள் இதை செய்ய போது, நாம் முடியும் பார்வை நாங்கள் என்னால் பார்க்க சிறிய மதிப்பு உறுப்பு சென்றார் வரிசை, ஆரம்பத்தில். திறம்பட அந்த உறுப்பு வரிசைப்படுத்த. 

எனவே நாம் உண்மையில் உறுதிப்படுத்த முடியும் மற்றும் மாநில ஒன்று என்று, வரிசைப்படுத்தப்பட்ட. அதனால் நாம் வரிசைப்படுத்தப்பட்ட பகுதி குறிக்க வேண்டும் எங்கள் அணி, அது நீல வண்ணத்தில் மூலம். 

இப்போது நாம் இப்போது மீண்டும் செயல்முறை மீண்டும். நாம் வரிசையாக்கம் செய்யப்படாத பகுதி மூலம் தேட வரிசை சிறிய உறுப்பு கண்டுபிடிக்க. இந்த வழக்கில், இது இரண்டு ஆகும். 

நாம் முதல் அந்த இடமாற்ற வரிசையாக்கம் செய்யப்படாத பகுதி உறுப்பு. இந்த வழக்கில் இருவரும் இருக்கும் நடக்கிறது வரிசையாக்கம் செய்யப்படாத பகுதி முதல் உறுப்பு. எனவே நாம் தன்னை இரண்டு இடமாற்றம், இது உண்மையில் இரண்டு இலைகள் அது, இது வரிசைப்படுத்தப்பட்ட எங்கே. தொடர்ந்து, நாங்கள் மூலம் தேட சிறிய உறுப்பு கண்டுபிடிக்க. அது மூன்று தான். நாம் முதலில் அதை அதை இடமாற்றம் ஐந்து இது உறுப்பு,. இப்போது மூன்று பிரிக்கப்பட்டுள்ளது. 

நாங்கள் மீண்டும் மூலம் தேட, நாம் சிறிய உறுப்பு நான்கு ஆகும் கண்டறிய. நாம் முதல் உறுப்பு அது பரிமாறிக்கொள்ளலாம் வரிசையாக்கம் செய்யப்படாத பகுதி, இப்போது நான்கு பிரிக்கப்பட்டுள்ளது. 

நாங்கள் ஐந்து என்று கண்டுபிடிக்க சிறிய உறுப்பு. நாம் முதலில் அதை அதை இடமாற்றம் வரிசையாக்கம் செய்யப்படாத பகுதி உறுப்பு. இப்போது ஐந்து பிரிக்கப்பட்டுள்ளது. 

பின்னர் இறுதியாக, எங்கள் வரிசையாக்கம் செய்யப்படாத பகுதி கொண்டிருக்கிறது ஒரு ஒற்றை உறுப்பு, எனவே நாம் மூலம் தேட நாம் ஆறு என்று கண்டுபிடிக்க சிறிதான உண்மையில், ஒரே உறுப்பு. பின்னர் நாம் அது வரிசைப்படுத்தப்பட்ட என்று கூற முடியும். இப்போது நாங்கள் எங்கள் அணி மாறியது முற்றிலும் வரிசையாக்கம் இருந்து சிவப்பு, முற்றிலும் வரிசைப்படுத்தப்பட்ட நீல, தேர்வு வகையான பயன்படுத்தி. 

எனவே மோசமான சூழ்நிலையில் இங்கே என்ன? சரி மிகவும் மோசமான உள்ள வழக்கு, நாம் பார்த்து வேண்டும் வரிசை கூறுகளை அனைத்து சிறிய வரிசையாக்கம் செய்யப்படாத உறுப்பு காணலாம், மற்றும் நாம் மீண்டும் வேண்டும் இந்த செயல்முறை n முறை. வரிசை ஒவ்வொரு உறுப்பு ஒரு முறை நாம் மட்டுமே, ஏனெனில், இந்த வழிமுறைகளில், நேரத்தில் வகையான ஒரு உறுப்பு. 

சிறந்த வழக்கு சூழ்நிலையில் என்ன? சரி அது சரி, சரியாக அதே தான்? நாம் உண்மையில் இன்னும் மூலம் விலக வேண்டும் வரிசை ஒவ்வொரு உறுப்பு பொருட்டு, அதை என்பதை உறுதிப்படுத்த உண்மையில், சிறிய உறுப்பு. 

எனவே மோசமான இயக்க, நாங்கள் ஒரு செயல்முறை n முறை மீண்டும் வேண்டும், n உறுப்புகள் ஒவ்வொரு முறை. மற்றும் சிறந்த சூழ்நிலையில், நாம் அதே செய்ய வேண்டும். 

எனவே மீண்டும் நினைத்து எங்கள் கணிப்பு சிக்கலான கருவி பெட்டி, நீங்கள் என்ன நினைக்கிறீர்கள் மோசமான உள்ளது தேர்வு வகையான வழக்கு இயக்க? என்ன நினைக்கிறீர்கள் சிறந்த தேர்வு வகையான வழக்கு இயக்க? 

ஸ்கொயர் n நீங்கள் பிக் ஓ யூகித்தாய், மற்றும் பெரிய ஒமேகா ஸ்கொயர் n? நீங்கள் சரியான இருக்கும். அவையாவன, உண்மையில், மிக மோசமான நிலையில் மற்றும் சிறந்த வழக்கு ரன் தேர்வு வகையான முறை,. 

நான் டக் லாயிட் இருக்கிறேன். இந்த CS50 உள்ளது.