فہرست کا خانہ
- تعارف
- C++ میں ضم ترتیب کیا ہے؟
- تقسیم اور فتح کا نقطہ نظر
- ترتیب الگورتھم کو ضم کریں۔
- C++ میں انضمام کی ترتیب کا نفاذ
- نتیجہ
1. تعارف
کمپیوٹر سائنس میں ترتیب دینے والے الگورتھم ڈیٹا کو صعودی یا نزولی ترتیب میں ترتیب دینے کے لیے استعمال ہوتے ہیں۔ الگ الگ خصوصیات کے ساتھ متعدد چھانٹنے والے الگورتھم دستیاب ہیں۔ مرج ترتیب C++ میں ایک طریقہ ہے جو صفوں کو ترتیب دے سکتا ہے۔
2. C++ میں مرج کی ترتیب کیا ہے؟
مرج کی ترتیب تقسیم اور فتح کی تکنیک کا استعمال کرتی ہے جو ایک صف کے عناصر کو ترتیب دے سکتی ہے۔ یہ C++ میں عناصر کی فہرست کو بھی ترتیب دے سکتا ہے۔ یہ ان پٹ کو دو حصوں میں تقسیم کرتا ہے، ہر نصف کو آزادانہ طور پر ترتیب دیتا ہے، اور پھر انہیں صحیح ترتیب میں ضم کرتا ہے۔
3. تقسیم اور فتح کا نقطہ نظر
چھانٹنے والا الگورتھم تقسیم اور فتح کی حکمت عملی کا اطلاق کرتا ہے، جس میں ان پٹ سرنی کو چھوٹے ذیلی ریزوں میں تقسیم کرنا، انہیں الگ سے حل کرنا، اور پھر ترتیب شدہ آؤٹ پٹ پیدا کرنے کے لیے نتائج کو ضم کرنا شامل ہے۔ انضمام کی ترتیب کی صورت میں، صف کو بار بار دو حصوں میں تقسیم کیا جاتا ہے جب تک کہ ہر نصف میں صرف ایک عنصر باقی نہ رہ جائے۔
4. ترتیب الگورتھم کو ضم کریں۔
انضمام کی ترتیب الگورتھم دو اہم مراحل پر مشتمل ہے: تقسیم اور انضمام۔ اقدامات درج ذیل ہیں:
4.1 تقسیم کریں۔
ضم ترتیب الگورتھم ایک صف میں عناصر کو چھانٹنے کے لیے تقسیم اور فتح کی حکمت عملی کی پیروی کرتا ہے۔
- الگورتھم میں پہلا قدم صف کے عناصر کو چیک کرے گا۔ اگر یہ ایک عنصر پر مشتمل ہے، تو اسے پہلے سے ترتیب دیا گیا سمجھا جاتا ہے، اور الگورتھم بغیر کسی تبدیلی کے اسی صف کو لوٹائے گا۔
- اگر صف میں ایک سے زیادہ عنصر شامل ہیں تو الگورتھم اسے دو حصوں میں تقسیم کرنے کے لیے آگے بڑھتا ہے: بایاں نصف اور دائیں نصف۔
- انضمام کی ترتیب کا الگورتھم پھر سرنی کے بائیں اور دائیں حصوں پر بار بار لاگو ہوتا ہے، مؤثر طریقے سے انہیں چھوٹے ذیلی ریزوں میں تقسیم کرتا ہے اور انفرادی طور پر ترتیب دیتا ہے۔
- یہ تکراری عمل اس وقت تک جاری رہتا ہے جب تک کہ ذیلی ریزوں میں ہر ایک میں صرف ایک عنصر شامل نہ ہو (مرحلہ 1 کے مطابق)، اس مقام پر انہیں ایک حتمی، ترتیب شدہ آؤٹ پٹ سرنی بنانے کے لیے ضم کیا جا سکتا ہے۔
4.2 ضم کریں۔
اب ہم صفوں کو ضم کرنے کے اقدامات دیکھیں گے:
- انضمام کے الگورتھم کے پہلے مرحلے میں ایک خالی صف بنانا شامل ہے۔
- الگورتھم پھر ان پٹ سرنی کے بائیں اور دائیں حصوں کے پہلے عناصر کا موازنہ کرنے کے لیے آگے بڑھتا ہے۔
- دو عناصر میں سے چھوٹے کو نئی صف میں شامل کیا جاتا ہے اور پھر ان پٹ سرنی کے متعلقہ نصف سے ہٹا دیا جاتا ہے۔
- مرحلہ 2-3 پھر دہرایا جاتا ہے جب تک کہ ایک آدھا خالی نہ ہوجائے۔
- غیر خالی نصف میں کوئی بھی باقی عناصر پھر نئی صف میں شامل کیے جاتے ہیں۔
- نتیجہ خیز صف اب مکمل طور پر ترتیب دی گئی ہے اور انضمام کے الگورتھم کے حتمی آؤٹ پٹ کی نمائندگی کرتی ہے۔
5. C++ میں انضمام کی ترتیب کا نفاذ
C++ میں انضمام کی ترتیب کو نافذ کرنے کے لیے دو مختلف طریقے اپنائے جاتے ہیں۔ دونوں طریقوں کی وقتی پیچیدگی مساوی ہے، لیکن ان کے عارضی ذیلی ریزوں کا استعمال مختلف ہے۔
C++ میں انضمام کی ترتیب کا پہلا طریقہ دو عارضی ذیلی رے استعمال کرتا ہے، جبکہ دوسرا صرف ایک استعمال کرتا ہے۔ یہ بات قابل غور ہے کہ پہلے طریقہ میں دو عارضی ذیلی ریزوں کا کل سائز دوسرے طریقہ میں اصل صف کے سائز کے برابر ہے، اس لیے خلائی پیچیدگی مستقل رہتی ہے۔
طریقہ 1 - دو عارضی سبریوں کا استعمال
طریقہ 1 کا استعمال کرتے ہوئے C++ میں انضمام کی ترتیب کے لیے یہاں ایک مثالی پروگرام ہے، جو دو عارضی ذیلی ریز استعمال کرتا ہے:
# شامل کریںنام کی جگہ کا استعمال کرتے ہوئے std ;
باطل ضم ( int arr [ ] ، int l ، int m ، int r )
{
int n1 = m - l + 1 ;
int n2 = r - m ;
int ایل [ n1 ] ، آر [ n2 ] ;
کے لیے ( int میں = 0 ; میں < n1 ; میں ++ )
ایل [ میں ] = arr [ l + میں ] ;
کے لیے ( int جے = 0 ; جے < n2 ; جے ++ )
آر [ جے ] = arr [ m + 1 + جے ] ;
int میں = 0 ، جے = 0 ، ک = l ;
جبکہ ( میں < n1 && جے < n2 ) {
اگر ( ایل [ میں ] <= آر [ جے ] ) {
arr [ ک ] = ایل [ میں ] ;
میں ++
}
اور {
arr [ ک ] = آر [ جے ] ;
جے ++
}
ک ++
}
جبکہ ( میں < n1 ) {
arr [ ک ] = ایل [ میں ] ;
میں ++
ک ++
}
جبکہ ( جے < n2 ) {
arr [ ک ] = آر [ جے ] ;
جے ++
ک ++
}
}
باطل ضم کریں ( int arr [ ] ، int l ، int r )
{
اگر ( l < r ) {
int m = l + ( r - l ) / 2 ;
ضم کریں ( arr ، l ، m ) ;
ضم کریں ( arr ، m + 1 ، r ) ;
ضم ( arr ، l ، m ، r ) ;
}
}
int مرکزی ( )
{
int arr [ ] = { 12 ، گیارہ ، 13 ، 5 ، 6 ، 7 } ;
int arr_size = کا سائز ( arr ) / کا سائز ( arr [ 0 ] ) ;
cout << 'دی گئی صف ہے \n ' ;
کے لیے ( int میں = 0 ; میں < arr_size ; میں ++ )
cout << arr [ میں ] << ' ;
ضم کریں ( arr ، 0 ، arr_size - 1 ) ;
cout << ' \n ترتیب شدہ صف ہے۔ \n ' ;
کے لیے ( int میں = 0 ; میں < arr_size ; میں ++ )
cout << arr [ میں ] << ' ;
واپسی 0 ;
}
اس پروگرام میں، ضم کرنے کا فنکشن تین دلائل لیتا ہے arr، l، اور r، جو ترتیب دینے کے لیے ارے کی نمائندگی کرتا ہے اور ذیلی رے کے اشاریے دکھاتا ہے جسے ضم کرنے کی ضرورت ہے۔ فنکشن پہلے ضم ہونے والے دو ذیلی ریزوں کے سائز تلاش کرتا ہے، پھر ان ذیلی ریزوں کے عناصر کو ذخیرہ کرنے کے لیے دو عارضی ذیلی ریزیں L اور R بناتا ہے۔ یہ پھر L اور R میں عناصر کا موازنہ کرتا ہے اور انہیں اصل صف میں ضم کرتا ہے۔ arr صعودی ترتیب میں
تقسیم اور فتح کی تکنیک کو مرج سورٹ فنکشن کے ذریعے استعمال کیا جاتا ہے تاکہ سرنی کو بار بار دو حصوں میں تقسیم کیا جا سکے جب تک کہ ذیلی رے میں صرف ایک عنصر باقی نہ رہ جائے۔ اس کے بعد یہ دو ذیلی ریزوں کو ایک ترتیب شدہ ذیلی رے میں ضم کر دیتا ہے۔ فنکشن ذیلی ریزوں کو ضم کرتا رہتا ہے جب تک کہ یہ مکمل صف کو ترتیب نہ دے۔
مین فنکشن میں، ہم 6 عناصر کے ساتھ ایک array کی وضاحت کرتے ہیں اور اسے ترتیب دینے کے لیے mergeSort فنکشن کو کال کرتے ہیں۔ کوڈ کے آخر میں، ترتیب شدہ صف پرنٹ کی جاتی ہے۔
طریقہ 2 - ایک عارضی سبری کا استعمال
طریقہ 2 کا استعمال کرتے ہوئے C++ میں انضمام کی ترتیب کے لیے یہاں ایک مثالی پروگرام ہے، جو ایک عارضی ذیلی رے کا استعمال کرتا ہے:
# شامل کریںنام کی جگہ کا استعمال کرتے ہوئے std ;
باطل ضم ( int arr [ ] , int l , int m , int r )
{
int میں , جے , ک ;
int n1 = m - l + 1 ;
int n2 = r - m ;
// عارضی ذیلی ریز بنائیں
int ایل [ n1 ] , آر [ n2 ] ;
// ڈیٹا کو subarrays میں کاپی کریں۔
کے لیے ( میں = 0 ; میں < n1 ; میں ++ )
ایل [ میں ] = arr [ l + میں ] ;
کے لیے ( جے = 0 ; جے < n2 ; جے ++ )
آر [ جے ] = arr [ m + 1 + جے ] ;
// عارضی ذیلی ریزوں کو واپس اصل صف میں ضم کریں۔
میں = 0 ;
جے = 0 ;
ک = l ;
جبکہ ( میں < n1 && جے < n2 ) {
اگر ( ایل [ میں ] <= آر [ جے ] ) {
arr [ ک ] = ایل [ میں ] ;
میں ++
}
اور {
arr [ ک ] = آر [ جے ] ;
جے ++
}
ک ++
}
// L کے باقی عناصر کو کاپی کریں[]
جبکہ ( میں < n1 ) {
arr [ ک ] = ایل [ میں ] ;
میں ++
ک ++
}
// R[] کے باقی عناصر کو کاپی کریں
جبکہ ( جے < n2 ) {
arr [ ک ] = آر [ جے ] ;
جے ++
ک ++
}
}
باطل ضم کریں ( int arr [ ] , int l , int r )
{
اگر ( l < r ) {
int m = l + ( r - l ) / 2 ;
// بائیں اور دائیں حصوں کو بار بار ترتیب دیں۔
ضم کریں ( arr , l , m ) ;
ضم کریں ( arr , m + 1 , r ) ;
// دو ترتیب شدہ حصوں کو ضم کریں۔
ضم ( arr , l , m , r ) ;
}
}
int مرکزی ( )
{
int arr [ ] = { 12 , گیارہ , 13 , 5 , 6 , 7 } ;
int arr_size = کا سائز ( arr ) / کا سائز ( arr [ 0 ] ) ;
cout << 'دی گئی صف ہے \n ' ;
کے لیے ( int میں = 0 ; میں < arr_size ; میں ++ )
cout << arr [ میں ] << ' ;
ضم کریں ( arr , 0 , arr_size - 1 ) ;
cout << ' \n ترتیب شدہ صف ہے۔ \n ' ;
کے لیے ( int میں = 0 ; میں < arr_size ; میں ++ )
cout << arr [ میں ] << ' ;
واپسی 0 ;
}
یہ پروگرام پچھلے پروگرام کی طرح ہے، لیکن دو عارضی ذیلی اضلاع L اور R استعمال کرنے کے بجائے، یہ ایک واحد عارضی ذیلی ٹرم استعمال کرتا ہے۔ مرج فنکشن پہلے کی طرح کام کرتا ہے، لیکن ڈیٹا کو L اور R میں کاپی کرنے کے بجائے، اسے temp پر کاپی کرتا ہے۔ اس کے بعد یہ عارضی صف کے عناصر کو واپس میں ضم کر دیتا ہے۔ arr جو اصل صف ہے.
mergeSort فنکشن پہلے جیسا ہی ہے، سوائے اس کے کہ یہ عارضی ذیلی رے کو ذخیرہ کرنے کے لیے L اور R کی بجائے temp استعمال کرتا ہے۔
مین فنکشن میں، ہم 6 عناصر کے ساتھ ایک array کی وضاحت کرتے ہیں اور اسے ترتیب دینے کے لیے mergeSort فنکشن کو کال کرتے ہیں۔ کوڈ پر عمل درآمد اسکرین پر ترتیب شدہ صف کو پرنٹ کرکے ختم ہوتا ہے۔
نتیجہ
مرج سورٹ ایک الگورتھم ہے جو صف کے عناصر کو ترتیب دیتا ہے، اور یہ تقسیم اور فتح کی تکنیک کا استعمال کرتا ہے اور عناصر کے درمیان موازنہ کرتا ہے۔ C++ میں ضم ہونے والی ترتیب میں O(n log n) کی وقتی پیچیدگی ہوتی ہے اور یہ خاص طور پر بڑی صفوں کو چھانٹنے کے لیے موثر ہے۔ اگرچہ ضم شدہ ذیلی ریزوں کو ذخیرہ کرنے کے لیے اسے اضافی میموری کی ضرورت ہوتی ہے، لیکن اس کا استحکام اسے چھانٹنے کے لیے ایک مقبول انتخاب بناتا ہے۔