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

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

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

આમ કરવા માટે, અમે 23 માટે 42 તુલના કરવાની જરૂર પડશે - અમારા છટણી ભાગ માં માત્ર તત્વ અત્યાર સુધી. બેતાલીસ 23 કરતા વધારે હોય છે, તેથી અમે ફક્ત અંતે 42 ઉમેરી શકો છો યાદીમાં છટણી ભાગ છે. સરસ! હવે અમારા છટણી ભાગ બે ઘટકો હોય છે, અને અમારા ક્રમમાંગોઠવાયેલનથી ભાગ ચાર તત્વો ધરાવે છે. તેથી, ચાલો હવે 4 માટે ખસેડવા માટે, ક્રમમાંગોઠવાયેલનથી ભાગ આગામી તત્વ. તેથી, જ્યાં આ છટણી ભાગ મૂકવામાં આવવો જોઈએ? 

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

તેનો અર્થ એ કે અમે છટણી ભાગ પ્રથમ સ્લોટ માં 4 મૂકવા માંગો છો. નોંધ કેવી રીતે યાદી આ જગ્યા પહેલાથી જ ખાલી, કારણ કે અમે છટણી કરવામાં તત્વો ખસેડીને કરી છે ડાઉન તરીકે અમે તેમને આવી. અધિકાર છે. તેથી, અમે હાફવે ત્યાં છો. ચાલો આ છટણી ભાગ માં 16 ના દાખલ કરીને અમારી અલ્ગોરિધમનો ચાલુ રાખો. સોળ ઓછા 42 કરતાં, તેથી આપણે જમણી 42 પાળી. સોળ પણ ઓછા 23 કરતાં, તેથી આપણે પણ તે તત્વ પાળી. 

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

અધિકાર છે. હવે, અમે ચાર છટણી તત્વો અને બે ક્રમમાંગોઠવાયેલનથી તત્વો હોય છે. તેથી, ચાલો આ છટણી ભાગ માં 8 ના ખસેડો. આઠ 42 કરતાં ઓછી છે. આઠ 23 કરતાં ઓછી છે. અને 8 16 કરતાં ઓછી છે. પરંતુ 8 4 કરતા વધારે છે. તેથી, અમે 4 અને 16 વચ્ચે 8 ના સામેલ કરવા માંગો છો. 15 ના - અને હવે અમે માત્ર એક વધુ બાકી તત્વ સૉર્ટ કરવા માટે હોય છે. પંદર 42 કરતાં ઓછી છે, પંદર 23 કરતાં ઓછી છે. અને 15 16 કરતા પણ ઓછી છે. પરંતુ 15 8 કરતા વધારે છે. 

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

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

4 વાક્ય પર, અમે છટણી જમણેથી ડાબી ભાગ વારો કરી રહ્યાં છો. અમે તત્વ એકવાર અમારી વર્તમાન સ્થિતિ ડાબી વારો રોકવા માંગો છો તત્વ અમે દાખલ પ્રયાસ કરી રહ્યા છો તેના કરતાં ઓછી છે. 5 રેખા પર, અમે દરેક તત્વ અમે જમણી એક જગ્યા મળે સ્થળાંતર કરી રહ્યા છો. તે રીતે, અમે સ્પષ્ટ દાખલ જગ્યા છે જ્યારે અમે પ્રથમ તત્વ મળશે તત્વ અમે ખસેડીએ છીએ કરતાં ઓછો હોય છે. 6 વાક્ય પર, અમે અમારી કાઉન્ટર અપડેટ કરી રહ્યા છો તે માટે છટણી ભાગ દ્વારા છોડી ખસેડવા ચાલુ રાખો. છેલ્લે, 7 વાક્ય પર, અમે યાદીમાં છટણી ભાગ માં તત્વ દાખલ કરી રહ્યા છો. 

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

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

અમે summations માં અહીં ન જાય, પરંતુ તે તારણ છે કે જે આ શ્રેઢી સમાન છે 2 ઉપર છે, જે સમકક્ષ ^ 2/2 n છે - (1 એન) - એન / 2 એન. જ્યારે અનંત સ્પર્શી રનટાઈમ વિશે વાત, આ n ^ 2 પદ માટે આ n એ શબ્દ પર પ્રભુત્વ રહ્યું છે. તેથી, નિવેશ સૉર્ટ મોટા ઓ (n ^ 2) છે. જો અમે પહેલાથી જ છટણી યાદી પર દાખલ સૉર્ટ ચાલી હતી. તે કિસ્સામાં, અમે ફક્ત અપ છટણી ડાબેથી જમણે ભાગ બિલ્ડ છો. તેથી, અમે માત્ર n પગલાંઓ ઓર્ડર કરવાની જરૂર પડશે. 

એટલે કે નિવેશ સૉર્ટ n ના પ્રભાવ સૌથી કેસ છે, જે અમે Ω (એન) સાથે પ્રતિનિધિત્વ કરે છે. અને તે નિવેશ સૉર્ટ માટે છે, માત્ર એક જ અનેક અલગોરિથમ્સ અમે યાદી સૉર્ટ વાપરી શકો છો. મારું નામ ટોમી છે, અને આ CS50 છે. [CS50.TV] ઓહ, તમે હમણાં બંધ ન કરી શકો છો કે એકવાર તે શરૂ થાય છે. ઓહ, અમે તે હતી - >> બૂમ!