Introselect
کمپیوٹر سائنس میں، انٹرو سلیکٹ ("انٹروسپیکٹو سلیکشن" کے لیے مختصر) ایک سلیکشن الگورتھم ہے جو میڈینز کے فوری انتخاب اور میڈین کا ایک ہائبرڈ ہے جس میں تیز اوسط کارکردگی اور بہترین بدترین صورت میں کارکردگی ہوتی ہے۔ انٹرو سلیکٹ کا تعلق انٹروسرٹ چھانٹنے والے الگورتھم سے ہے: یہ بنیادی فوری انتخاب اور تیز ترتیب الگورتھم کی مماثل اصلاحات ہیں، اس میں وہ دونوں فوری الگورتھم سے شروع ہوتے ہیں، جس کی اوسط کارکردگی اچھی ہوتی ہے اور اوور ہیڈ کم ہوتا ہے، لیکن اگر فوری الگورتھم تیزی سے ترقی نہیں کرتا ہے تو ایک بہترین بدترین کیس الگورتھم (زیادہ اوور ہیڈ کے ساتھ) پر واپس آجاتا ہے۔ دونوں الگورتھم کو ڈیوڈ مسسر نے C + + اسٹینڈرڈ لائبریری کے لیے عام الگورتھم فراہم کرنے کے مقصد سے متعارف کرایا تھا جس میں تیز اوسط کارکردگی اور بہترین بدترین صورت حال کی کارکردگی دونوں ہوتی ہیں، اس طرح کارکردگی کی ضروریات کو سخت کیا جا سکتا ہے۔ تاہم، زیادہ تر C + + معیاری لائبریری کے نفاذ میں، ایک مختلف "انٹروسلیکٹ" الگورتھم استعمال کیا جاتا ہے، جو فوری انتخاب اور ہیپسلیکٹ کو یکجا کرتا ہے، اور اس میں O (n لاگ n) کا بدترین کیس رننگ ٹائم ہوتا ہے۔ سی + + ڈرافٹ معیار، 2022 تک، بدترین صورت حال کی کارکردگی پر تقاضے نہیں رکھتا ہے، اس لیے اس طرح کے انتخاب کی اجازت دیتا ہے۔ الگورتھم انٹروسورٹ قکسورٹ کے مقابلے میں عملی کارکردگی حاصل کرتا ہے جبکہ قکسورٹ اور ہیپسورٹ کا ہائبرڈ بنا کر او (این لاگ این) بدترین صورت حال کے رویے کو محفوظ رکھتا ہے۔ انٹروسورٹ تیز رفتار سے شروع ہوتا ہے، لہذا اگر تیز رفتار کام کرتا ہے تو یہ تیز رفتار سے ملتی جلتی کارکردگی حاصل کرتا ہے، اور اگر تیز رفتار تیزی سے ترقی نہیں کرتا ہے تو ہیپسورٹ (جس میں بہترین بدترین کارکردگی ہوتی ہے) پر واپس آ جاتا ہے۔ اسی طرح، انٹروسلیکٹ فوری انتخاب کی طرح کارکردگی کے ساتھ بدترین صورت میں لکیری انتخاب حاصل کرنے کے لیے میڈین کے ساتھ فوری انتخاب کو جوڑتا ہے۔ انٹروسلیکٹ پر امید طور پر فوری انتخاب کے ساتھ شروع کر کے کام کرتا ہے اور صرف بدترین صورت میں لکیری ٹائم سلیکشن الگورتھم (میڈینز الگورتھم کا بلم-فلائیڈ-پراٹ-ریوسٹ-ٹارجن میڈین) میں تبدیل ہوتا ہے اگر یہ کافی ترقی کیے بغیر بہت زیادہ بار بار ہوتا ہے۔ بدلنے کی حکمت عملی الگورتھم کا بنیادی تکنیکی مواد ہے۔ صرف تکرار کو مستقل گہرائی تک محدود رکھنا کافی نہیں ہے، کیونکہ اس سے الگورتھم تمام کافی بڑی فہرستوں کو آن کر دے گا۔ مسیر چند آسان طریقوں پر تبادلہ خیال کرتا ہے: اب تک زیر عمل ذیلی تقسیم کے سائز کی فہرست پر نظر رکھیں۔ اگر کسی بھی وقت فہرست کے سائز کو آدھا کیے بغیر k ریکرسو کالز کی گئی ہیں، تو کچھ چھوٹے مثبت k کے لیے، بدترین صورت میں لکیری الگورتھم پر جائیں۔ اب تک تیار کردہ تمام پارٹیشنوں کے سائز کا مجموعہ بنائیں۔ اگر یہ فہرست کے سائز کے اوقات سے کچھ چھوٹے مثبت مستقل k سے تجاوز کرتا ہے، تو بدترین صورت میں لکیری الگورتھم پر جائیں۔ اس رقم کو ایک واحد اسکیلر متغیر میں ٹریک کرنا آسان ہے۔ دونوں نقطہ نظر تکرار کی گہرائی کو k ¥ log n ′ = O (log n) اور کل چلنے کے وقت کو O (n) تک محدود کرتے ہیں۔ مقالے میں تجویز کیا گیا کہ انٹروسلیٹ پر مزید تحقیق آنے والی ہے، لیکن مصنف 2007 میں اس طرح کی مزید تحقیق شائع کیے بغیر ریٹائر ہو گئے۔ فلائیڈ-ریوسٹ الگورتھم حوالہ جات سلیکشن الگورتھم بھی دیکھیں۔