MARK GROZEN-SMITH: Hi, நான் மார்க் இருக்கிறேன் ஸ்மித் Grozen, இந்த விரைவு உள்ளது. வெறும் செருகும் வரிசையாக்கம் மற்றும் குமிழி போல் வகையான, விரைவு ஒரு வழிமுறை இருக்கிறது ஒரு பட்டியல் அல்லது விஷயங்களை ஒரு வரிசை வரிசைப்படுத்த. எளிமை, தான் வைத்து கொள்வோம் என்று அந்த விஷயங்கள் மட்டும் முழு உள்ளன, ஆனால் விரைவு வேலை என்று எனக்கு தெரியும் வெறும் எண்கள் விட. விரைவு சற்று சிக்கலான ஆகிறது விட செருகும் அல்லது குமிழ், ஆனால் அது தான் மேலும் மிகவும் திறமையான பெரும்பாலான சந்தர்ப்பங்களில். இரண்டாவது காத்திருக்க. அவர் தான் "மிகவும் சொன்னார்களா வழக்குகள், "இல்லை" அனைத்து "? சுவாரஸ்யமாக, இல்லை. எல்லா நேரங்களில் அதே இருக்கின்றன. இந்த விவரம் பற்றி கவலைப்பட வேண்டாம் நீங்கள் இன்னும் பெரிய ஓ குறிப்பு காணப்படுகிறது, ஆனால் இல்லை விரைவு O (n ஸ்கொயர்) வழிமுறை மோசமான, போல் செருகும் அல்லது குமிழி வரிசையாக்கம். எனினும், இது வழக்கமாக மிக செயல்படுகிறது ஒரு பழைய அனலாக் மீ வழிமுறை போன்ற. ஏன்? நாம் பின்னர் மீண்டும் அது கிடைக்கும். ஆனால் இப்போது, தான் கற்று கொள்வோம் விரைவு எப்படி வேலை செய்கிறது. 

எனவே இந்த 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. அங்கு இருந்து, நாம் வரிசை வரிசைப்படுத்தப்பட்ட அறிகிறோம் ஒவ்வொரு உறுப்பு உள்ளது, ஏனெனில், அன்று சில புள்ளி, ஒரு மையத்தை வருகிறது. வேறுவிதமாக கூறினால், ஒவ்வொரு உறுப்பு, அனைத்து இடது எண்கள் குறைந்த இருக்கின்றன மதிப்புகள் மற்றும் அனைத்து எண்கள் வலது அதிக மதிப்புகளை கொண்டுள்ளது. 

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

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

என் பெயர், மார்க் Grozen ஸ்மித் ஆகிறது மற்றும் இந்த CS50 உள்ளது. 

எளிமை, தான் வைத்து கொள்வோம் என்று அந்த விஷயங்கள் மட்டும் முழு உள்ளன, ஆனால் என்று Quicksert தெரியும் - Quicksert? மன்னிக்கவும். 

இங்கே நாம் முழு வேண்டும் 6, 5, 1, 3, 8, 4, 9. 

காண்க: 1 உண்மையாகவா? 

காண்க 2: அங்கு நிறுத்த கூடாது. 

காண்க: 1 உண்மையாகவா?