فاسٹ آرڈرنگ ٹونی ہال کی طرف سے تیار کردہ ایک قسم کا الگورتھم ہے۔ اوسط حالت میں ، آرڈر کرنے کے لئے n اشیاء کو O ((nlogn) بار موازنہ کی ضرورت ہوتی ہے۔ بدترین حالت میں ، O ((n2) بار موازنہ کی ضرورت ہوتی ہے ، لیکن یہ غیر معمولی ہے۔ در حقیقت ، فاسٹ آرڈرنگ عام طور پر دوسرے O ((nlogn) الگورتھم سے نمایاں طور پر تیز ہوتی ہے ، کیونکہ اس کے اندرونی لوپ کو زیادہ تر فن تعمیرات میں بہت موثر انداز میں لاگو کیا جاسکتا ہے۔
فوری ترتیب تقسیم اور فتح کرنے کی حکمت عملی کا استعمال کرتے ہوئے ایک فہرست کو دو ذیلی فہرستوں میں تقسیم کرتا ہے۔
الگورتھم کے اقدامات:
1، ایک عنصر کو منتخب کریں، جو کہ ایک اہم عنصر ہے، اور اس کے بعد ایک عنصر کو منتخب کریں، جو کہ ایک اہم عنصر ہے.
2، دوبارہ ترتیب دینے والے صفوں میں، تمام عناصر جو بیعانہ کی قیمت سے کم ہیں وہ بیعانہ کے سامنے اور تمام عناصر جو بیعانہ کی قیمت سے زیادہ ہیں وہ بیعانہ کے پیچھے ہیں۔ اس تقسیم سے نکلنے کے بعد، یہ بیعانہ صف کے وسط میں ہے۔ یہ تقسیم کا آپریشن کہا جاتا ہے۔
3، recursively (recursive) ذیلی صفوں کو ترتیب دیتا ہے جن کے ذیلی صفوں میں کم سے کم بیعانہ عنصر ہیں اور جن کے ذیلی صفوں میں زیادہ سے زیادہ بیعانہ عنصر ہیں۔
ریکوریشن کی سب سے بنیادی صورت یہ ہے کہ صف کا سائز صفر یا ایک ہے، یعنی یہ ہمیشہ کے لئے اچھی طرح سے ترتیب دیا گیا ہے۔ اگرچہ یہ مسلسل ریکوریشن کرتا رہتا ہے، لیکن یہ الگورتھم ہمیشہ باہر نکل جاتا ہے کیونکہ ہر تکرار میں یہ کم از کم ایک عنصر کو اپنی آخری پوزیشن میں رکھتا ہے۔
ڈھیر لگانا (انگریزی: Heapsort) اس طرح کے اعداد و شمار کے ڈھانچے کا استعمال کرتے ہوئے ڈھیر لگانے کا ایک الگورتھم ہے۔ ڈھیر ایک ایسا ڈھانچہ ہے جو تقریبا مکمل طور پر بائنری درخت ہے اور اس کے ساتھ ساتھ اس ڈھیر کی خصوصیات کو پورا کرتا ہے: یعنی اس کے نچلے نوڈس کی کلیدی قدر یا انڈیکس ہمیشہ اس کے والدین نوڈس سے کم یا زیادہ ہوتا ہے۔
اسٹیک کی ترتیب کی اوسط وقت کی پیچیدگی O ((nlogn) ہے.
الگورتھم کے اقدامات:
1، ایک H [0...n-1] سیٹ بنائیں
2، اسٹیک کے سر (زیادہ سے زیادہ) اور اسٹیک کے آخر کو تبدیل کریں
3، ڈھیر کو 1 سے کم کریں اور shift_down ((0) کو کال کریں ، جس کا مقصد نئے صف کے اوپری حصے کے اعداد و شمار کو اسی مقام پر ایڈجسٹ کرنا ہے۔
4، مرحلہ 2 کو دہرائیں، جب تک کہ ان کی مقدار 1 نہ ہو جائے۔
انضمام کی ترتیب (Mergesort) ایک موثر ترتیب دینے والا الگورتھم ہے جو انضمام کے آپریشن پر مبنی ہے۔ یہ الگورتھم تقسیم اور فتح کا ایک بہت ہی عام استعمال ہے۔
الگورتھم کے اقدامات:
1، درخواست کی جگہ، جس کا سائز دو ترتیب شدہ سیریز کے مجموعے کے طور پر ہے، اور اس جگہ کو ضم شدہ سیریز کو ذخیرہ کرنے کے لئے استعمال کیا جاتا ہے
2، دو پوائنٹرز کو ترتیب دیں، جن کی ابتدائی پوزیشن دو ترتیب شدہ سیریز کی ابتدائی پوزیشنوں کے طور پر ہے
3، دو اشاروں کی طرف اشارہ کرنے والے عناصر کا موازنہ کریں، نسبتاً چھوٹے عناصر کو منتخب کریں، انہیں ملانے کی جگہ پر رکھیں اور اشارے کو اگلے مقام پر منتقل کریں
4، مرحلہ 3 کو دہرائیں جب تک کہ کوئی اشارہ سیریز کے آخر تک نہ پہنچ جائے
5، دوسرے سیریز کے باقی تمام عناصر کو براہ راست ضم سیریز کے آخر میں کاپی کریں
بائنری تلاش کرنے والا الگورتھم ایک ایسا سرچ الگورتھم ہے جو کسی مخصوص عنصر کو ترتیب شدہ صف میں تلاش کرتا ہے۔ سرچ کا عمل صف کے درمیانی عنصر سے شروع ہوتا ہے ، اگر درمیانی عنصر وہی عنصر ہے جس کی تلاش کی جارہی ہے تو سرچ کا عمل ختم ہوجاتا ہے۔ اگر کوئی خاص عنصر درمیانی عنصر سے بڑا یا چھوٹا ہے تو ، صف کے اس نصف حصے میں تلاش کی جاتی ہے جو درمیانی عنصر سے بڑا یا چھوٹا ہے ، اور اسی طرح شروع ہوتا ہے۔ اگر کسی مرحلے میں صف خالی ہے ، تو اس کا مطلب یہ نہیں مل سکتا ہے۔ اس طرح کا سرچ الگورتھم ہر موازنہ میں تلاش کی حد کو ایک بار کم کرتا ہے۔ ہر نصف تلاش میں تلاش کے علاقے کو آدھا کردیا جاتا ہے ، جس میں وقت کی پیچیدگی ہے۔
بی ایف پی آر ٹی الگورتھم کا حل ایک کلاسک مسئلہ ہے ، یعنی کسی n عناصر کے سلسلے میں سے k بڑا ((k چھوٹا)) عنصر منتخب کرنا ، اور ہنر مند تجزیہ کے ذریعہ ، بی ایف پی آر ٹی اس بات کا یقین کرسکتا ہے کہ بدترین صورت میں بھی لکیری وقت کی پیچیدگی ہے۔ اس الگورتھم کا خیال تیزی سے ترتیب دینے کے خیال سے ملتا جلتا ہے ، اور یقینا ، پانچ مصنفین نے اس بات کو یقینی بنانے کے لئے نفیس طور پر کام کیا ہے کہ الگورتھم بدترین صورت میں بھی o ((n) وقت کی پیچیدگی تک پہنچ سکے گا۔
الگورتھم کے اقدامات:
1، n عناصر کو ہر 5 میں سے ایک گروپ میں تقسیم کریں، n/5 ((اوپری سرحد) گروپ میں تقسیم کریں۔
2، ہر سیٹ کے درمیانہ نمبر کو نکالنے، کسی بھی ترتیب دینے کا طریقہ، مثال کے طور پر داخل کرنے کے لئے ترتیب دیں.
3، recursive call selection algorithm finds the median of all medians in the previous step, set to x, even number of medians in case set to select the smallest of the middle one. 3، recursive call selection algorithm finds the median of all medians in the previous step, set to x, even number of medians in case of even numbers set to select the smallest of the middle one.
4، x کے ساتھ تقسیم کرنے کے لئے، x سے کم کے لئے ایک عدد مقرر کریں، اور x سے زیادہ کے لئے ایک عدد مقرر کریں n-k.
5، اگر i==k، واپس x؛ اگر i
ختم ہونے کی شرط: n = 1، واپس کیا جاتا ہے i چھوٹے عنصر.
گہرائی سے پہلی تلاش (انگریزی: Depth-First-Search) ایک قسم کا سرچ الگورتھم ہے۔ یہ درخت کے گہرائی کے ساتھ درخت کے نوڈس کو گھومتا ہے اور درخت کی شاخوں کو جتنا ممکن ہو گہرائی تک تلاش کرتا ہے۔ جب نوڈس v کے تمام اطراف کو تلاش کیا جاتا ہے تو ، تلاش شروع ہونے والے نوڈس پر واپس آجاتی ہے جو نوڈس v کے پاس پائے جاتے ہیں۔ یہ عمل اس وقت تک جاری رہتا ہے جب تک کہ تمام نوڈس جو ماخذ نوڈس سے پہنچنے کے قابل ہیں مل نہ جائیں۔ اگر کوئی ماخذ نوڈس موجود نہیں ہے تو ، ان میں سے کسی کو ماخذ نوڈس کے طور پر منتخب کریں اور اس عمل کو دہرائیں ، جب تک کہ تمام نوڈس تک رسائی حاصل نہ ہو جائے۔ ڈی ایف ایس اندھے تلاش کا حصہ ہے۔
گہری ترجیح کی تلاش گرافک میں ایک کلاسک الگورتھم ہے جس کا استعمال گہری ترجیح کی تلاش کے الگورتھم کے ذریعہ ہدف کے گراف کے مطابق ٹاپولوجیکل ترتیب کی فہرست تیار کرنے کے لئے کیا جاسکتا ہے۔ ٹاپولوجیکل ترتیب کی فہرستوں کا استعمال کرتے ہوئے گرافک کے بہت سے متعلقہ مسائل کو آسانی سے حل کیا جاسکتا ہے ، جیسے زیادہ سے زیادہ راستے کا مسئلہ وغیرہ۔ عام طور پر ڈی ایف ایس الگورتھم کو اسٹیک ڈیٹا ڈھانچے کے ساتھ نافذ کرنے میں مدد ملتی ہے۔
گہرائی میں گرافک الگورتھم کے اقدامات کو ترجیح دیں:
1، چوٹی v تک رسائی؛
2، گہرائی کی ترجیح کے ساتھ گراف کو گراف کے غیر قابل رسائی ہمسایہ مقامات سے شروع کریں؛ جب تک کہ گراف کے تمام چوٹیوں تک رسائی حاصل نہ ہو جہاں v کے ساتھ راستے ملتے ہیں؛
3، اگر اس وقت گراف میں کوئی چوٹی نہیں ہے تو، ایک غیر متوقع چوٹی سے شروع کریں اور گہرائی کی ترجیح کو دوبارہ چلائیں، جب تک کہ گراف میں تمام چوٹیوں تک رسائی حاصل نہ ہو.
اس کے علاوہ ، آپ کو یہ بھی بتانا چاہئے کہ آپ کے پاس کیا ہے:
ڈی ایف ایس ایک ہی نقطہ v سے شروع ہوتا ہے، پھر v سے شروع ہوتا ہے، اس کے کسی بھی ہمسایہ نقطہ w1 تک رسائی حاصل کرتا ہے؛ پھر w1 سے شروع ہوتا ہے، w2 تک رسائی حاصل کرتا ہے، جو w1 کے ساتھ ہمسایہ ہے لیکن ابھی تک نہیں پہنچا ہے؛ اور پھر w2 سے شروع ہوتا ہے، اسی طرح کا دورہ کرتا ہے،... اور اسی طرح تک پہنچ جاتا ہے، جب تک کہ تمام ہمسایہ نقطہ u تک پہنچ جاتا ہے.
اس کے بعد، ایک قدم پیچھے ہٹیں اور پچھلے دورے پر آنے والے چوٹی پر واپس جائیں اور دیکھیں کہ آیا کوئی اور ہمسایہ چوٹی ہے جو ابھی تک نہیں دیکھی گئی ہے۔ اگر ہے تو، اس چوٹی پر جائیں اور پھر اس چوٹی سے شروع کریں اور اسی طرح کا دورہ کریں؛ اگر نہیں ہے تو، ایک اور قدم پیچھے ہٹیں اور تلاش کریں.
چوڑائی سے پہلے تلاش کرنے والا الگورتھم (انگریزی: Breadth-First-Search) ایک گرافک تلاش کرنے والا الگورتھم ہے۔ بساط سے ، بی ایف ایس درخت کے چوڑائی کے ساتھ ساتھ درخت کے چوڑائی کے ساتھ ساتھ درخت کے چوڑائی کے ساتھ شروع ہوتا ہے۔ اگر تمام نوڈس تک رسائی حاصل کی جاتی ہے تو ، الگورتھم کو روک دیا جاتا ہے۔ بی ایف ایس بھی اندھے تلاش میں شامل ہے۔ عام طور پر قطار کے اعداد و شمار کی ساخت کا استعمال کرتے ہوئے بی ایف ایس الگورتھم کو نافذ کرنے میں مدد ملتی ہے۔
الگورتھم کے اقدامات:
1، سب سے پہلے جڑ نوڈس کو قطار میں ڈالیں۔
2، قطار میں سے پہلا نوڈ نکالیں اور چیک کریں کہ آیا یہ ہدف ہے۔
اگر کوئی ہدف مل جاتا ہے تو ، تلاش ختم کریں اور نتائج واپس بھیجیں۔ دوسری صورت میں ، اس کے تمام براہ راست ذیلی نوڈس کو قطار میں شامل کریں جن کی جانچ نہیں کی گئی ہے۔
3، اگر قطار خالی ہے، تو اس کا مطلب یہ ہے کہ پورے گراف میں کوئی بھی نشانہ نہیں ہے جسے آپ تلاش کرنا چاہتے ہیں۔
4، مرحلہ 2 دہرائیں۔
ڈیکسٹرا الگورتھم (انگریزی: Dijkstra's Salgorithm) نیدر لینڈ کے کمپیوٹر سائنسدان ایزہر ڈیکسٹرا نے پیش کیا تھا۔ ڈیکسٹرا کا الگورتھم وسیع ترجیحی تلاش کا استعمال کرتا ہے تاکہ غیر منفی اختیار والے گراف کے واحد ذریعہ کا سب سے مختصر راستہ حل کیا جاسکے ، جس کے نتیجے میں ایک مختصر ترین راستہ درخت مل جاتا ہے۔ یہ الگورتھم عام طور پر روٹنگ الگورتھم میں استعمال ہوتا ہے یا دوسرے گراف کے الگورتھم کے ایک ذیلی ماڈیول کے طور پر۔
اس الگورتھم کی ان پٹ میں ایک وزن والے متوجہ گراف G، اور G میں ایک ماخذ چوٹی S شامل ہے۔ ہم V کو G میں تمام چوٹیوں کا مجموعہ کہتے ہیں۔ ہر گراف کے اطراف ، دو چوٹیوں کے ذریعہ تشکیل دیئے گئے ترتیب والے عناصر کا جوڑا ہے۔ ((u ، v) کا مطلب ہے کہ چوٹی u سے v تک راستے منسلک ہیں۔ ہم E کو G میں تمام اطراف کا مجموعہ کہتے ہیں ، اور اطراف کا وزن وزن کے ذریعہ بیان کیا جاتا ہے: w: E → [0, ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
لہذا ، w ((u ، v) چوٹی u سے چوٹی v تک غیر منفی وزن ((weight) ہے ؛ جس طرف کا وزن دو چوٹیوں کے درمیان فاصلہ کے طور پر تصور کیا جاسکتا ہے۔ جہاں تک دو نکاتی راستے کا وزن ہے ، اس راستے پر تمام اطراف کے وزن کا مجموعہ ہے۔ جہاں V میں چوٹی s اور t ہیں ، ڈیجسٹرا الگورتھم s سے t تک کم سے کم وزن والے راستے تلاش کرتا ہے۔ مثال کے طور پر ، مختصر ترین راستہ) ؛ یہ الگورتھم ایک گراف میں ایک چوٹی s سے کسی دوسرے چوٹی تک کا سب سے مختصر راستہ بھی تلاش کرسکتا ہے۔ غیر منفی اختیارات والے سمتل گراف کے لئے ، ڈیجسٹرا الگورتھم فی الحال سب سے تیز واحد ذریعہ کا سب سے مختصر راستہ ہے جو معلوم ہے۔
الگورتھم کے اقدامات:
1، ابتدائی وقت S = {V0}، T = {باقی چوٹیوں}، T میں چوٹیوں کے مساوی فاصلے کی قدر
اگر
2، T میں سے ایک چوٹی منتخب کریں جس کا فاصلہ کم سے کم ہے W اور S میں نہیں ہے، اور S کو شامل کریں
3، باقی T میں چوٹیوں کے فاصلے کی قدر میں ترمیم: اگر W کو وسط چوٹی کے طور پر شامل کیا جائے اور V0 سے Vi تک فاصلے کی قدر کو کم کیا جائے تو اس فاصلے کی قدر میں ترمیم کی جائے۔
مندرجہ بالا مرحلہ 2 یا 3 کو دہرائیں، جب تک کہ S میں تمام چوٹیوں کو شامل نہیں کیا جاتا ہے، یعنی W = Vi
متحرک پروگرامنگ (انگریزی: Dynamic programming) ریاضی، کمپیوٹر سائنس اور معاشیات میں استعمال ہونے والا ایک طریقہ ہے جس میں پیچیدہ مسائل کو حل کرنے کے لئے بنیادی مسائل کو نسبتا simple آسان ذیلی مسائل میں تقسیم کرنے کا طریقہ استعمال کیا جاتا ہے۔ متحرک پروگرامنگ اکثر اوورلیپ ذیلی مسائل اور زیادہ سے زیادہ ذیلی ساخت کی خصوصیات والے مسائل کے لئے استعمال ہوتی ہے ، متحرک پروگرامنگ کا طریقہ سادہ حل سے کہیں زیادہ کم وقت لگتا ہے۔
متحرک منصوبہ بندی کے پیچھے بنیادی خیال بہت آسان ہے۔ عام طور پر ، کسی دیئے گئے مسئلے کو حل کرنے کے ل we ، ہمیں اس کے مختلف حصوں کو حل کرنے کی ضرورت ہوتی ہے (بچوں کے مسائل) ، اور اس کے حل کو دوبارہ جوڑنے کے لئے سبسکرائب کریں۔ عام طور پر ، بہت سے سبسکرائب مسائل بہت ملتے جلتے ہیں ، لہذا متحرک منصوبہ بندی کا طریقہ کار ہر سبسکرائب کو صرف ایک بار حل کرنے کی کوشش کرتا ہے ، جس سے حساب کتاب کی مقدار کم ہوجاتی ہے۔ ایک بار جب کسی دیئے گئے سبسکرائب کا حل حل ہوجائے تو ، اس کا میموری اسٹوریج کیا جاتا ہے ، تاکہ اگلی بار جب کسی کو اسی طرح کے مسئلے کو حل کرنے کی ضرورت ہو تو براہ راست جانچ پڑتال کی جاسکے۔ یہ عمل خاص طور پر مفید ہے جب بار بار چلنے والے سبسکرائب مسائل کی تعداد ان پٹ کے سائز کے بارے میں اشاریہ میں بڑھ رہی ہے۔
اس کے بارے میں سب سے زیادہ کلاسیکی سوالات میں سے ایک ہے: کیا آپ کے پاس ایک بیگ ہے؟
الگورتھم کے اقدامات:
1، سب سے زیادہ مثالی ساخت کی خصوصیات۔ اگر کسی مسئلے کے سب سے زیادہ مثالی حل میں شامل سب سے زیادہ مثالی حل بھی موجود ہے تو ہم کہتے ہیں کہ اس مسئلے میں سب سے زیادہ مثالی ساخت کی خصوصیات ہیں (یعنی زیادہ سے زیادہ اصلاح کے اصول کو پورا کرتی ہے۔) ۔ سب سے زیادہ مثالی ساخت کی خصوصیات متحرک منصوبہ بندی کے الگورتھم کے مسئلے کو حل کرنے کے لئے اہم اشارے فراہم کرتی ہیں۔
2، ذیلی مسائل کی اوورلیپنگ۔ ذیلی مسائل کی اوورلیپنگ کا مطلب یہ ہے کہ جب ایک بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار بار حساب لگایا جاتا ہے۔ متحرک منصوبہ بندی الگورتھم اس طرح کے ذیلی مسائل کی اوورلیپنگ کی نوعیت سے فائدہ اٹھاتا ہے ، ہر ذیلی مسئلے پر صرف ایک بار حساب لگاتا ہے ، اور پھر اس کے حساب کے نتائج کو ایک جدول میں محفوظ کرتا ہے ، جب دوبارہ حساب کتاب کرنے کی ضرورت ہوتی ہے تو ، صرف جدول میں نتائج کو دیکھنا آسان ہے ، تاکہ اعلی کارکردگی حاصل کی جاسکے۔
بے مثال بے مثال درجہ بندی الگورتھم ایک سادہ احتمال کی درجہ بندی الگورتھم ہے جو بیجسٹ تھیورم پر مبنی ہے۔ بیجسٹ درجہ بندی کی بنیاد احتمال کی استدلال ہے ، یعنی یہ کہ مختلف شرائط کا وجود غیر یقینی ہے ، اور صرف اس صورت میں کہ ان کے امکانات موجود ہیں۔ احتمال کی دلیل یقینیت کی دلیل کے مترادف ہے۔ جبکہ بے مثال بیجسٹ درجہ بندی آزاد مفروضے پر مبنی ہے ، یعنی یہ فرض کرتے ہوئے کہ نمونہ میں ہر خصوصیت دیگر خصوصیات سے متعلق نہیں ہے۔
سادہ بیزوس درجہ بندی کرنے والے صحت مند قدرتی امکانات کے ماڈل پر انحصار کرتے ہیں اور نگرانی سیکھنے والے نمونے کے مجموعوں میں بہت اچھے درجہ بندی کے نتائج حاصل کرتے ہیں۔ بہت سے عملی ایپلی کیشنز میں ، سادہ بیزوس ماڈل کے پیرامیٹرز کا تخمینہ زیادہ سے زیادہ مماثلت کا تخمینہ استعمال کرتے ہوئے کیا جاتا ہے ، یعنی سادہ بیزوس ماڈل کام کرتا ہے اور بیزوس امکانات یا کسی بھی بیزوس ماڈل کا استعمال نہیں کرتا ہے۔
ان سادہ خیالات اور بہت زیادہ آسان مفروضوں کے باوجود ، سادہ بیزس درجہ بندی بہت ساری پیچیدہ حقیقتوں میں کافی حد تک کام کرتی ہے۔