فوری ترتیب اور ضم شدہ ترتیب کے مابین فرق
مواد
فوری ترتیب اور انضمام کی ترتیب الگورتھم تقسیم اور فتح الگورتھم پر مبنی ہیں جو بالکل اسی طرح کام کرتا ہے۔ فوری اور انضمام کی ترتیب کے مابین پہلے فرق یہ ہے کہ فوری ترتیب میں محور عنصر کو چھانٹ رہا ہے۔ دوسری طرف ، انضمام کی ترتیب چھانٹ رہا ہے کے لئے محور عنصر کا استعمال نہیں کرتی ہے۔
چھانٹنے کی دونوں تکنیک ، کوئیک سورسٹ اور انضمام کی ترتیب تقسیم اور فتح کے طریقہ کار پر استوار ہوتی ہے جس میں عناصر کا سیٹ تقسیم ہوجاتا ہے اور پھر انضمام کے بعد مل جاتا ہے۔ فوری ترتیب میں عنصروں کا ایک بڑا مجموعہ چھانٹنے کے لئے انضمام کی ترتیب سے زیادہ موازنہ کی ضرورت ہوتی ہے۔
-
- موازنہ چارٹ
- تعریف
- کلیدی اختلافات
- نتیجہ اخذ کرنا
موازنہ چارٹ
| موازنہ کی بنیاد | فوری ترتیب | ترتیب دیں ضم کریں |
|---|---|---|
| صف میں موجود عناصر کی تقسیم | عناصر کی فہرست کی تقسیم لازمی طور پر نصف میں تقسیم نہیں کی جاتی ہے۔ | سرنی کو ہمیشہ نصف (n / 2) میں تقسیم کیا جاتا ہے۔ |
| معاملے کی بدترین پیچیدگی | O (n)2) | O (n لاگ این) |
| اچھی طرح سے کام کرتا ہے | چھوٹی چھوٹی سرنی | کسی بھی قسم کی صف میں ٹھیک کام کرتی ہے۔ |
| سپیڈ | چھوٹے ڈیٹا سیٹ کے ل for دوسرے چھنٹائی کرنے والے الگورتھم سے بھی تیز تر۔ | ہر طرح کے ڈیٹا سیٹ میں مستقل رفتار۔ |
| ذخیرہ کرنے کی اضافی ضرورت | کم | مزید |
| کارکردگی | بڑی صفوں کے ل In ناکافی۔ | زیادہ موثر |
| ترتیب دینے کا طریقہ | اندرونی | بیرونی |
فوری ترتیب کی تعریف
فوری ترتیب الگورتھم کو چھانٹنے کے لئے وسیع پیمانے پر استعمال کیا جاتا ہے کیونکہ مختصر صفوں کے ل fast یہ تیز ہے۔ عناصر کا سیٹ بار بار حصوں میں تقسیم ہوتا ہے جب تک کہ اس کو مزید تقسیم کرنا ممکن نہ ہو۔ فوری ترتیب کو بھی جانا جاتا ہے تقسیم تبادلہ کی طرح. یہ عناصر کو تقسیم کرنے کے لئے ایک کلیدی عنصر (محور کے نام سے جانا جاتا ہے) استعمال کرتا ہے۔ ایک تقسیم میں وہ عنصر ہوتے ہیں جو کلیدی عنصر سے چھوٹے ہوتے ہیں۔ ایک اور تقسیم میں وہ عناصر شامل ہیں جو کلیدی عنصر سے زیادہ ہیں۔ عناصر کو بار بار ترتیب دیا جاتا ہے۔
فرض کریں کہ A ایک صف ہے A، A، A، …… ..، A جو نمبر ہے جس کو ترتیب دینا ہے۔ فوری ترتیب الگورتھم مندرجہ ذیل مراحل پر مشتمل ہے۔
- پہلا عنصر یا کوئی بھی بے ترتیب عنصر جس کی کلید منتخب ہوتی ہے ، کلید = A (1) فرض کریں۔
- دوسرے مقام پر "کم" پوائنٹر رکھا گیا ہے اور "اوپر" پوائنٹر سرنی کے آخری عنصر پر رکھا گیا ہے ، یعنی کم = 2 اور اس سے اوپر = n؛
- مستقل طور پر ، "کم" پوائنٹر کو ایک پوزیشن کے ذریعہ (A> کلید) تک بڑھاو۔
- مستقل طور پر ، جب تک (A <= key) تک ایک پوزیشن کے ذریعہ "اپ" پوائنٹر کم ہوجائے۔
- اگر اپ A کے ساتھ کم تبادلہ A سے زیادہ ہے۔
- مرحلہ 3،4 ، اور 5 کو دہرائیں جب تک کہ مرحلہ 5 کی حالت ناکام ہوجائے (یعنی اوپر <= کم) پھر کلید کے ساتھ A کا تبادلہ کریں۔
- اگر کلید کے بائیں عناصر کلید سے چھوٹے ہیں اور کلید کے دائیں عناصر کلید سے زیادہ ہیں تو پھر سرنی دو ذیلی صفوں میں تقسیم ہوجاتی ہے۔
- مذکورہ بالا طریقہ کار بار بار subarrays پر لاگو ہوتا ہے جب تک کہ پوری صف کو ترتیب نہیں دیا جاتا۔
فوائد اور نقصانات
اس میں اوسط کیس کا اچھا سلوک ہے۔ تیز رفتار ترتیب سے چلنے والے وقت کی پیچیدگی اچھی ہے جو یہ الگورتھم جیسے تیز بلبلوں ، اضافے کی ترتیب اور انتخاب کی ترتیب سے تیز ہے۔ تاہم ، یہ پیچیدہ اور بہت تکرار بخش ہے ، یہی وجہ ہے کہ یہ بڑی صفوں کے ل suitable موزوں نہیں ہے۔
ضم شدہ ترتیب کی تعریف
ترتیب دیں ضم کریں ایک بیرونی الگورتھم ہے جو تقسیم اور فتح کی حکمت عملی پر بھی مبنی ہے۔ جب تک صرف ایک عنصر باقی نہ رہ جاتا ہو ، عناصر کو بار بار ذیلی ارا (N / 2) میں تقسیم کیا جاتا ہے ، جس سے چھنٹائی کے وقت میں نمایاں کمی واقع ہوتی ہے۔ اس سے متعلق معاون صف کو ذخیرہ کرنے کے لئے اضافی ذخیرہ استعمال ہوتا ہے۔ مرج ترتیب میں تین آریوں کا استعمال ہوتا ہے جہاں ہر ایک آدھے حصے کو ذخیرہ کرنے کے لئے استعمال کیا جاتا ہے ، اور تیسری ترتیب آخری ترتیب شدہ فہرست کو محفوظ کرنے کے لئے استعمال ہوتی ہے۔ پھر ہر صف کو بار بار ترتیب دیا جاتا ہے۔ آخر میں ، سبریوں کو ضم کیا جاتا ہے تاکہ اسے سرنی کا عنصر سائز بنایا جا.۔ فہرست کو ہمیشہ نصف حص nوں میں تقسیم کیا جاتا ہے (n / 2) فوری ترتیب دینے سے مختلف ہے۔
A ، A ، A ، ……… ، A. ترتیب دیئے جانے والے عناصر کی ایک بڑی تعداد کی صف بنائیں ، انضمام کی ترتیب دیئے گئے مراحل کی پیروی کرتی ہے۔
- A کے سرے A کو تقریبا n N / 2 کے مطابق ذیلی سرے میں 2 سے تقسیم کریں ، جس کا مطلب ہے کہ (A، A)، (A، A)، (A، A)، (A، A) ذیلی ارای میں موجود عناصر لازمی ہیں الگ الگ ترتیب میں رہیں۔
- سائز 4 کے چھانٹے والے سبباروں کی فہرست حاصل کرنے کے لئے ہر جوڑے کو جوڑیں۔ ماتحت علاقوں میں موجود عناصر بھی ترتیب کے مطابق ہیں ، (A ، A، A، A) ، …… ، (A، A، A، A)، …….، (A، A، A، A)
- مرحلہ 2 بار بار انجام دیا جاتا ہے یہاں تک کہ سائز n کی صرف ایک ترتیب شدہ صف موجود ہو۔
فوائد اور نقصانات
انضمام کی ترتیب الگورتھم چھانٹ inے میں شامل عناصر کی تعداد سے قطع نظر عین ویسا اور عین مطابق انداز میں انجام دیتا ہے۔ بڑے اعداد و شمار کے سیٹ کے باوجود بھی یہ ٹھیک کام کرتا ہے۔ تاہم ، یہ میموری کا بڑا حصہ کھاتا ہے۔
- انضمام کی طرح ، صف کو صرف دو حصوں میں تقسیم کرنا چاہئے (یعنی n / 2) اس کے برخلاف ، فوری ترتیب میں ، فہرست کو مساوی عناصر میں تقسیم کرنے کی کوئی مجبوری نہیں ہے۔
- فوری ترتیب دینے کی بدترین صورت پیچیدگی O (n) ہے2) کیونکہ یہ بدترین حالت میں بہت زیادہ موازنہ لیتا ہے۔ اس کے برعکس ، انضمام کی طرح ایک ہی بدترین کیس اور اوسط کیس کی پیچیدگیاں ہیں ، وہ ہے O (n log n)۔
- کسی بھی طرح کے ڈیٹا سیٹ پر مرج ترتیب بہتر طریقے سے چل سکتی ہے خواہ وہ بڑا ہو یا چھوٹا۔ اس کے برعکس ، فوری ترتیب دینے والے بڑے ڈیٹاسیٹس کے ساتھ اچھی طرح کام نہیں کرسکتے ہیں۔
- کچھ طرح کے معاملات میں جیسے چھوٹے ڈیٹا سیٹ کے لئے کوئیک سلائٹ انضمام کی ترتیب سے تیز تر ہے۔
- ضم کرنے کے لئے معاون صفوں کو ذخیرہ کرنے کے لئے اضافی میموری کی ضرورت ہوتی ہے۔ دوسری طرف ، فوری ترتیب میں اضافی اسٹوریج کے ل much زیادہ جگہ کی ضرورت نہیں ہوتی ہے۔
- ضم شدہ ترتیب فوری ترتیب سے کہیں زیادہ موثر ہے۔
- فوری ترتیب اندرونی ترتیب دینے کا طریقہ ہے جہاں ڈیٹا کو ترتیب دیا جانا ہے جس میں ایک وقت میں اہم میموری میں ایڈجسٹ کیا جاتا ہے۔ اس کے برعکس ، انضمام کی ترتیب بیرونی چھنٹائی کا طریقہ ہے جس میں ترتیب دینے والے ڈیٹا کو ایک ہی وقت میں میموری میں ایڈجسٹ نہیں کیا جاسکتا ہے اور کچھ کو معاون میموری میں رکھنا پڑتا ہے۔
نتیجہ اخذ کرنا
فوری ترتیب سے تیز تر مقدمات ہوتے ہیں لیکن کچھ حالتوں میں وہ غیر موثر ہے اور انضمام کی طرح موازنہ بھی بہت کرتا ہے۔ اگرچہ انضمام کی ترتیب کو کم موازنہ کرنے کی ضرورت ہے ، اضافی صفوں کو ذخیرہ کرنے کے لئے اسے 0 (n) کی اضافی میموری جگہ کی ضرورت ہے جبکہ فوری ترتیب میں O (log n) کی جگہ کی ضرورت ہے۔
