Flashsort
فلیش شارٹ ایک ڈسٹری بیوشن شارٹنگ الگورتھم ہے جو یکساں طور پر تقسیم شدہ ڈیٹا سیٹوں اور نسبتا کم اضافی میموری کی ضرورت کے لیے لکیری کمپیوٹیشنل پیچیدگی کو ظاہر کرتا ہے۔ اصل کام 1998 میں کارل ڈیٹریچ نیوبرٹ نے شائع کیا تھا۔ تصور فلیش شارٹ ہسٹوگرام کی ترتیب کا ایک موثر ان پلیس نفاذ ہے، جو خود بالٹی کی ترتیب کی ایک قسم ہے۔ یہ ہر ایک ان پٹ عنصر کو بالٹیوں میں سے کسی ایک کو تفویض کرتا ہے، بالٹیوں کو صحیح ترتیب میں رکھنے کے لیے ان پٹ کو مؤثر طریقے سے دوبارہ ترتیب دیتا ہے، پھر ہر بالٹی کو ترتیب دیتا ہے۔ اصل الگورتھم ایک ان پٹ صف کو مندرجہ ذیل ترتیب دیتا ہے: ان پٹ یا ترجیحی علم پر پہلے پاس کا استعمال کرتے ہوئے، کم سے کم اور زیادہ سے زیادہ ترتیب کی چابیاں تلاش کریں۔ رینج کو لکیری طور پر بالٹیوں میں تقسیم کریں۔ ہر بالٹی میں آنے والے عناصر کی تعداد گنتے ہوئے ان پٹ کے اوپر سے ایک پاس کریں۔ (نیوبرٹ بالٹیوں کو "کلاسز" اور ان کی بالٹیوں میں عناصر کی تفویض کو "درجہ بندی" کہتے ہیں۔) ہر بالٹی میں عناصر کی گنتی کو سابقہ رقم میں تبدیل کریں، جہاں بالٹی میں عناصر کی تعداد یا اس سے کم ہے۔ (اور۔) ان پٹ کو دوبارہ ترتیب دیں تاکہ ہر بالٹی کے تمام عناصر کو ان جگہوں پر محفوظ کیا جائے جہاں. ہر بالٹی کو داخل کرنے کی ترتیب کا استعمال کرتے ہوئے ترتیب دیں۔ مرحلہ 1-3 اور 6 کسی بھی بالٹی کی قسم کے لیے عام ہیں، اور عام سے بالٹی کی قسم کی تکنیکوں کا استعمال کرتے ہوئے بہتر کیا جا سکتا ہے۔ خاص طور پر، مقصد یہ ہے کہ بالٹیاں تقریبا برابر سائز (ہر عنصر) کی ہوں، جس میں مثالی مقدار کو کوانٹائل میں تقسیم کیا جائے۔ اگرچہ بنیادی الگورتھم ایک لکیری انٹرپولیشن قسم ہے، اگر ان پٹ کی تقسیم کو غیر یکساں جانا جاتا ہے، تو غیر لکیری تقسیم اس آئیڈیل کا زیادہ قریب سے تخمینہ لگائے گی۔ اسی طرح، حتمی ترتیب متعدد تکنیکوں میں سے کسی کو بھی استعمال کر سکتی ہے، بشمول ایک تکراری فلیش ترتیب۔ جو چیز فلیش کی ترتیب میں فرق کرتی ہے وہ مرحلہ 5 ہے: صرف اضافی میموری کے الفاظ کا استعمال کرتے ہوئے ہر بالٹی کے عناصر کو صحیح متعلقہ ترتیب میں اکٹھا کرنے کے لیے ایک موثر ان پلیس الگورتھم۔ میموری کا موثر نفاذ فلیش شارٹ دوبارہ ترتیب کا مرحلہ چکروں میں چلتا ہے۔ عناصر "غیر درجہ بند" سے شروع ہوتے ہیں، پھر انہیں صحیح بالٹی میں منتقل کیا جاتا ہے اور "درجہ بند" سمجھا جاتا ہے۔ بنیادی طریقہ کار یہ ہے کہ ایک غیر درجہ بند عنصر کا انتخاب کیا جائے، اس کی صحیح بالٹی تلاش کی جائے، اسے وہاں ایک غیر درجہ بند عنصر کے ساتھ تبدیل کیا جائے (جو موجود ہونا چاہیے، کیونکہ ہم نے ہر بالٹی کا سائز وقت سے پہلے شمار کیا تھا)، اسے درجہ بند کے طور پر نشان زد کیا جائے، اور پھر صرف تبدیل شدہ غیر درجہ بند عنصر کے ساتھ دہرایا جائے۔ آخر کار، عنصر خود کے ساتھ تبدیل ہو جاتا ہے اور سلسلہ ختم ہو جاتا ہے۔ فی بالٹی دو (لفظ کے سائز کے) متغیرات کا استعمال کرتے ہوئے تفصیلات کو سمجھنا آسان ہے۔ ہوشیار حصہ ان متغیرات میں سے ایک کا خاتمہ ہے، جس سے دوگنا بالٹیاں استعمال کی جا سکتی ہیں اور اس وجہ سے حتمی چھانٹ پر آدھا وقت خرچ ہوتا ہے۔ اسے دو متغیر فی بالٹی کے ساتھ سمجھنے کے لیے، فرض کریں کہ اضافی الفاظ کی دو صف ہیں: بالٹی (اور) کی (مقررہ) اوپری حد ہے، جبکہ بالٹی میں (متحرک) انڈیکس ہے، تو۔ ہم لوپ غیر متغیر کو برقرار رکھتے ہیں کہ ہر بالٹی کو ایک غیر درجہ بند سابقہ (کیونکہ ابھی تک ان کے ہدف بالٹیوں میں منتقل نہیں کیا گیا ہے) اور ایک درجہ بند لاحقہ (کیونکہ یہ سب صحیح بالٹی میں ہیں اور دوبارہ منتقل نہیں کیے جائیں گے) میں تقسیم کیا گیا ہے۔ ابتدائی طور پر اور تمام عناصر غیر درجہ بند ہیں۔ جیسے جیسے ترتیب جاری رہتی ہے، تمام عناصر کو اس وقت تک کم کیا جاتا ہے جب تک کہ تمام عناصر کو صحیح بالٹی میں درجہ بند نہیں کیا جاتا ہے۔ ہر دور کا آغاز پہلی نامکمل درجہ بند بالٹی (جس کے پاس ہے) کو تلاش کرنے اور اس بالٹی میں پہلا غیر درجہ بند عنصر لینے سے ہوتا ہے۔ (نیوبرٹ اسے "سائیکل لیڈر" کہتے ہیں۔) عارضی متغیر میں کاپی کریں اور دہرائیں: اس بالٹی کا حساب لگائیں جس سے اس کا تعلق ہے۔ وہ مقام ہونے دیں جہاں ذخیرہ کیا جائے گا۔ کے ساتھ تبادلہ کریں، یعنی۔ پچھلی قیمت حاصل کرتے ہوئے اسٹور کریں اس طرح بے گھر ہو جائیں۔ اس حقیقت کی عکاسی کرنے میں کمی جو اب صحیح طریقے سے درجہ بندی کی گئی ہے۔ اگر، اس لوپ کو نئے کے ساتھ دوبارہ شروع کریں۔ اگر، یہ راؤنڈ ختم ہو گیا ہے اور ایک نیا پہلا غیر درجہ بند عنصر تلاش کریں۔ جب مزید غیر درجہ بند عناصر نہ ہوں تو بالٹیوں میں تقسیم مکمل ہو جاتی ہے۔ جب اس طرح سے فی بالٹی دو متغیرات کے ساتھ لاگو کیا جاتا ہے، تو ہر راؤنڈ کے ابتدائی نقطہ کا انتخاب حقیقت میں من مانی ہوتا ہے ؛ کسی بھی غیر درجہ بند عنصر کو سائیکل لیڈر کے طور پر استعمال کیا جا سکتا ہے۔ واحد ضرورت یہ ہے کہ سائیکل لیڈرز کو مؤثر طریقے سے پایا جا سکے۔ اگرچہ پچھلی تفصیل سائیکل لیڈروں کو تلاش کرنے کے لیے استعمال ہوتی ہے، لیکن حقیقت میں اس کے بغیر کرنا ممکن ہے، جس سے پورے لفظ کی صف کو ختم کیا جا سکتا ہے۔ (تقسیم مکمل ہونے کے بعد، بالٹی کی حدود میں پایا جا سکتا ہے۔) فرض کریں کہ ہم نے تمام عناصر کو درجہ بند کر دیا ہے، اور ایک ممکنہ نئے سائیکل لیڈر کے طور پر غور کر رہے ہیں۔ اس کی ٹارگٹ بالٹی کا حساب لگانا آسان ہے۔ لوپ غیر متغیر کے ذریعہ، اس کی درجہ بندی کی جاتی ہے اگر، اور غیر درجہ بند اگر اس حد سے باہر ہے۔ پہلی عدم مساوات کی جانچ کرنا آسان ہے، لیکن دوسری قدر کی ضرورت محسوس ہوتی ہے۔ یہ پتہ چلتا ہے کہ انڈکشن مفروضہ کہ تمام عناصر کی درجہ بندی کی گئی ہے اس کا مطلب یہ ہے کہ، اس لیے دوسری عدم مساوات کی جانچ کرنا ضروری نہیں ہے۔ بالٹی پر غور کریں کہ وہ کس پوزیشن میں آتی ہے۔ یعنی۔ انڈکشن مفروضے کے مطابق، نیچے دیے گئے تمام عناصر، جن میں تمام بالٹیاں شامل ہیں، مکمل طور پر درجہ بند ہیں۔ I. e. ان بالٹیوں میں شامل کوئی بھی عنصر باقی صف میں نہیں رہتا ہے۔ اس لیے ایسا ممکن نہیں ہے۔ واحد باقی معاملہ ہے، جس کا مطلب ہے، کیو ای ڈی۔ اسے شامل کرتے ہوئے، فلیش شارٹ ڈسٹری بیوشن الگورتھم جیسا کہ اوپر بیان کیا گیا ہے اور سے شروع ہوتا ہے۔ پھر آگے بڑھیں: اگر تقسیم مکمل ہو گئی ہے۔ یہ دیکھتے ہوئے، اس بالٹی کا حساب لگائیں جس سے اس کا تعلق ہے۔ اگر، تو غیر درجہ بند ہے۔ اسے ایک عارضی متغیر کاپی کریں اور: وہ مقام ہونے دیں جہاں ذخیرہ کیا جائے گا۔ کے ساتھ تبادلہ کریں، یعنی۔ پچھلی قیمت حاصل کرتے ہوئے اسٹور کریں اس طرح بے گھر ہو جائیں۔ اس حقیقت کی عکاسی کرنے میں کمی جو اب صحیح طریقے سے درجہ بندی کی گئی ہے۔ اگر، اس بالٹی کا حساب لگائیں جس سے تعلق رکھتا ہے اور اس (اندرونی) لوپ کو نئے کے ساتھ دوبارہ شروع کریں۔ اب صحیح طریقے سے درجہ بندی کی گئی ہے۔ (بیرونی) لوپ کو بڑھائیں اور دوبارہ شروع کریں۔ میموری کو بچانے کے دوران، فلیش سارٹ کا نقصان یہ ہے کہ یہ بہت سے پہلے سے درجہ بند عناصر کے لیے بالٹی کو دوبارہ گنتی کرتا ہے۔ یہ پہلے سے ہی فی عنصر دو بار کیا جاتا ہے (ایک بار بالٹی گنتی کے مرحلے کے دوران اور دوسری بار جب ہر عنصر کو منتقل کیا جاتا ہے)، لیکن پہلے غیر درجہ بند عنصر کی تلاش کے لیے زیادہ تر عناصر کے لیے تیسرے حساب کی ضرورت ہوتی ہے۔ یہ مہنگا ہو سکتا ہے اگر بالٹیوں کو سادہ لکیری انٹرپولیشن سے زیادہ پیچیدہ فارمولے کا استعمال کرتے ہوئے تفویض کیا جائے۔ ایک متغیر ایک نامکمل بالٹی میں آخری غیر درجہ بند عنصر کو سائیکل لیڈر کے طور پر لے کر حسابات کی تعداد کو تقریبا کم کر کے زیادہ سے زیادہ کر دیتا ہے: پہلی نامکمل درجہ بند بالٹی کی شناخت کرنے والے متغیر کو برقرار رکھیں۔ شروع کرتے ہیں، اور تقسیم کب مکمل ہوتی ہے۔ جانے دیں۔ اگر، اس لوپ کو بڑھائیں اور دوبارہ شروع کریں۔ (.) اس بالٹی کا حساب لگائیں جس کا تعلق ہے۔ اگر، پھر اور ہم بالٹی کے ساتھ کیا جاتا ہے. اس لوپ کو بڑھائیں اور دوبارہ شروع کریں۔ اگر، درجہ بندی معمولی ہے۔ اس لوپ کو کم کریں اور دوبارہ شروع کریں۔ اگر، تو غیر درجہ بند ہے۔ پچھلے کیس کی طرح درجہ بندی کا لوپ انجام دیں، پھر اس لوپ کو دوبارہ شروع کریں۔ زیادہ تر عناصر کی بالٹیاں صرف دو بار شمار کی جاتی ہیں، سوائے ہر بالٹی کے آخری عنصر کے، جو مندرجہ ذیل بالٹی کی تکمیل کا پتہ لگانے کے لیے استعمال ہوتا ہے۔ غیر درجہ بند عناصر کی گنتی کو برقرار رکھ کر اور صفر تک پہنچنے پر روک کر ایک چھوٹی سی مزید کمی حاصل کی جا سکتی ہے۔ کارکردگی صرف اضافی میموری کی ضروریات بالٹی کی حدود کو ذخیرہ کرنے کے لیے معاون ویکٹر اور استعمال ہونے والے دیگر متغیرات کی مستقل تعداد ہیں۔ مزید برآں، ہر عنصر کو صرف ایک بار منتقل کیا جاتا ہے (ایک عارضی بفر کے ذریعے، لہذا دو حرکت کی کارروائیاں)۔ تاہم، یہ میموری کی کارکردگی اس نقصان کے ساتھ آتی ہے کہ صف تک تصادفی طور پر رسائی حاصل کی جاتی ہے، لہذا پوری صف سے چھوٹے ڈیٹا کیش سے فائدہ نہیں اٹھا سکتا۔ بالٹی کی تمام اقسام کی طرح، کارکردگی کا انحصار بالٹیوں کے توازن پر ہوتا ہے۔ متوازن ڈیٹا سیٹ کی مثالی صورت میں، ہر بالٹی تقریبا ایک ہی سائز کی ہوگی۔ اگر ان پٹ سائز میں بالٹیوں کی تعداد لکیری ہے، تو ہر بالٹی کا ایک مستقل سائز ہوتا ہے، لہذا اندراج کی ترتیب جیسے الگورتھم کے ساتھ ایک بالٹی کو ترتیب دینے میں پیچیدگی ہوتی ہے۔ لہذا حتمی اندراج کی اقسام کا چلنے کا وقت ہے۔ بالٹیوں کی تعداد کے لیے قدر کا انتخاب کرنا، عناصر (اعلی) کی درجہ بندی میں گزارے گئے وقت اور حتمی اندراج کی ترتیب کے مرحلے (کم) میں گزارے گئے وقت کی تجارت کرتا ہے۔ مثال کے طور پر، اگر متناسب طور پر منتخب کیا جاتا ہے، تو پھر حتمی اندراج کی اقسام کا چلنے کا وقت ہے۔ بدترین صورت حال میں جہاں تقریبا تمام عناصر چند بالٹیوں میں ہوتے ہیں، الگورتھم کی پیچیدگی حتمی بالٹی چھانٹنے کے طریقہ کار کی کارکردگی سے محدود ہوتی ہے، لہذا اس میں کمی واقع ہوتی ہے۔ الگورتھم کے تغیرات بالٹیوں پر بہتر کارکردگی کا مظاہرہ کرنے والی اقسام جیسے کوئکسورٹ یا ریکرسو فلیش شارٹ کا استعمال کرکے بدترین صورت میں کارکردگی کو بہتر بناتے ہیں جو ایک مخصوص سائز کی حد سے تجاوز کرتے ہیں۔ یکساں طور پر تقسیم شدہ بے ترتیب ڈیٹا کے ساتھ، فلیش شارٹ سب کے لیے ہیپس شارٹ سے تیز اور فوری طور پر تیز ہے۔ یہ تیز رفتار سے تقریبا دوگنا تیز ہو جاتا ہے۔ نوٹ کریں کہ یہ پیمائش 1990 کی دہائی کے آخر میں کی گئی تھی، جب میموری کی درجہ بندی کیشنگ پر بہت کم منحصر تھی۔ ان سیٹو پرموٹیشن کی وجہ سے جو فلیش شارٹ اپنے درجہ بندی کے عمل میں انجام دیتا ہے، فلیش شارٹ مستحکم نہیں ہے۔ اگر استحکام کی ضرورت ہو تو، دوسری صف کا استعمال کرنا ممکن ہے تاکہ عناصر کی ترتیب وار درجہ بندی کی جا سکے۔ تاہم، اس صورت میں، الگورتھم کو اضافی میموری کی ضرورت ہوگی۔ حوالہ جات کو ترتیب دینے کے بجائے تلاش کے لیے آئٹمز کی تقسیم کا استعمال کرتے ہوئے انٹرپولیشن سرچ بھی دیکھیں بیرونی لنکس بڑی متوازی مشینوں پر بے ترتیب ترتیب کے نفاذ (1992) متوازی الگورتھم کا نفاذ (1992) فلیش شارٹ ترتیب الگورتھم کا تصور