>> ડો LLOYD: તેથી CS50 માં અમે શીખ્યા વર્ગીકરણ અને શોધ વિવિધ
ગાણિતીક નિયમો.
અને ક્યારેક તે હોઈ શકે છે ઓછી રાખવા માટે મુશ્કેલ
શું અલ્ગોરિધમનો ટ્રેક શું કરે છે.
અમે ખરેખર માત્ર કર્યું પણ સપાટી મલાઇ તારવેલાં
અન્ય ઘણા શોધ છે અને સોર્ટિંગ એલ્ગોરિધમ્સ.
આ વિડીયો માં ચાલો માત્ર થોડી મિનિટો લે છે
પ્રયત્ન કરો અને દરેક અલ્ગોરિધમનો distill માટે તેના કોર તત્વો નીચે
જેથી તમે સૌથી યાદ કરી શકો છો તેમને વિશે મહત્વની જાણકારી
અને સ્પષ્ટ કરવા માટે સમર્થ હશે તફાવતો, જો જરૂરી હોય તો.
>> પ્રથમ પસંદગી જેવું છે.
પસંદગી સૉર્ટ પાછળનો મૂળ ખ્યાલ નાના ક્રમમાંગોઠવાયેલનથી તત્વ શોધવા છે
અને ઝાકઝમાળ સાથે તે સ્વેપ કે એરે પ્રથમ ક્રમમાંગોઠવાયેલનથી તત્વ.
અમે સૌથી ખરાબ કેસ જણાવ્યું હતું કે કે રન સમય સ્ક્વેર્ડ n આવી હતી.
અને તમે શા માટે યાદ કરવા માંગો છો, તો લેવા એક પસંદગી સૉર્ટ વિડિઓ જુઓ.
શ્રેષ્ઠ કેસ રન સમય પણ સ્ક્વેર્ડ n છે.
>> બબલ સૉર્ટ કરો, કે પાછળનો એક અડીને જોડીઓ સ્વેપ છે.
કે જેથી તમે મદદ કરે છે કે કી છે અહીં તફાવત યાદ કરે છે.
પસંદગી જેવું છે, અત્યાર સુધી, આ smallest-- બબલ શોધવા
સૉર્ટ અડીને જોડીઓ સ્વેપ.
આપણે સંલગ્ન જોડીઓ સ્વેપ તત્વો જો તેઓ
જે અસરકારક રીતે હુકમ બહાર છે જમણી મોટા તત્વો પરપોટા
અને તે જ સમયે તે પણ શરૂ થાય છે ડાબી નાના તત્વો ખસેડવા.
ખરાબ કેસ કેસ રન સમય બબલ પ્રકારના સ્ક્વેર્ડ n છે.
શ્રેષ્ઠ કેસ રન સમય બબલ સૉર્ટ n છે.
કારણ કે પરિસ્થિતિ અમે વાસ્તવમાં નથી
અમે જરૂર પડી શકે છે બધા કોઇ અદલબદલ બનાવે છે.
અમે ફક્ત એક બનાવવા માટે હોય છે તમામ n તત્વોના સમગ્ર પસાર કરે છે.
>> નિવેશ સૉર્ટ માં, અહીં મૂળભૂત વિચાર સ્થળાંતર થયેલ છે.
એટલે કે નિવેશ સૉર્ટ માટે કીવર્ડ છે.
અમે મારફતે એક વખત પગલું જઈ રહ્યાં છો ના એરે ડાબેથી જમણે.
અમે જેમ, અમે છો તત્વો પાળી રહ્યું
અમે પહેલેથી જ માટે જગ્યા બનાવવા માટે જોઇ ક્યાંક ફિટ કરવાની જરૂર છે કે નાનાઓ
પાછા છટણી ભાગ.
તેથી અમે છટણી એરે બિલ્ડ એક ડાબેથી જમણે એક સમયે તત્વ,
અને અમે રૂમ બનાવવા માટે વસ્તુઓ પાળી.
સૌથી ખરાબ કેસ રન સમય નિવેશ સૉર્ટ સ્ક્વેર્ડ n છે.
શ્રેષ્ઠ કેસ ચલાવવા સમય n છે.
>> શબ્દ સૉર્ટ મર્જ અહીં વિભાજિત અને મર્જ કરવામાં આવે છે.
અમે શું સંપૂર્ણ એરે વિભાજિત તે છ તત્વો, આઠ તત્વો છે,
10,000 elements-- અમે તેને વિભાજિત નીચે અડધા દ્વારા અડધા દ્વારા અડધા દ્વારા,
અમે એરે હેઠળ હોય ત્યાં સુધી એ એક તત્વ એરે.
એ એક તત્વ એરે એક સમૂહ.
તેથી અમે એક સાથે શરૂ 1000-તત્વ એરે,
અને અમે બિંદુ મેળવવા જ્યાં અમે 1000 એક તત્વ એરે છે.
પછી અમે તે પેટા એરે મર્જ કરવા શરૂ ફરી પાછા સાથે યોગ્ય ક્રમમાં.
તેથી અમે બે એક તત્વ એરે લેવા અને બે-તત્વ એરે બનાવો.
અમે બે બે તત્વ એરે લેવા અને ચાર તત્વ એરે બનાવો
અને તેથી પર અને તેથી પર અમે કર્યું ત્યાં સુધી ફરી એક એ તત્વ એરે પુનઃબીલ્ડ.
>> સૌથી ખરાબ કેસ રન સમય સૉર્ટ મર્જ n વખત લોગ એન.
અમે n તત્વોના હોય છે, પરંતુ આ recombining પ્રક્રિયા
લૉગ લે n પગલાંઓ વિચાર સંપૂર્ણ એરે પાછા.
સમય ચાલે શ્રેષ્ઠ કેસ પણ એ લોગ છે એ આ પ્રક્રિયા ખરેખર નથી કારણ કે
એરે હતી કે કેમ તે કાળજી સૉર્ટ નથી અથવા સાથે શરૂ કરવા માટે.
આ પ્રક્રિયા છે, એ જ છે શોર્ટ સર્કિટ વસ્તુઓ કરવા માટે કોઈ રીત.
તેથી એ સૌથી ખરાબ કિસ્સામાં n લોગ, n શ્રેષ્ઠ કિસ્સામાં n લોગ.
>> અમે બે વિશે વાત કરી ગાણિતીક નિયમો શોધ.
તેથી રેખીય શોધ વારો છે.
અમે એરે સમગ્ર આગળ વધો એકવાર, ડાબેથી જમણે કરવા માટે,
સંખ્યા શોધવા માટે પ્રયાસ કરી કે અમે શોધી રહ્યાં છે.
ખરાબ કેસ ચલાવવા સમય n ના મોટા ઓ છે.
તે વારો અમને લાગી શકે છે દરેક એક તત્વ સમગ્ર
અમે શોધી રહ્યાં છો તે તત્વ શોધવા માટે માટે, ક્યાં તો છેલ્લા સ્થિતીમાં,
અથવા તમામ નથી.
પરંતુ અમે ત્યાં સુધી તેની ખાતરી કરી શકો છો અમે બધું જોવામાં કર્યું છે.
શ્રેષ્ઠ કેસ છું, અમે તુરંત જ શોધી.
શ્રેષ્ઠ કેસ રન સમય રેખીય શોધ 1 ઓમેગા છે.
>> છેલ્લે, દ્વિસંગી શોધ હતી, જે મિશ્રિત એરે જરૂરી છે.
કે ખૂબ જ છે યાદ રાખો મહત્વપૂર્ણ વિચારણા
દ્વિસંગી શોધ સાથે કામ કરે છે.
તે તેને ઉપયોગ કરવા માટે એક પૂર્વશરત છે તમે મારફતે શોધી રહ્યા છો કે જે એરે
સૉર્ટ હોવું જ જોઈએ.
નહિંતર, શબ્દ ભાગલા પાડો અને કોન્કર છે.
અડધા માં એરે વિભાજિત અને તત્વો અડધા દૂર
દર વખતે તમે મારફતે આગળ વધવા.
કારણ કે ભાગાકાર અને કોન્કર ના અને અડધા અભિગમ વિભાજન વસ્તુઓ
ખરાબ કેસ રન સમય દ્વિસંગી શોધ છે
નોંધપાત્ર છે, જે n લોગ રેખીય શોધ માતાનો n કરતાં વધુ સારી.
શ્રેષ્ઠ કેસ ચલાવવા સમય હજુ પણ એક છે.
>> અમે તરત જ તેને શોધી શકે છે પ્રથમ વખત અમે એક વિભાગ કરે છે, પરંતુ
ફરીથી, યાદ રાખો કે દ્વિસંગી શોધ છે, તેમ છતાં
રેખીય શોધ કરતાં નોંધપાત્ર રીતે લોગ હોવાની સદ્ગુણ દ્વારા N N વિરુદ્ધ,
તમે વર્ક મારફતે જાઓ હોય શકે પ્રથમ તમારા એરે સૉર્ટ જે
આધાર રાખીને તે ઓછી અસરકારક બનાવવા શકે છે સૉર્ટ વારો માપ પર.
>> હું ડો લોયડ છું, આ CS50 છે.