Flashsort
ફ્લેશસોર્ટ એ એક વિતરણ સૉર્ટિંગ અલ્ગોરિધમ છે જે સમાન રીતે વિતરિત ડેટા સમૂહો અને પ્રમાણમાં ઓછી વધારાની મેમરી જરૂરિયાત માટે રેખીય કોમ્પ્યુટેશનલ જટિલતા દર્શાવે છે. મૂળ કૃતિ 1998માં કાર્લ-ડીટ્રીચ ન્યુબર્ટ દ્વારા પ્રકાશિત કરવામાં આવી હતી. કોન્સેપ્ટ ફ્લેશસોર્ટ એ હિસ્ટોગ્રામ સૉર્ટનું સ્થળ પર કાર્યક્ષમ અમલીકરણ છે, જે પોતે એક પ્રકારનો બકેટ સૉર્ટ છે. તે દરેક ઇનપુટ તત્વોને એક ડોલમાં સોંપે છે, ડોલને યોગ્ય ક્રમમાં મૂકવા માટે ઇનપુટને અસરકારક રીતે ફરીથી ગોઠવે છે, પછી દરેક ડોલને સૉર્ટ કરે છે. મૂળ અલ્ગોરિધમ ઇનપુટ એરેને નીચે પ્રમાણે સૉર્ટ કરે છેઃ ઇનપુટ અથવા પ્રાથમિક જ્ઞાન પર પ્રથમ પાસનો ઉપયોગ કરીને, ન્યૂનતમ અને મહત્તમ સૉર્ટ કીઓ શોધો. રેખીય રીતે શ્રેણીને ડોલમાં વિભાજીત કરો. દરેક ડોલમાં આવતા તત્વોની સંખ્યાની ગણતરી કરીને ઇનપુટ પર એક પાસ બનાવો. (ન્યુબર્ટ બાલ્ટીઓને "વર્ગો" અને તેમની બાલ્ટીમાં તત્વોની સોંપણીને "વર્ગીકરણ" કહે છે.) દરેક ડોલમાં તત્વોની ગણતરીને ઉપસર્ગ રકમમાં રૂપાંતરિત કરો, જ્યાં ડોલમાં તત્વોની સંખ્યા અથવા તેનાથી ઓછી છે. (અને.) ઇનપુટને ફરીથી ગોઠવો જેથી દરેક ડોલના તમામ ઘટકો જ્યાં સંગ્રહિત થાય ત્યાં સંગ્રહિત થાય. દરેક ડોલને નિવેશ સૉર્ટનો ઉપયોગ કરીને સૉર્ટ કરો. પગલાં 1-3 અને 6 કોઈપણ બકેટ સૉર્ટ માટે સામાન્ય છે, અને બકેટ સૉર્ટ માટે સામાન્ય તકનીકોનો ઉપયોગ કરીને સુધારી શકાય છે. ખાસ કરીને, ધ્યેય એ છે કે ડોલ લગભગ સમાન કદ (દરેક ઘટકો) ની હોવી જોઈએ, જેમાં આદર્શ પરિમાણોમાં વહેંચાયેલું હોવું જોઈએ. જ્યારે મૂળભૂત અલ્ગોરિધમ એક રેખીય અંતર્વેશન સૉર્ટ છે, જો ઇનપુટ વિતરણ બિન-સમાન હોવાનું જાણીતું હોય, તો બિન-રેખીય વિભાજન આ આદર્શને વધુ નજીકથી અંદાજિત કરશે. તેવી જ રીતે, અંતિમ સૉર્ટ પુનરાવર્તિત ફ્લેશ સૉર્ટ સહિત સંખ્યાબંધ તકનીકોમાંથી કોઈપણનો ઉપયોગ કરી શકે છે. ફ્લેશ સૉર્ટને જે અલગ પાડે છે તે પગલું 5 છેઃ માત્ર વધારાના મેમરીના શબ્દોનો ઉપયોગ કરીને દરેક ડોલના તત્વોને સાચા સંબંધિત ક્રમમાં એકત્રિત કરવા માટે એક કાર્યક્ષમ ઇન-પ્લેસ અલ્ગોરિધમ. મેમરી કાર્યક્ષમ અમલીકરણ ફ્લેશસોર્ટ પુનઃગોઠવણી તબક્કો ચક્રમાં કાર્ય કરે છે. તત્વો "બિનવર્ગીકૃત" થી શરૂ થાય છે, પછી યોગ્ય ડોલમાં ખસેડવામાં આવે છે અને "વર્ગીકૃત" ગણવામાં આવે છે. મૂળભૂત પ્રક્રિયા એ છે કે બિનવર્ગીકૃત તત્વ પસંદ કરવું, તેની સાચી ડોલ શોધવી, તેને ત્યાં બિનવર્ગીકૃત તત્વ સાથે વિનિમય કરવો (જે અસ્તિત્વમાં હોવું જોઈએ, કારણ કે આપણે દરેક ડોલનું કદ સમય પહેલા ગણ્યા છે), તેને વર્ગીકૃત તરીકે ચિહ્નિત કરો, અને પછી માત્ર-વિનિમયિત બિનવર્ગીકૃત તત્વ સાથે પુનરાવર્તન કરો. આખરે, તત્વની પોતાની સાથે અદલાબદલી થાય છે અને ચક્ર સમાપ્ત થાય છે. બકેટ દીઠ બે (શબ્દ-કદના) ચલોનો ઉપયોગ કરીને વિગતો સમજવી સરળ છે. ચપળ ભાગ એ છે કે તે ચલોમાંથી એકને દૂર કરવામાં આવે છે, જે બમણી ડોલનો ઉપયોગ કરવાની મંજૂરી આપે છે અને તેથી અંતિમ સૉર્ટિંગ પર અડધો સમય વિતાવે છે. તેને બકેટ દીઠ બે ચલ સાથે સમજવા માટે, ધારો કે વધારાના શબ્દોની બે શ્રેણીઓ છેઃ બકેટ (અને) ની (નિશ્ચિત) ઉપલી મર્યાદા છે, જ્યારે બકેટમાં (જંગમ) અનુક્રમણિકા છે, તેથી. અમે લૂપ અપરિવર્તન જાળવીએ છીએ કે દરેક ડોલને વર્ગીકૃત ઉપસર્ગમાં વહેંચવામાં આવે છે (કારણ કે હજુ સુધી તેમના લક્ષ્ય ડોલમાં ખસેડવાનું બાકી છે) અને વર્ગીકૃત પ્રત્યય (કારણ કે તે બધા યોગ્ય ડોલમાં છે અને ફરીથી ખસેડવામાં આવશે નહીં). શરૂઆતમાં અને તમામ ઘટકો બિનવર્ગીકૃત છે. જેમ જેમ સૉર્ટિંગ આગળ વધે છે, તે બધા માટે ઘટાડવામાં આવે છે અને તમામ ઘટકોને યોગ્ય ડોલમાં વર્ગીકૃત કરવામાં આવે છે. દરેક રાઉન્ડની શરૂઆત પ્રથમ અપૂર્ણ વર્ગીકૃત ડોલ (જેની પાસે છે) શોધીને અને તે ડોલમાં પ્રથમ વર્ગીકૃત તત્વ લઈને થાય છે. (ન્યુબર્ટ આને "સાયકલ લીડર" કહે છે.) કામચલાઉ ચલમાં નકલ કરો અને પુનરાવર્તન કરો કેઃ જે ડોલ સાથે સંબંધિત છે તેની ગણતરી કરો. જ્યાં સંગ્રહિત કરવામાં આવશે તે સ્થાન હોવું જોઈએ. સાથે વિનિમય, એટલે કે. અગાઉની કિંમત મેળવતી વખતે સ્ટોર કરો જેથી વિસ્થાપિત થાય. જે હકીકત હવે યોગ્ય રીતે વર્ગીકૃત કરવામાં આવી છે તેને પ્રતિબિંબિત કરવા માટે ઘટાડો. જો, તો આ લૂપને નવા સાથે પુનઃપ્રારંભ કરો. જો, આ રાઉન્ડ સમાપ્ત થઈ ગયો હોય અને નવું પ્રથમ વર્ગીકૃત ન કરેલું તત્વ શોધો. જ્યારે વધુ બિનવર્ગીકૃત ઘટકો ન હોય, ત્યારે ડોલમાં વિતરણ પૂર્ણ થાય છે. જ્યારે આ રીતે ડોલ દીઠ બે ચલ સાથે અમલ કરવામાં આવે છે, ત્યારે દરેક રાઉન્ડના પ્રારંભિક બિંદુની પસંદગી હકીકતમાં મનસ્વી હોય છે; કોઈપણ વર્ગીકૃત તત્વનો ઉપયોગ ચક્ર નેતા તરીકે થઈ શકે છે. એકમાત્ર જરૂરિયાત એ છે કે સાયકલ લીડર્સને અસરકારક રીતે શોધી શકાય છે. જો કે અગાઉના વર્ણનનો ઉપયોગ ચક્રના નેતાઓને શોધવા માટે થાય છે, તેમ છતાં હકીકતમાં તેના વિના કરવું શક્ય છે, જેનાથી સંપૂર્ણ શબ્દ શ્રેણીને દૂર કરી શકાય છે. (વિતરણ પૂર્ણ થયા પછી, ડોલની સીમાઓ અહીં મળી શકે છે.) ધારો કે આપણે તમામ તત્વોને વર્ગીકૃત કર્યા છે, અને સંભવિત નવા ચક્ર નેતા તરીકે વિચારણા કરી રહ્યા છીએ. તેની લક્ષ્ય બકેટની ગણતરી કરવી સરળ છે. લૂપ અપરિવર્તન દ્વારા, તેને વર્ગીકૃત કરવામાં આવે છે જો, અને વર્ગીકૃત કરવામાં ન આવે તો તે શ્રેણીની બહાર છે. પ્રથમ અસમાનતા ચકાસવા માટે સરળ છે, પરંતુ બીજાને મૂલ્યની જરૂર હોય તેવું લાગે છે. તે તારણ આપે છે કે ઇન્ડક્શન પૂર્વધારણા કે જે તમામ ઘટકોને વર્ગીકૃત કરવામાં આવે છે તે સૂચવે છે કે, તેથી બીજી અસમાનતાને ચકાસવી જરૂરી નથી. ડોલ કઈ સ્થિતિમાં પડે છે તેનો વિચાર કરો. એટલે કે,. ઇન્ડક્શન પૂર્વધારણા દ્વારા, નીચે આપેલા તમામ ઘટકો, જેમાં તમામ ડોલનો સમાવેશ થાય છે, તે સંપૂર્ણપણે વર્ગીકૃત કરવામાં આવે છે. આઈ. ઇ. તે ડોલમાં રહેલા કોઈપણ ઘટકો બાકીના એરેમાં રહેતા નથી. તેથી, તે શક્ય નથી. એકમાત્ર બાકી રહેલો કેસ છે, જે સૂચવે છે, ક્યુ. ઇ. ડી. આનો સમાવેશ કરીને, ફ્લેશસોર્ટ વિતરણ અલ્ગોરિધમ ઉપર વર્ણવ્યા મુજબ અને સાથે શરૂ થાય છે. પછી આગળ વધોઃ જો, વિતરણ પૂર્ણ થઈ ગયું હોય. આપેલ છે, તે જે ડોલની છે તેની ગણતરી કરો. જો, તો પછી વર્ગીકૃત નથી. તેને કામચલાઉ ચલ તરીકે નકલ કરો અનેઃ ચાલો તે સ્થાન હોઈએ જ્યાં તેને સંગ્રહિત કરવામાં આવશે. સાથે વિનિમય, એટલે કે. અગાઉની કિંમત મેળવતી વખતે સ્ટોર કરો જેથી વિસ્થાપિત થાય. જે હકીકત હવે યોગ્ય રીતે વર્ગીકૃત કરવામાં આવી છે તેને પ્રતિબિંબિત કરવા માટે ઘટાડો. જો, જે ડોલની માલિકી ધરાવે છે તેની ગણતરી કરો અને આ (આંતરિક) લૂપને નવા સાથે પુનઃપ્રારંભ કરો. હવે યોગ્ય રીતે વર્ગીકૃત કરવામાં આવે છે. (બાહ્ય) લૂપને વધારો અને પુનઃપ્રારંભ કરો. મેમરી સાચવતી વખતે, ફ્લેશસોર્ટનો ગેરલાભ એ છે કે તે ઘણા પહેલાથી વર્ગીકૃત ઘટકો માટે બકેટની ફરીથી ગણતરી કરે છે. આ પહેલેથી જ તત્વ દીઠ બે વાર કરવામાં આવે છે (એક વખત ડોલ-ગણતરીના તબક્કા દરમિયાન અને બીજી વખત દરેક તત્વને ખસેડતી વખતે), પરંતુ પ્રથમ બિનવર્ગીકૃત તત્વની શોધ માટે મોટાભાગના ઘટકો માટે ત્રીજી ગણતરીની જરૂર પડે છે. જો સરળ રેખીય પ્રક્ષેપણ કરતાં વધુ જટિલ સૂત્રનો ઉપયોગ કરીને ડોલની સોંપણી કરવામાં આવે તો આ ખર્ચાળ બની શકે છે. એક પ્રકાર અપૂર્ણ ડોલમાં છેલ્લા બિનવર્ગીકૃત તત્વને ચક્ર નેતા તરીકે લઈને ગણતરીઓની સંખ્યાને લગભગ મહત્તમ ઘટાડે છેઃ પ્રથમ અપૂર્ણ-વર્ગીકૃત ડોલને ઓળખતા ચલની જાળવણી કરો. ચાલો શરૂ કરીએ, અને ક્યારે, વિતરણ પૂર્ણ થાય છે. જવા દો. જો, આ લૂપને વધારો અને પુનઃપ્રારંભ કરો. (.) જે ડોલની છે તેની ગણતરી કરો. જો, તો પછી અને આપણે બકેટ સાથે પૂર્ણ કરી લીધું છે. આ લૂપને વધારો અને પુનઃપ્રારંભ કરો. જો, વર્ગીકરણ તુચ્છ છે. આ લૂપને ઘટાડીને પુનઃપ્રારંભ કરો. જો, તો પછી વર્ગીકૃત નથી. અગાઉના કેસની જેમ જ વર્ગીકરણ લૂપ કરો, પછી આ લૂપને પુનઃપ્રારંભ કરો. મોટાભાગના ઘટકોની ડોલની ગણતરી માત્ર બે વાર કરવામાં આવે છે, સિવાય કે દરેક ડોલમાં અંતિમ તત્વ, જેનો ઉપયોગ નીચેની ડોલની પૂર્ણતાને શોધવા માટે થાય છે. બિનવર્ગીકૃત તત્વોની ગણતરી જાળવી રાખીને અને જ્યારે તે શૂન્ય સુધી પહોંચે ત્યારે તેને અટકાવીને થોડો વધુ ઘટાડો હાંસલ કરી શકાય છે. પ્રદર્શન માત્ર વધારાની મેમરી જરૂરિયાતો ડોલની સીમાઓ સંગ્રહિત કરવા માટે સહાયક વેક્ટર અને ઉપયોગમાં લેવાતા અન્ય ચલની સતત સંખ્યા છે. વધુમાં, દરેક તત્વને (કામચલાઉ બફર દ્વારા, તેથી બે ચાલ કામગીરી) માત્ર એક જ વાર ખસેડવામાં આવે છે. જો કે, આ મેમરી કાર્યક્ષમતા ગેરલાભ સાથે આવે છે કે એરેને અવ્યવસ્થિત રીતે એક્સેસ કરવામાં આવે છે, તેથી સમગ્ર એરે કરતા નાના ડેટા કેશનો લાભ લઈ શકાતો નથી. તમામ પ્રકારની ડોલની જેમ, કામગીરી પણ ટીકાત્મક રીતે ડોલના સંતુલન પર આધાર રાખે છે. સંતુલિત ડેટા સેટના આદર્શ કિસ્સામાં, દરેક ડોલ લગભગ સમાન કદની હશે. જો ઇનપુટ કદમાં ડોલની સંખ્યા રેખીય હોય, તો દરેક ડોલનું કદ સ્થિર હોય છે, તેથી નિવેશ સૉર્ટ જેવા અલ્ગોરિધમ સાથે એક જ ડોલને સૉર્ટ કરવામાં જટિલતા હોય છે. તેથી અંતિમ નિવેશ પ્રકારોનો ચાલી રહેલો સમય છે. ડોલની સંખ્યા માટે મૂલ્ય પસંદ કરવું, ઘટકો (ઉચ્ચ) નું વર્ગીકરણ કરવામાં વિતાવેલા સમય અને અંતિમ નિવેશ સૉર્ટ પગલું (નિમ્ન) માં વિતાવેલા સમયનો વેપાર કરે છે. ઉદાહરણ તરીકે, જો તેને પ્રમાણસર પસંદ કરવામાં આવે, તો અંતિમ નિવેશ પ્રકારનો ચાલી રહેલો સમય છે. સૌથી ખરાબ પરિસ્થિતિઓમાં જ્યાં લગભગ તમામ ઘટકો થોડા ડોલમાં હોય છે, ત્યાં અલ્ગોરિધમની જટિલતા અંતિમ ડોલ-વર્ગીકરણ પદ્ધતિની કામગીરી દ્વારા મર્યાદિત હોય છે, તેથી તેમાં ઘટાડો થાય છે. અલ્ગોરિધમનોના ફેરફારો ચોક્કસ કદની મર્યાદા કરતાં વધી ગયેલા ડોલ પર ક્વિકસોર્ટ અથવા રિકર્સિવ ફ્લેશસોર્ટ જેવા વધુ સારા પ્રદર્શન પ્રકારોનો ઉપયોગ કરીને સૌથી ખરાબ સ્થિતિમાં કામગીરીમાં સુધારો કરે છે. એકસમાન રીતે વિતરિત રેન્ડમ ડેટા સાથે, ફ્લેશસોર્ટ બધા માટે હીપસોર્ટ કરતાં ઝડપી છે અને બધા માટે ક્વિકસોર્ટ કરતાં ઝડપી છે. તે ઝડપી ગતિ કરતા લગભગ બમણી ઝડપી બને છે. નોંધ લો કે આ માપ 1990 ના દાયકાના અંતમાં લેવામાં આવ્યા હતા, જ્યારે મેમરી પદાનુક્રમ કેશ કરવા પર ઘણો ઓછો નિર્ભર હતો. ફ્લેશસોર્ટ તેની વર્ગીકરણ પ્રક્રિયામાં કરે છે તે ઇન સિટુ ક્રમચયને કારણે, ફ્લેશસોર્ટ સ્થિર નથી. જો સ્થિરતા જરૂરી હોય, તો બીજા એરેનો ઉપયોગ કરવો શક્ય છે જેથી તત્વોને ક્રમિક રીતે વર્ગીકૃત કરી શકાય. જો કે, આ કિસ્સામાં, અલ્ગોરિધમને વધારાની મેમરીની જરૂર પડશે. સંદર્ભોને સૉર્ટ કરવાને બદલે શોધ માટે વસ્તુઓના વિતરણનો ઉપયોગ કરીને ઇન્ટરપોલેશન સર્ચ પણ જુઓ બાહ્ય કડીઓ મોટા સમાંતર મશીનો પર રેન્ડમાઇઝ્ડ સૉર્ટિંગનો અમલ (1992) સમાંતર અલ્ગોરિધમ્સનો અમલ (1992) ફ્લેશસોર્ટ સૉર્ટિંગ અલ્ગોરિધમ્સની વિઝ્યુલાઇઝેશન