[Powered by Google Translate] [બબલ સોર્ટ] [JACKSON STEINKAMP હાર્વર્ડ યુનિવર્સિટી] [આ CS50 છે. CS50TV] બબલ સૉર્ટ કરો એક સૉર્ટ અલ્ગોરિધમનો એક ઉદાહરણ છે - એટલે કે, તત્વોના સમૂહના માં સૉર્ટ કરવા માટે કાર્યવાહી ચડતા અથવા ઉતરતા ક્રમમાં. હમણાં પૂરતું, જો તમે એક એરે સૉર્ટ માગતો હતો, નંબરો સમાવેશ થાય છે [3, 5, 2, 9], બબલ સૉર્ટ કરો એક યોગ્ય અમલીકરણ એ પાછો આવશે છટણી [2, 3, 5, 9] એરે ચડતા ક્રમમાં. હવે, હું સ્યુડોકોડનો માં કેવી રીતે કામ કરે છે અલગોરિધમ જાઉં છું. 

હવે કહો કે અમે 5 પૂર્ણાંકો યાદી સૉર્ટ કરી રહ્યા છીએ - 3, 2, 9, 6, અને 5. અલગોરિધમ પ્રથમ બે ઘટકો, 3 અને 2 ખાતે જોવાનું શરૂ કરે છે, અને ચકાસણી જો તેઓ એકબીજા સાથે સંબંધિત હુકમ નથી. તેઓ આ પ્રમાણે છે - 3 2 કરતા વધારે હોય છે. માટે ચઢતો ક્રમ હોય છે, તેઓ અન્ય આસપાસ રસ્તો પ્રયત્ન કરીશું. તેથી, અમે તેમને સ્વેપ. [2, 3, 9, 6, 5]: હવે સૂચિ આ જેવો દેખાય છે. 

પછી, આપણે બીજા અને ત્રીજા તત્વો, 3 અને 9 જુઓ. તેઓ યોગ્ય દરેક અન્ય સંબંધિત ક્રમમાં છો. એટલે કે, 3 છે 9 કરતાં ઓછી જેથી અલ્ગોરિધમનો તેમને સ્વેપ નથી. પછી, આપણે 9 અને 6 જુઓ. તેઓ હુકમ નથી. 

તેથી, અમે તેમને સ્વેપ કારણ કે 9 6 કરતા વધારે હોય છે જરૂર છે. છેલ્લે, અમે છેલ્લા બે પૂર્ણાંકો, 9 અને 5 જુઓ. તેઓ હુકમ બહાર છો, જેથી તેઓ એકબીજાને નંબર હોવો જ જોઈએ. આ યાદી મારફતે પ્રથમ સંપૂર્ણ પાસ કર્યા પછી, [2, 3, 6, 5, 9]: આ જેવો દેખાય છે. જવાબ નથી ખરાબ. તે લગભગ છટણી છે. પરંતુ અમે યાદી મારફતે ફરી ચલાવવા માટે વિચાર તેને સંપૂર્ણપણે છટણી કરવાની જરૂર છે. બે 3 કરતાં ઓછી હોય છે, તેથી અમે તેમને સ્વેપ નથી. 

ત્રણ 6 કરતા ઓછી હોય છે, તેથી અમે તેમને સ્વેપ નથી. છ 5 કરતા વધારે છે. અમે એકબીજાને નંબર. છ 9 કરતાં ઓછી છે. અમે નથી સ્વેપ નથી. બીજા દ્વારા પાસ કર્યા પછી, તે આના જેવું દેખાય છે: [2, 3, 5, 6, 9]. પરફેક્ટ. હવે, તેના સ્યુડોકોડનો લખી. મૂળભૂત રીતે, યાદીમાં દરેક તત્વ માટે, અમે તેના પર જોવાની જરૂર અને સીધા તેની જમણી તત્વ. જો તેઓ હુકમ બહાર છે દરેક અન્ય સંબંધિત - એટલે કે, જો ડાબી પર તત્વ જમણે પર એક કરતાં વધારે હોય છે - અમે બે તત્વો સ્વેપ કરીશું. 

અમે યાદી દરેક તત્વ માટે આવું કરવા માટે, અને અમે મારફતે એક પાસ કર્યા છે. હવે અમે માત્ર પાસ થ્રુ પર્યાપ્ત સમય કરવા માટે યાદી છે તેની ખાતરી હોય છે છે સંપૂર્ણપણે, યોગ્ય રીતે સોર્ટ થાય છે. પરંતુ કેટલી વખત અમે યાદીમાં પસાર હોય બાંયધરી કે અમે પૂર્ણ કરી? વેલ, દૃશ્ય ખરાબ કેસ છે, જો અમે સંપૂર્ણપણે પાછળની યાદી હોય છે. પછી તેને પસાર-throughs સંખ્યાબંધ નંબર સમાન લે છે n-1 તત્વો. જો આ અર્થમાં તર્ક નથી, એક સરળ કેસ લાગે છે - આ યાદીમાં [2, 1]. 

આ એક પાસ થ્રુ લેવા માટે યોગ્ય સૉર્ટ રહ્યું છે. [3, 2, 1] - આ સૌથી ખરાબ કેસ એ છે કે 3 તત્વો સાથે પાછળની સૉર્ટ કરેલ તે પ્રકારની માટે 2 iterations લાગી રહ્યું છે. એક પુનરાવર્તન કર્યા પછી, તે [2, 1, 3] છે. બીજા ઉત્પાદનની છટણી એરે [1, 2, 3]. તેથી તમે જાણો છો કે તમે સામાન્ય ક્યારેય હોય, એરે મારફતે જાઓ, n-1 વખત, કે જ્યાં n એરે માં સંખ્યાબંધ તત્વો છે તે કરતાં વધુ. તે બબલ સૉર્ટ કરો કહેવાય છે કારણ કે સૌથી મોટી તત્વો 'બબલ અપ' વલણ ધરાવે છે આ ખૂબ ઝડપથી અધિકાર છે. હકીકતમાં, આ અલ્ગોરિધમનો ખૂબ રસપ્રદ વર્તન ધરાવે છે. 

સમગ્ર એરે મારફતે મીટર iterations પછી, જમણીબાજુનીસ્થિતિ મીટર તત્વો ખાતરી આપી છે તેમની સાચી જગ્યાએ સૉર્ટ શકાય છે. જો તમે તમારા પોતાના માટે આ જોવા માંગો છો, અમે તેને સંપૂર્ણપણે પાછળની [9, 6, 5, 3, 2] યાદી પર પ્રયાસ કરી શકો છો. સમગ્ર યાદી મારફતે એક પાસ કર્યા પછી, [લેખન અવાજ] [6, 9, 5, 2, 3], [6, 5, 9, 2, 3], [6, 5, 3, 9 2,], [6, 5, 3, 2, 9] જમણીબાજુનીસ્થિતિ 9 તત્વ તેના યોગ્ય સ્થાને છે. આ પાસ થ્રુ બીજા પછી, 6 એ 'bubbled અપ' માટે હશે બીજા જમણીબાજુનીસ્થિતિ સ્થળ. 6 અને 9 - - જમણે બે તત્વો તેમના યોગ્ય સ્થળોએ થશે પ્રથમ બે પાસ-throughs પછી. 

તેથી, અમે કેવી રીતે ઉપયોગ કરવા માટે અલગોરિધમ ઑપ્ટિમાઇઝ કરી શકું? વેલ, એરે મારફતે એક પુનરાવર્તન પછી અમે ખરેખર જમણીબાજુનીસ્થિતિ તત્વ તપાસ કરવાની જરૂર નથી કારણ કે અમે જાણીએ છીએ કે તે છટણી છે. બે iterations પછી, અમે ખાતરી જમણીબાજુનીસ્થિતિ બે ઘટકો તેની જગ્યાએ છે જાણી. તેથી, સામાન્ય રીતે, પૂર્ણ એરે મારફતે k iterations પછી, છેલ્લા k તત્વો ચકાસણી રીડન્ડન્ટ છે કારણ આપણે જાણીએ છીએ તેઓ યોગ્ય સ્થાન પહેલાથી જ છો. 

તેથી જો તમે n તત્વોના ઝાકઝમાળ સૉર્ટ કરી રહ્યા છો, પ્રથમ પુનરાવૃત્તિ પર - you'll માટે બધા તત્વો સૉર્ટ હોય - પ્રથમ-n 0. બીજા પુનરાવૃત્તિ પર, તમે આ બધા તત્વો પરંતુ છેલ્લા જોવા મળશે - આ n-1 પ્રથમ. અન્ય ઓપ્ટિમાઇઝેશન માટે ચકાસો જો યાદી પહેલેથી સૉર્ટ થાય છે હોઈ શકે છે દરેક ઇટરેશન પછી. જો તે પહેલાથી જ છટણી છે, અમે કોઇપણ વધુ iterations બનાવવા જરૂર નથી આ યાદી મારફતે. અમે આ કેવી રીતે કરી શકો છો? વેલ, જો અમે કોઈ અદલબદલ એક યાદી પાસ થ્રુ પર બનાવતા નથી, તે સ્પષ્ટ છે કે યાદી પહેલાથી જ કારણ કે અમે કોઇ સ્વેપ નહોતી છટણી કરવામાં આવી હતી. જેથી અમે ચોક્કસપણે ફરીથી સૉર્ટ નથી. 

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

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

બબલ સૉર્ટ છે કોઇ અત્યંત કાર્યક્ષમ અથવા ઝડપી સોર્ટિંગ અલ્ગોરિધમનો થાય છે. તેના રનટાઈમ સૌથી ખરાબ કેસ n ના મોટા ઓ છે ચોરસ કારણ કે તમે યાદી મારફતે n iterations બનાવવા હોય તમામ n તત્વોના ચકાસણી દરેક પાસ થ્રુ, nxn = n ધરાવે છે. આ સ્કોર સમય અર્થ એ છે કે સંખ્યાબંધ તત્વો તરીકે તમે વધારો સૉર્ટ કરી રહ્યા છો, આ સમય રન quadratically વધારે છે. 

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