[સંગીત વગાડવાનો] ડો LLOYD: પસંદગી સૉર્ટ છે તમે આશા રાખી શકે છે કે, અલ્ગોરિધમનો તત્વોના સમૂહના ગોઠવે છે. અને અલ્ગોરિધમનો રિકોલ એક પગલું દ્વારા પગલું સમૂહ છે એક કાર્ય પૂર્ણ કરવા માટે સૂચનો. 

પસંદગી સૉર્ટ મૂળભૂત વિચાર, આ છે નાના ક્રમમાંગોઠવાયેલનથી તત્વ શોધવા અને છટણી યાદી ઓવરને ઉમેરો. અસરકારક રીતે આ શું કરે છે બિલ્ડ છે એક છટણી યાદી, એક સમયે એક તત્વ. સ્યુડોકોડનો તે તોડી અમે આ અલ્ગોરિધમનો રાજ્ય શકે નીચે પ્રમાણે સુધી આ પુનરાવર્તન કોઈ ક્રમમાંગોઠવાયેલનથી તત્વો રહે છે. ક્રમમાંગોઠવાયેલનથી દ્વારા શોધો માહિતી નાના કિંમત શોધવા માટે, પછી સાથે નાના કિંમત સ્વેપ ક્રમમાંગોઠવાયેલનથી ભાગ પ્રથમ તત્વ. 

તે આ વિઝ્યુઅલાઈઝ મદદ કરી શકે છે તેથી આપણે આ પર એક નજર કરીએ. તેથી આ હું દલીલ, એક છે ક્રમમાંગોઠવાયેલનથી એરે અને હું કર્યું બધા જે દર્શાવે છે કે તેને સંકેત તત્વો, લાલ રંગના હોય છે તેઓ હજુ સુધી નથી સૉર્ટ થાય છે. આ સમગ્ર છે એરે ક્રમમાંગોઠવાયેલનથી ભાગ. 

તેથી આપણે પગલાંઓ મારફતે જાઓ પસંદગી સૉર્ટ આ એરે સૉર્ટ. તેથી ફરી, અમે તેમ વારંવાર છો કોઈ ક્રમમાંગોઠવાયેલનથી તત્વો રહે છે ત્યાં સુધી. અમે મારફતે તેમ શોધ કરો છો માહિતી નાના કિંમત શોધવા માટે, અને પછી સાથે કિંમત સ્વેપ ક્રમમાંગોઠવાયેલનથી ભાગ પ્રથમ તત્વ. 

હમણાં, ફરીથી, આ સમગ્ર એરે ક્રમમાંગોઠવાયેલનથી ભાગ છે. લાલ બધા તત્વો ક્રમમાંગોઠવાયેલનથી છે. તેથી અમે મારફતે શોધવા અને અમે નાના કિંમત શોધવા. અમે શરૂઆતમાં શરૂ અમે ઓવરને પર જાઓ અમે નાના કિંમત છે, એક છે શોધવા. તેથી તે એક ભાગ છે. અને પછી બે ભાગ સાથે, તે કિંમત સ્વેપ ક્રમમાંગોઠવાયેલનથી ભાગ પ્રથમ તત્વ, અથવા પ્રથમ લાલ તત્વ. 

આ કિસ્સામાં હશે કે પાંચ, તેથી અમે એક અને પાંચ સ્વેપ. અમે આ કરો છો, ત્યારે અમે કરી શકો છો દૃષ્ટિની અમે જોયું છે કે નાના મૂલ્ય તત્વ ખસેડવામાં એરે, ખૂબ શરૂઆતમાં છે. અસરકારક રીતે તે તત્વ સૉર્ટ. 

અને તેથી અમે ખરેખર ખાતરી કરી શકો છો અને રાજ્ય એક કે છટણી કરવામાં આવે છે. અને તેથી અમે છટણી ભાગ સૂચવે પડશે અમારા એરે, તે વાદળી રંગ દ્વારા. 

હવે અમે ફક્ત ફરીથી પ્રક્રિયા પુનરાવર્તન કરો. અમે ક્રમમાંગોઠવાયેલનથી ભાગ મારફતે શોધવા એરે નાના તત્વ શોધવા માટે. આ કિસ્સામાં, તે બે છે. 

અમે પ્રથમ સાથે સ્વેપ ક્રમમાંગોઠવાયેલનથી ભાગ તત્વ. આ કિસ્સામાં બે પણ બને ક્રમમાંગોઠવાયેલનથી ભાગ પ્રથમ તત્વ. તેથી અમે પોતે સાથે બે સ્વેપ, જે ખરેખર માત્ર બે નહીં તે છે, અને તે છટણી છે જ્યાં. પર સતત, અમે મારફતે શોધવા નાના તત્વ શોધવા માટે. તે ત્રણ છે. અમે પ્રથમ સાથે સ્વેપ પાંચ છે જે તત્વ. અને હવે ત્રણ છટણી કરવામાં આવે છે. 

અમે ફરીથી શોધવા, અને અમે નાના તત્વ ચાર છે શોધવા. અમે પ્રથમ તત્વ સાથે સ્વેપ ક્રમમાંગોઠવાયેલનથી ભાગ છે, અને હવે ચાર છટણી કરવામાં આવે છે. 

અમે પાંચ કે શોધવા નાના તત્વ. અમે પ્રથમ સાથે સ્વેપ ક્રમમાંગોઠવાયેલનથી ભાગ તત્વ. અને હવે પાંચ છટણી કરવામાં આવે છે. 

અને પછી છેલ્લે, અમારા ક્રમમાંગોઠવાયેલનથી ભાગ સમાવે છે માત્ર એક જ તત્વ છે, તેથી અમે મારફતે શોધવા અને અમે છ છે કે જે શોધી નાના, અને હકીકતમાં, માત્ર તત્વ. અને પછી અમે તેને છટણી કરવામાં આવે છે કે રાજ્ય શકો છો. અને હવે અમે અમારા એરે ફેરવાઈ કર્યું સંપૂર્ણપણે ક્રમમાંગોઠવાયેલનથી થવાથી લાલ, સંપૂર્ણપણે છટણી માટે વાદળી, પસંદગી સૉર્ટ મદદથી. 

તેથી સૌથી ખરાબ કેસ દૃશ્ય અહીં શું છે? વેલ ચોક્કસ ખરાબ કેસ, અમે ઉપર જોવા માટે હોય છે એરે તત્વો તમામ નાના ક્રમમાંગોઠવાયેલનથી તત્વ શોધવા અને અમે પુનરાવર્તન છે આ પ્રક્રિયા n વખત. એરે દરેક તત્વ માટે એકવાર અમે માત્ર કારણ કે, આ અલ્ગોરિધમનો માં, સમયે સૉર્ટ એક તત્વ. 

શ્રેષ્ઠ કેસ દૃશ્ય શું છે? વેલ તે અધિકાર, બરાબર એ જ છે? અમે ખરેખર હજુ પણ મારફતે પગલું છે એરે દરેક એક તત્વ માટે, તે છે તેની ખાતરી કરવા માટે હકીકતમાં, નાના તત્વ. 

તેથી ખરાબ કેસ રનટાઇમ, અમે પ્રક્રિયા n વખત પુનરાવર્તન છે, n તત્વો દરેક માટે એક વાર. અને શ્રેષ્ઠ કેસ દૃશ્ય માં, અમે એ જ કરી છે. 

તેથી પાછા વિચારવાનો અમારા ગણતરીની જટિલતા શોધો, શું તમે વિચારો છો સૌથી ખરાબ છે પસંદગી સૉર્ટ કેસ રનટાઈમ? તમે શું વિચારો છો શ્રેષ્ઠ છે પસંદગી સૉર્ટ કેસ રનટાઈમ? 

સ્ક્વેર્ડ n તમે મોટા ઓ ધારી હતી, અને મોટા ઓમેગા સ્ક્વેર્ડ n ના? તમે જમણી હશો. તે છે, હકીકતમાં, ખરાબ કેસ અને શ્રેષ્ઠ કેસ રન પસંદગી સૉર્ટ વખત. 

હું ડો લોયડ છું. આ CS50 છે.