[Powered by Google Translate] ટોમી: ચાલો પસંદગી સૉર્ટ પર એક નજર અલ્ગોરિધમ લેવા
સંખ્યાની યાદી લઈને તેમને સોર્ટિંગ કરવા માટે.
એક એલ્ગોરિધમ, યાદ રાખો કે, માત્ર એક પગલું દ્વારા પગલું છે
એક કાર્ય પૂર્ણ કરવા માટે પ્રક્રિયા.
પસંદગી સૉર્ટ પાછળનો મૂળ ખ્યાલ વિભાજિત છે
બે વિભાગોમાં અમારા સૂચિ -
એક છટણી ભાગ અને એક ક્રમમાંગોઠવાયેલનથી ભાગ.
અલગોરિધમ દરેક પગલે, એક નંબર પરથી ખસેડવામાં આવે
છેવટે સુધી છટણી ભાગ માટે ક્રમમાંગોઠવાયેલનથી ભાગ
સમગ્ર યાદી સૉર્ટ થાય છે.
તેથી અહીં છ નંબરોની યાદી છે -
23, 42, 4, 16, 8, અને 15.
હમણાં સમગ્ર યાદીમાં ક્રમમાંગોઠવાયેલનથી માનવામાં આવે છે.
તેમ છતાં 16 જેવા નંબર પહેલેથી જ તેની યોગ્ય હોઈ શકે છે
સ્થાન, અમારા અલગોરિધમ સુધી કે જાણીને કોઈ રીત છે
સમગ્ર યાદી સૉર્ટ થાય છે.
તેથી અમે દરેક નંબર માને છે ક્રમમાંગોઠવાયેલનથી કરી ત્યાં સુધી અમે સૉર્ટ પડશે
તે જાતને.
અમે જાણીએ છીએ કે અમે યાદી ચડતા ક્રમમાં કરવા માંગો છો.
તેથી અમે અમારી યાદીમાં છટણી ભાગ બિલ્ડ કરવા માંગો છો પડશે
ડાબેથી જમણી તરફ, સૌથી મોટી નાનું.
કે કરવા માટે, અમે લઘુત્તમ ક્રમમાંગોઠવાયેલનથી તત્વ શોધવા જરૂર પડશે
અને તે છટણી ભાગ ઓવરને અંતે મૂકો.
આ યાદીમાં નથી છટણી કરવામાં આવે છે, જે માત્ર કે રસ્તો એ છે
આ ક્રમમાંગોઠવાયેલનથી ભાગ દરેક તત્વ પર જુઓ, યાદ
જે તત્વ સૌથી નીચો અને સરખામણી છે
કે દરેક તત્વ.
તેથી અમે પ્રથમ 23 એ જોવા મળશે.
આ પ્રથમ તત્વ અમે જોયેલા છે, તેથી અમે યાદ પડશે
તે ઓછામાં ઓછા છે.
આગામી અમે 42 જોવા મળશે.
42 23 કરતા મોટા છે, તેથી 23 હજુ પણ ઓછામાં ઓછા છે.
આગળ 4 જે 23 કરતાં ઓછી હોય છે, તેથી અમે 4 યાદ પડશે
નવા ન્યુનતમ.
આગામી 16 જે 4 કરતાં મોટી છે, જેથી 4
હજુ પણ ઓછામાં ઓછા છે.
8 4 કરતાં મોટી છે, અને 15 4 કરતાં પણ મોટો છે, જેથી 4 હોવા જ જોઈએ
નાના ક્રમમાંગોઠવાયેલનથી તત્વ.
તેથી ભલે મનુષ્યો અમે તરત જ જુઓ કે 4 શકે છે
લઘુત્તમ તત્વ, અમારા અલગોરિધમ માટે જોવા જરૂર
દરેક ક્રમમાંગોઠવાયેલનથી તત્વ, પણ પછી અમે 4 એ શોધ્યું છે - તે
ન્યૂનતમ તત્વ.
તેથી હવે અમે લઘુત્તમ તત્વ, 4 મળ્યાં છે, અમે માંગો છો પડશે
તેને યાદીમાં છટણી ભાગ ખસેડો.
જ્યારથી આ પ્રથમ પગલું છે, એનો અર્થ અમે અંતે 4 મૂકેલ
યાદી શરૂઆત.
23 હમણાં યાદી શરૂઆતમાં આવું છે,
ચાલો આ 4 અને 23 ના સ્વેપ.
તેથી હવે અમારી યાદી આ જેવો દેખાય છે.
અમે જાણીએ છીએ કે 4 તેના અંતિમ સ્થાન હોવું જ જોઈએ, કારણ કે તે છે
બન્ને નાના અને શરૂઆતમાં તત્વ તત્વ
આ યાદીમાં છે.
આ અર્થ કે જેથી અમે ક્યારેય તેને ફરીથી ખસેડવા જરૂર નથી.
તેથી આપણે આ પ્રક્રિયા પુનરાવર્તન કરવા માટે અન્ય તત્વ ઉમેરો
યાદીમાં છટણી ભાગ.
અમે જાણીએ છીએ કે અમે 4 એ જોવા જરૂર નથી, કારણ કે તે
પહેલેથી સોર્ટ થાય છે.
તેથી અમે 42 એ શરૂ થાય છે, જેને આપણે તરીકે યાદ શકો છો
ન્યૂનતમ તત્વ.
અમે આગામી તેથી અમે 23 કે જેને 42 કરતાં ઓછી હોય જોવા કરીશું, જેથી
યાદ 23 નવા લઘુત્તમ છે.
આગામી અમે 16 જે 23 કરતાં ઓછી છે, જેથી જુઓ,
16 નવા લઘુત્તમ છે.
હવે અમે 8 જેમાં 16 કરતા પણ ઓછી છે, જેથી જુઓ,
8 નવા લઘુત્તમ છે.
અને 8 આખરે 15 કરતાં ઓછી છે, તેથી આપણે જાણીએ છીએ કે 8 ઓછામાં ઓછા છે
ક્રમમાંગોઠવાયેલનથી તત્વ.
તેથી તેનો અર્થ એ કે અમે 8 ના છટણી માટે ઉમેરી જોઈએ
યાદીમાં ભાગ.
હમણાં જ એક માત્ર 4 છટણી તત્વ છે, તેથી અમે મૂકવા માંગો છો
આ 8 એ માટે 4 આગામી.
42 હોવાના ના ક્રમમાંગોઠવાયેલનથી ભાગ પ્રથમ તત્વ છે
યાદી, અમે 42 અને 8 ના સ્વેપ કરવા માંગો છો પડશે.
તેથી હવે અમારી યાદી આ જેવો દેખાય છે.
4 અને 8 યાદીમાં છટણી ભાગ પ્રતિનિધિત્વ કરે છે, અને
બાકી નંબરો ક્રમમાંગોઠવાયેલનથી પ્રતિનિધિત્વ
યાદીમાં ભાગ.
તેથી આપણે અન્ય પુનરાવૃત્તિ સાથે ચાલુ રાખો.
અમે 23 સાથે આ સમય શરૂ કરવા માટે, કારણ કે અમે જોવા જરૂર નથી
4 અને હવે 8 કારણ કે તેઓ કરેલા
પહેલેથી જ છટણી કરવામાં આવી છે.
16 23 કરતા પણ ઓછી છે, તેથી અમે યાદ પડશે
16 નવા ન્યુનતમ.
16 42 કરતા પણ ઓછી છે, પરંતુ 15 16 કરતા પણ ઓછી છે, તેથી 15 જ હોવી જોઈએ
લઘુત્તમ ક્રમમાંગોઠવાયેલનથી તત્વ.
તેથી હવે અમે 15 અને 23 ને સ્વેપ કરવા માંગો છો
અમને આ યાદી આપે છે.
યાદીમાં છટણી ભાગ 8 4, અને 15 નો સમાવેશ થાય છે, અને
આ તત્વો હજુ પણ ક્રમમાંગોઠવાયેલનથી છે.
પરંતુ તે જ બને છે કે આગામી ક્રમમાંગોઠવાયેલનથી તત્વ, 16,
પહેલાંથી જ સોર્ટ થાય છે.
જો કે, ત્યાં અમારા અલગોરિધમ માટે કોઈ રીત છે તે જાણવા માટે કે 16
તેના યોગ્ય સ્થાન પહેલેથી જ છે, તેથી અમે હજુ પણ જરૂર
બરાબર એ જ પ્રક્રિયા પુનરાવર્તન કરો.
તેથી અમે જુઓ કે 16 42 કરતાં ઓછી છે, અને 16 23 કરતાં ઓછી છે, જેથી
16 લઘુત્તમ તત્વ હોવા જ જોઈએ.
તે અશક્ય છે કે પોતે આ તત્વ સ્વેપ તેથી, અમે આ કરી શકો છો
ફક્ત તે આ સ્થાન છોડી દો.
જેથી અમે અમારા અલગોરિધમ એક વધુ પાસ કરવાની જરૂર છે.
42 23 કરતા વધારે છે, તેથી 23 એ જ હોવી જોઈએ
ન્યૂનતમ ક્રમમાંગોઠવાયેલનથી તત્વ.
એકવાર અમે 23 અને 42 ના સ્વેપ, અમે અમારી અંતિમ સાથે અંત
છટણી યાદી -
4, 8, 15, 16, 23, 42.
અમે જાણીએ 42 યોગ્ય સ્થાને હોઈ કારણ કે તે હોવું જ જોઈએ
માત્ર તત્વ બાકી છે, અને તે પસંદગી સૉર્ટ છે.
ચાલો હવે કેટલાક અમારા અલગોરિધમ નિશ્ચિત સ્વરૂપ આપવું
સ્યુડોકોડનો.
એક લીટી પર, અમે જોઈ શકો છો કે અમે ઉપર સંકલિત કરવાની જરૂર
યાદી દરેક તત્વ.
છેલ્લા તત્વ સિવાય, ત્યારથી 1 તત્વ
યાદી પહેલેથી સૉર્ટ થાય છે.
બે લીટી પર, અમે ક્રમમાંગોઠવાયેલનથી પ્રથમ તત્વ ધ્યાનમાં
યાદીમાં ભાગ લઘુત્તમ છે, કારણ કે અમે અમારા સાથે કર્યું
ઉદાહરણ તરીકે, તેથી અમે સાથે સરખામણી કંઈક હોય છે.
ત્રણ લીટી બીજા લૂપ છીએ, જેમાં આપણે ઉપર ફરી વળવું શરૂ થાય છે
દરેક ક્રમમાંગોઠવાયેલનથી તત્વ.
અમે જાણીએ છીએ કે હું iterations પછી, સોર્ટ ભાગ
અમારા યાદી દરેક પગલું થી હું તેને તત્વો હોવી જ જોઈએ
એક તત્વ ગોઠવે છે.
જેથી પ્રથમ ક્રમમાંગોઠવાયેલનથી તત્વ હું વત્તા 1 સ્થિતિમાં જ હોવી જોઈએ.
ચાર લીટી પર, અમે લઘુત્તમ કરવા માટે વર્તમાન તત્વ તુલના
તત્વ કે અમે અત્યાર સુધી જોઇ છે.
જો વર્તમાન તત્વ લઘુત્તમ કરતા ઓછી છે
તત્વ, તો પછી અમે નવા તરીકે વર્તમાન તત્વ યાદ
પાંચ લાઇન પર ન્યૂનતમ.
છેલ્લે, છ અને સાત રેખાઓ પર, અમે ન્યૂનતમ સ્વેપ
પ્રથમ ક્રમમાંગોઠવાયેલનથી તત્વ સાથે ત્યાં તત્વ,
તે યાદીમાં છટણી ભાગ ઉમેરી રહ્યા હોય.
એકવાર અમે અલ્ગોરિધમ છે, એક મહત્વપૂર્ણ પ્રશ્ન પૂછી
જાતને પ્રોગ્રામરો સુધી કેવી રીતે છે લીઘા હતા?
અમે પ્રથમ પ્રશ્ન પૂછવા પડશે લાંબા તે કેવી રીતે આ માટે લે
અલ્ગોરિધમનો ખરાબ કેસ ચલાવવા માટે?
રિકોલ અમે આ દોડ પ્રતિનિધિત્વ
મોટું ઓ નોટેશનમાં સાથે સમય.
ક્રમમાં લઘુત્તમ ક્રમમાંગોઠવાયેલનથી તત્વ નક્કી કરવા માટે અમે,
અનિવાર્યપણે કરવા માટે યાદી દરેક તત્વ સરખાવવા હતી
યાદીમાં દરેક અન્ય તત્વ.
તર્ક, એન સ્ક્વેર્ડ કામગીરીના એક ઓ જેવી આ ધ્વનિઓ.
અમારા સ્યુડોકોડનો અંતે છીએ, અમે પણ અંદર નેસ્ટ લૂપ છે
અન્ય, એક ઓ જેવા લૂપ જે ખરેખર લાગે
n સ્ક્વેર્ડ ઓપરેશન.
જોકે યાદ રાખો કે અમે જોશે જરૂર ન હતી
સમગ્ર યાદી જ્યારે લઘુત્તમ ક્રમમાંગોઠવાયેલનથી તત્વ નક્કી?
એકવાર અમે જાણતા હતા કે 4 છટણી કરવામાં આવી હતી, ઉદાહરણ તરીકે કર્યું છે, તો અમે નથી
તેને ફરીથી જોવાની જરૂર નથી.
તેથી આ ચાલી રહેલ સમય નથી નીચલા?
6 લંબાઈ અમારી યાદી માટે, અમે પાંચ બનાવવા જરૂરી
પ્રથમ તત્વ માટે સરખામણીઓ માટે ચાર સરખામણીઓ
બીજા તત્વ, અને તેથી પર.
એટલે કે પગલાંઓ કુલ સંખ્યા સરવાળો છે
1 થી 1 બાદ યાદી લંબાઈ માટે પૂર્ણાંકો.
અમે એક શ્રેઢી સાથે આ પ્રતિનિધિત્વ કરી શકે છે.
અમે summations માં અહીં જશે.
પરંતુ તે તારણ છે કે જે આ શ્રેઢી n વખત સમાન છે
n બાદ 1 2 બનાવ્યા.
અથવા સમકક્ષ, એન 2 પર ઓછા 2 પર n ચોરસ.
જ્યારે અનંત સ્પર્શી રનટાઈમ વિશે વાત, આ n સ્ક્વેર્ડ પદ
છે આ n એ શબ્દ પર પ્રભુત્વ હોય છે.
તેથી પસંદગી સૉર્ટ n સ્ક્વેર્ડ ઓફ ઓ છે.
જણાવ્યું હતું કે અમારા ઉદાહરણમાં, પસંદગી સૉર્ટ કરવા માટે હજુ પણ જરૂરી
તપાસો જો એ સંખ્યા છે કે પહેલેથી જ છટણી કરવામાં આવી હતી
ખસેડવામાં આવશે જરૂર છે.
જેથી અર્થ એ થાય કે જો અમે પહેલાથી જ પસંદગી સૉર્ટ ચાલી હતી
યાદી છટણી, તેને તરીકે પગલાંઓ જ નંબર જરૂરી છે
છો જ્યારે સંપૂર્ણપણે ક્રમમાંગોઠવાયેલનથી યાદી પર દોડે છે.
તેથી પસંદગી સૉર્ટ એક શ્રેષ્ઠ સ્ક્વેર્ડ n ના કેસ કામગીરી ધરાવે છે,
જે અમે ઓમેગા સ્ક્વેર્ડ n સાથે પ્રતિનિધિત્વ કરે છે.
અને તે પસંદગી સૉર્ટ માટે છે.
જસ્ટ ઘણા એલ્ગોરિધમ્સ અમે કરી શકો છો એક
એક યાદી સૉર્ટ વાપરો.
મારું નામ ટોમી છે, અને આ cs50 છે.