>> માર્ક GROZEN-સ્મિથ: હાય, હું માર્ક છું સ્મિથ Grozen, અને આ Quicksort છે.
જસ્ટ દાખલ સૉર્ટ કરો અને બબલ જેવી સૉર્ટ કરો, Quicksort માટે અલ્ગોરિધમનો છે
યાદી અથવા વસ્તુઓ ઝાકઝમાળ સૉર્ટ.
સરળતા માટે, ચાલો ધારે છે કે જેઓ વસ્તુઓ માત્ર પૂર્ણાંકો હોય છે, પરંતુ
Quicksort માટે કામ કરે છે ખબર માત્ર નંબરો કરતાં વધુ.
ક્વિકસ્ટાર્ટ થોડી વધુ જટિલ છે કરતાં નિવેશ અથવા બબલ, પરંતુ તે છે
પણ વધારે કાર્યક્ષમ મોટા ભાગના કિસ્સાઓમાં.
બીજી રાહ જુઓ.
તે માત્ર "મોટા ભાગના કહે છે શું કિસ્સાઓમાં, "નથી" તમામ "?
રસપ્રદ રીતે, કોઈ.
બધા કિસ્સાઓમાં સમાન હોય છે.
આ વિગત વિશે ચિંતા કરશો નહીં તમે જો હજુ સુધી મોટી ઓ નોટેશનમાં જોવા મળે છે, પરંતુ છે
Quicksort એક ઓ (એન સ્ક્વેર્ડ) એલ્ગોરિધમ છે સૌથી ખરાબ છે, જેમ
નિવેશ અથવા બબલ સૉર્ટ કરો.
જો કે, તે સામાન્ય રીતે વધુ કામ કરે છે જૂની એનાલોગ મીટર અલ્ગોરિધમનો છે.
શા માટે?
અમે પછી પાછા તે માટે મળશે.
પરંતુ હવે માટે છે, માત્ર શીખીએ Quicksort કેવી રીતે કામ કરે.
>> તેથી આપણે આ Quicksorting લઈ જવામાં દો નાના થી પૂર્ણાંકો એરે
સૌથી માટે.
અહ તે પૂર્ણાંકો 6 છે 5, 1, 3, 8, 4, 7, 9, અને 2.
પ્રથમ, અમે અંતિમ તત્વ પસંદ આ એરે - આ કિસ્સામાં, બે -
અને તે "ધરી." કૉલ પછી, આપણે બે વસ્તુઓ જોવા શરૂ -
એક, હું સંદર્ભ લો પડશે જે સૌથી ઓછી અનુક્રમણિકા, અધિકાર છે માટે રહેતા તરીકે
દિવાલ, અને, બે, પાંચ leftmost હું "વર્તમાન કહી શકશો કે જે તત્વ છે,
ઘટક. "અમે શું કરી રહ્યા છીએ છે અન્ય બીજા બધા તત્વો, જુઓ
ધરી કરતા, અને તમામ ઘટકો મૂકવા આ માટે ધરી કરતા નાની
દિવાલ છોડી અને તે બધા આ માટે ધરી કરતાં મોટી
દિવાલ અધિકાર.
પછી, છેવટે, અમે ધરી મૂકવા પડશે અધિકાર વચ્ચે મૂકવા કે દિવાલ પર
તે કરતા નાની બધી સંખ્યાઓ અને તમામ નંબરો મોટા.
>> તેથી આપણે તે કરીએ.
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 અલ્ગોરિધમનો પછી લેવામાં આવે છે
પૂર્ણ લાભ.
આ ઓ એક રનટાઈમ બનાવે (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 વક્તા: ખરેખર?