[Powered by Google Translate] [સૉર્ટ કરો મર્જ કરો] [રોબ બોડેન - હાર્વર્ડ યુનિવર્સિટી] [આ CS50 છે. - CS50.TV] ચાલો મર્જ સૉર્ટ વિશે વાત કરો. અત્યાર સુધી તમે બબલ સૉર્ટ કરો, નિવેશ સૉર્ટ કરો, અને પસંદગી સૉર્ટ જોઇ છે. જોકે હું પડશે હું શું વધુ સારી દ્વારા અર્થ મારા હાથ મોજું પ્રકારની, મર્જ સૉર્ટ સામાન્ય રીતે આ પ્રકારની 3 કોઈપણ કરતાં વધુ સારી કામગીરી બજાવે છે. 

પરંતુ મર્જ સૉર્ટ વિશે વાત કરતાં પહેલાં, ચાલો 2 છટણી યાદીઓ મર્જ વિશે વાત કરો. અમે આ જેવા 2 છટણી યાદીઓ લેવાની પ્રક્રિયા, કૉલ કરશો, અને તેમને એક જ છટણી યાદી બહાર બનાવે છે - યાદીઓ મર્જ. અમે આ કેવી રીતે કરી શકો છો? વેલ, એક વિચાર માત્ર બીજી યાદી ઓવરને પર એક યાદી વળગી છે અને પછી પરિણામી યાદીમાં સૉર્ટ. 

જ્યારે આ કામ કરે છે, તે બિનજરૂરી કામ ઘણું છે. અમે તે માત્ર સૉર્ટ કરતાં વધુ ઝડપથી કરી શકો છો. નોંધ કરો કે એક ખોટું વિચાર માત્ર દરેક યાદીમાંથી વૈકલ્પિક કપ લેવાનું હોય છે. જ્યારે કે જે કામો જેવા પ્રથમ લાગે, આમ કે અમે 4, 8, 15, 23, 16 સાથે અંત - સૂચના કે 16 અને 23 સ્થળ ગઈ છે. આ કારણ છે કે 2 તત્વો કે મર્જ યાદીમાં સતત દેખાવા જોઈએ એ જ પ્રારંભિક યાદી છે. 15 અને 16 એમ બંને ડાબી બાજુ પર યાદી છે. આ યુક્તિ એ હકીકત છે કે બંને યાદીઓ પહેલાથી જ અલગ પાડવામાં આવે છે લાભ લેવા છે. આનો અર્થ એ થાય કે જો અમે માત્ર બંને યાદીઓ પ્રથમ તત્વો જોવા - અહીં, 4 અને 8 - તેમાંના એક પણ મર્જ યાદી પ્રથમ તત્વ હોવા જ જોઈએ. વેલ, તે શા માટે છે? આ યાદીઓ બંને પહેલેથી જ છટણી કરવામાં આવે છે, અને તેથી 4 અથવા 8 નાના તત્વ હોય ત્યારે અમે 2 યાદીઓ ભેગા જ જોઈએ. આ કિસ્સામાં, નાના 4 છે, તેથી અમે 4 લાગી શકે છે અને તે અમારા મર્જ યાદી પ્રથમ તત્વ બનાવે છે. હવે અમે પ્રથમ યાદી બાકીના 3 તત્વો ભળીને ચાલુ રાખવા અને બીજી યાદી 4 તત્વો છે. 

ફરી એકવાર, અમે માત્ર બંને યાદીઓ પ્રથમ તત્વ અંતે જોવાની જરૂર નથી. 2 ની નાની અમારા મર્જ યાદી બીજા તત્વ હોવા જ જોઈએ. આ સમય, 8 અને 15 વચ્ચે નાના 8 છે, અને તેથી અમે દાખલ કરો કે જે અમારા છટણી યાદી બીજા તત્વ તરીકે. અમે બંને યાદીઓ પ્રથમ તત્વો સાથે સરખામણી ચાલુ રાખી શકો છો અને 2 ના નાના દૂર કરીને. 15 અને 15 23, સરખામણી નાના અને જેથી અમારા ત્રીજા તત્વ છે. હવે 16 સરખામણી અને 23, 16 ઓછી છે. જેથી ચોથા તત્વ છે. 

નોંધ કરો કે 2 તત્વો પંક્તિ એ જ યાદી હતી. આ શા માટે થાય છે મર્જ યાદી 2 યાદી માત્ર વૈકલ્પિક તત્વો શકતો નથી. 50 અને 23, 23 સરખામણી નાની હોય છે, તેથી અમે તે પસંદ કરો. 50 અને 42 ની વચ્ચે, 42 ઓછી છે. 50 અને 108 ની વચ્ચે, 50 ઓછી છે. અને, અંતે અમે માત્ર 108 છે, જેથી તે અમારી યાદી ઓવરને પર જવું આવશ્યક છે. નોંધ કરો કે અમે સરસ, સોર્ટ યાદી હોય છે. દર વખતે આપણે 2 યાદીઓ પ્રથમ 2 તત્વો સરખામણીમાં અમે મર્જ યાદી આગળના તત્વ નક્કી કરવા સમર્થ હતા. આનો અર્થ એ થાય કે જો અંતિમ યાદી n નંબરો, જ્યાં n અહીં 8 ધરાવે છે, તો પછી અમે સૌથી n સરખામણીઓ અંતે જરૂર યોગ્ય સ્થાન માં તે નંબરો તમામ મેળવો. આવી અલ્ગોરિધમનો લિનીઅર સમય ચાલે કહેવાય છે, પરંતુ તે વિશે અહીં ચિંતા કરશો નહિ. 

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

અને હવે અમે દરેક યાદી એક કપ સાથે 8 યાદીઓ છે. જેથી તે પગલું 1 માટે છે. પગલું 2 માટે, અમે વારંવાર મર્જ અલ્ગોરિધમનો અમે પહેલાં શીખ્યા મદદથી યાદીઓ જોડીઓ મર્જ. 108 અને 15 મર્જ, અમે 15 યાદી, 108 સાથે અંત. 50 અને 4 મર્જ, અમે 50 4, સાથે અંત. 8 અને 42 મર્જ, અમે 8 સાથે અંત, 42. અને 23 અને 16 મર્જ, અમે 16 સાથે અંત, 23. હવે અમારી બધી યાદીઓમાં 2 કદના હોય છે. નોંધ કરો કે આ યાદીઓ 4 દરેક સૉર્ટ થાય છે. 

તેથી અમે યાદીઓ જોડીઓ ફરીથી મર્જ શરૂ કરી શકો છો. 15 અને 108 અને 4 અને 50 મર્જ - પ્રથમ 4 લાગી, પછી 15 ના, તો પછી 50, 108 કે પછી. 8, 42 અને 16, 23 મર્જ, અમે પ્રથમ 8 ના, તો પછી 16 ના, તો પછી 23 ના, તો પછી 42 ના લો. તેથી હવે અમે 4 કદ 2 માત્ર યાદીઓ હોય છે, જે પ્રત્યેક સૉર્ટ થાય છે. તેથી હવે અમે આ 2 યાદીઓ મર્જ. પ્રથમ અમે 4 લો. તો પછી અમે 8 ના લો. તો પછી અમે 15 અને 16, 23 પછી, પછી 42, પછી 50, પછી 108 લે છે. અને અમે પૂર્ણ કરી લીધું. હવે અમે એક છટણી યાદી હોય છે. જેથી ઝડપી આ કેવી રીતે બરાબર હતું? તકનિકી દ્રષ્ટિએ, મર્જ સૉર્ટ ઓ (n લોગ એન) છે, જ્યારે બબલ સૉર્ટ કરો, નિવેશ સૉર્ટ કરો, અને પસંદગી પ્રકારના તમામ ગુમાવનારા છે (n ²) હતું. હકીકત માં, તમે જલદી જાણવા મળશે, તો તમે એક પ્રકારના આંબવું કરી શકશે નહીં કે સામાન્ય કિસ્સામાં ઓ (n લોગ એન) કરતા વધુ સારી રીતે કરે છે. ફરીથી, આ મોટી ઓ નોટેશનમાં વિશે ચિંતા જો તમે તેને હજુ સુધી જોઇ ન હોય નથી. 

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

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

મારું નામ રોબ બોડેન છે, અને આ CS50 છે. [CS50.TV] - અને સૉર્ટ પસંદગી. [Laughs] ઓહ, કે બહાર લઇ જવા માટે પણ કારણ કે હું સ્વિચ હું કેવી રીતે તે પ્રસ્તુત કરવામાં આવી હતી મળ્યો હતો. ડાબી બાજુ પર યાદી. કે લખતી વખતની ભૂલો હતી. [Misspoke] હું ઘણું ખરાબ - [Laughs] મને ખબર નથી કે શું -