Introselect
કોમ્પ્યુટર વિજ્ઞાનમાં, ઇન્ટ્રોસેલેક્ટ ("આત્મનિરીક્ષણ પસંદગી" માટે ટૂંકું) એ એક પસંદગી અલ્ગોરિધમ છે જે ઝડપી સરેરાશ પ્રદર્શન અને શ્રેષ્ઠ ખરાબ-કેસ પ્રદર્શન ધરાવતા માધ્યમોની ઝડપી પસંદગી અને મધ્યસ્થીનું સંકર છે. ઇન્ટ્રોસેલેક્ટ ઇન્ટ્રોસોર્ટ સોર્ટિંગ અલ્ગોરિધમ સાથે સંબંધિત છેઃ આ મૂળભૂત ઝડપી પસંદગી અને ઝડપી વર્ગીકરણ અલ્ગોરિધમ્સના સમાન સુધારાઓ છે, જેમાં તેઓ બંને ઝડપી અલ્ગોરિધમથી શરૂઆત કરે છે, જે સારી સરેરાશ કામગીરી અને ઓછી ઓવરહેડ ધરાવે છે, પરંતુ જો ઝડપી અલ્ગોરિધમ ઝડપથી પ્રગતિ ન કરે તો શ્રેષ્ઠ ખરાબ-કેસ અલ્ગોરિધમ (ઉચ્ચ ઓવરહેડ સાથે) પર પાછા ફરે છે. સી + + સ્ટાન્ડર્ડ લાઇબ્રેરી માટે સામાન્ય અલ્ગોરિધમ્સ પ્રદાન કરવાના હેતુથી ડેવિડ મુસેર દ્વારા બંને અલ્ગોરિધમ્સ રજૂ કરવામાં આવ્યા હતા, જેમાં ઝડપી સરેરાશ પ્રદર્શન અને શ્રેષ્ઠ ખરાબ-કેસ પ્રદર્શન બંને હોય છે, આમ પ્રદર્શન જરૂરિયાતોને કડક કરવાની મંજૂરી આપે છે. જો કે, મોટાભાગના સી + + સ્ટાન્ડર્ડ લાઈબ્રેરી અમલીકરણમાં, એક અલગ "ઇન્ટ્રોસેલેક્ટ" અલ્ગોરિધમનો ઉપયોગ થાય છે, જે ઝડપી પસંદગી અને હિપસેલેક્ટને જોડે છે, અને તેમાં ઓ (એન લોગ એન) નો સૌથી ખરાબ કેસ ચાલી રહ્યો છે. સી + + ડ્રાફ્ટ સ્ટાન્ડર્ડ, 2022 સુધીમાં, સૌથી ખરાબ-કેસ પ્રદર્શન પર આવશ્યકતાઓ નથી, તેથી આવી પસંદગીને મંજૂરી આપે છે. એલ્ગોરિધમ્સ ઇન્ટ્રોસોર્ટ ક્વિકસોર્ટ સાથે તુલનાત્મક વ્યવહારુ કામગીરી હાંસલ કરે છે જ્યારે ક્વિકસોર્ટ અને હીપસોર્ટનું સંકર બનાવીને ઓ (એન લોગ એન) સૌથી ખરાબ-કેસ વર્તણૂકને જાળવી રાખે છે. ઇન્ટ્રોસોર્ટ ક્વિકસોર્ટથી શરૂ થાય છે, તેથી જો ક્વિકસોર્ટ કામ કરે તો તે ક્વિકસોર્ટ જેવું જ પ્રદર્શન પ્રાપ્ત કરે છે, અને જો ક્વિકસોર્ટ ઝડપથી પ્રગતિ ન કરે તો તે હિપસોર્ટ (જે શ્રેષ્ઠ સૌથી ખરાબ-કેસ પ્રદર્શન ધરાવે છે) પર પાછા આવે છે. તેવી જ રીતે, ઇન્ટ્રોસેલેક્ટ ઝડપી પસંદગીની સમાન કામગીરી સાથે સૌથી ખરાબ-કેસ રેખીય પસંદગી પ્રાપ્ત કરવા માટે મધ્યસ્થની મધ્ય સાથે ઝડપી પસંદગીને જોડે છે. ઇન્ટ્રોસેલેક્ટ આશાવાદી રીતે ઝડપી પસંદગી સાથે શરૂઆત કરીને કામ કરે છે અને જો તે પૂરતી પ્રગતિ કર્યા વિના ઘણી વખત પુનરાવર્તન કરે તો માત્ર સૌથી ખરાબ-કેસ રેખીય-સમય પસંદગી અલ્ગોરિધમ (મીડિયન્સ અલ્ગોરિધમનો બ્લમ-ફ્લોઇડ-પ્રેટ-રીવેસ્ટ-ટર્જન મીડિયન) પર સ્વિચ કરે છે. સ્વિચિંગ વ્યૂહરચના એ અલ્ગોરિધમનો મુખ્ય તકનીકી વિષયવસ્તુ છે. ફક્ત પુનરાવર્તનને સતત ઊંડાણ સુધી મર્યાદિત કરવું પૂરતું નથી, કારણ કે આ અલ્ગોરિધમને તમામ પૂરતી મોટી સૂચિ પર સ્વિચ કરશે. મુસેર કેટલાક સરળ અભિગમોની ચર્ચા કરે છેઃ અત્યાર સુધી પ્રક્રિયા કરાયેલા પેટા વિભાગોના કદની યાદી પર નજર રાખો. જો કોઈ પણ સમયે સૂચિના કદને અડધું કર્યા વિના k પુનરાવર્તિત કૉલ્સ કરવામાં આવ્યા હોય, તો કેટલાક નાના હકારાત્મક k માટે, સૌથી ખરાબ-કેસ રેખીય અલ્ગોરિધમ પર સ્વિચ કરો. અત્યાર સુધી પેદા થયેલા તમામ પાર્ટીશનોના કદનો સરવાળો કરો. જો આ સૂચિનું કદ અમુક નાના હકારાત્મક અચળાંક k કરતા વધી જાય, તો સૌથી ખરાબ-કેસ રેખીય અલ્ગોરિધમ પર સ્વિચ કરો. આ રકમને એક જ સ્કેલર ચલમાં ટ્રેક કરવી સરળ છે. બંને અભિગમો પુનરાવર્તનની ઊંડાઈને k′log n′ = O (log n) અને કુલ ચાલી રહેલા સમયને O (n) સુધી મર્યાદિત કરે છે. પેપર સૂચવે છે કે ઇન્ટ્રોસેલેક્ટ પર વધુ સંશોધન આગામી હતું, પરંતુ લેખક 2007 માં આવા કોઈ વધુ સંશોધન પ્રકાશિત કર્યા વિના નિવૃત્ત થયા. ફ્લોયડ-રીવેસ્ટ અલ્ગોરિધમ સંદર્ભો પસંદગી અલ્ગોરિધમનો પણ જુઓ