درج ذیل نمبروں پر غور کریں:
50 60 30 10 80 70 20 40
اگر اس فہرست کو صعودی ترتیب میں ترتیب دیا جائے تو یہ ہوگا:
10 20 30 40 50 60 70 80
اگر اسے نزولی ترتیب میں ترتیب دیا جائے تو یہ ہوگا:
80 70 60 50 40 30 20 10
اندراج کی ترتیب ایک ترتیب دینے والا الگورتھم ہے جو فہرست کو صعودی ترتیب میں یا نزولی ترتیب میں ترتیب دینے کے لیے استعمال ہوتا ہے۔ یہ مضمون صرف صعودی ترتیب میں ترتیب دینے سے متعلق ہے۔ نزولی ترتیب میں ترتیب دینا اس دستاویز میں دی گئی اسی منطق کی پیروی کرتا ہے۔ اس مضمون کا مقصد اندراج کی ترتیب کی وضاحت کرنا ہے۔ پروگرامنگ مندرجہ ذیل مثال میں C میں کی گئی ہے۔ اندراج کی ترتیب کی وضاحت یہاں ایک صف کا استعمال کرتے ہوئے کی گئی ہے۔
اندراج کی ترتیب کے لیے الگورتھم
ایک غیر ترتیب شدہ فہرست دی گئی ہے۔ مقصد اسی فہرست کا استعمال کرتے ہوئے فہرست کو صعودی ترتیب میں ترتیب دینا ہے۔ ایک ہی صف کا استعمال کرتے ہوئے غیر ترتیب شدہ صف کو ترتیب دینا جگہ جگہ چھانٹنا کہا جاتا ہے۔ زیرو بیسڈ انڈیکسنگ یہاں استعمال ہوتی ہے۔ اقدامات درج ذیل ہیں:
-
- فہرست کو شروع سے اسکین کیا جاتا ہے۔
- اسکیننگ کے دوران، اس کے پیشرو سے کم کسی بھی نمبر کو اس کے پیشرو کے ساتھ تبدیل کیا جاتا ہے۔
- یہ تبادلہ فہرست کے ساتھ ساتھ جاری رہتا ہے، جب تک کہ اسے تبدیل کرنا ممکن نہ ہو۔
- جب سکیننگ اختتام کو پہنچ جاتی ہے، چھانٹنا مکمل ہو جاتا ہے۔
اندراج ترتیب کی مثال
وقت کی پیچیدگی سے نمٹتے وقت، یہ بدترین صورت ہے جسے عام طور پر مدنظر رکھا جاتا ہے۔ پچھلی فہرست کے لیے بدترین ترتیب یہ ہے:
80 70 60 50 40 30 20 10
صفر سے 7 تک اشاریہ جات کے ساتھ آٹھ عناصر ہیں۔
انڈیکس صفر پر، سکیننگ 80 پر جاتی ہے۔ یہ ایک حرکت ہے۔ یہ ایک تحریک ایک آپریشن ہے۔ اب تک کل ایک آپریشن ہے (ایک حرکت، کوئی موازنہ، اور کوئی تبادلہ نہیں)۔ نتیجہ یہ ہے:
| 80 70 60 50 40 30 20 10
انڈیکس ون میں، 70 کی حرکت ہوتی ہے۔ 70 کا 80 کے ساتھ موازنہ کیا جاتا ہے۔ 70 اور 80 کو تبدیل کیا جاتا ہے۔ ایک تحریک ایک آپریشن ہے۔ ایک موازنہ بھی ایک آپریشن ہے۔ ایک تبادلہ بھی ایک آپریشن ہے۔ یہ سیکشن تین آپریشن فراہم کرتا ہے۔ اب تک کل چار آپریشنز ہو چکے ہیں (1 + 3 = 4)۔ نتیجہ حسب ذیل ہے:
70 | 80 60 50 40 30 20 10
انڈیکس ٹو میں، 60 کی حرکت ہوتی ہے۔ 60 کا 80 سے موازنہ کیا جاتا ہے، پھر 60 اور 80 کو تبدیل کیا جاتا ہے۔ 60 کا موازنہ 70 سے کیا جاتا ہے، پھر 60 اور 70 کو تبدیل کیا جاتا ہے۔ ایک تحریک ایک آپریشن ہے۔ دو موازنہ دو آپریشن ہیں۔ دو تبادلہ دو آپریشن ہیں۔ یہ سیکشن پانچ آپریشن فراہم کرتا ہے۔ اب تک کل نو آپریشنز ہو چکے ہیں (4 + 5 = 9)۔ نتیجہ حسب ذیل ہے:
60 70 | 80 50 40 30 20 10
انڈیکس تھری میں، 50 کی حرکت ہوتی ہے۔ 50 کا 80 سے موازنہ کیا جاتا ہے، پھر 50 اور 80 کو تبدیل کیا جاتا ہے۔ 50 کا موازنہ 70 سے کیا جاتا ہے، پھر 50 اور 70 کو تبدیل کیا جاتا ہے۔ 50 کا موازنہ 60 سے کیا جاتا ہے، پھر 50 اور 60 کو تبدیل کیا جاتا ہے۔ ایک تحریک ایک آپریشن ہے۔ تین موازنہ تین آپریشن ہیں۔ تین ادل بدل تین آپریشن ہیں۔ یہ سیکشن سات آپریشن فراہم کرتا ہے۔ اب تک کل سولہ آپریشنز ہو چکے ہیں (9 + 7 = 16)۔ نتیجہ حسب ذیل ہے:
50 60 70 | 80 40 30 20 10
انڈیکس فور پر، 40 کی حرکت ہوتی ہے۔ 40 کا 80 سے موازنہ کیا جاتا ہے، پھر 40 اور 80 کو تبدیل کیا جاتا ہے۔ 40 کا موازنہ 70 سے کیا جاتا ہے، پھر 40 اور 70 کو تبدیل کیا جاتا ہے۔ 40 کا موازنہ 60 سے کیا جاتا ہے، پھر 40 اور 60 کو تبدیل کیا جاتا ہے۔ 40 کا موازنہ 50 سے کیا جاتا ہے، پھر 40 اور 50 کو تبدیل کیا جاتا ہے۔ ایک تحریک ایک آپریشن ہے۔ چار موازنہ چار آپریشن ہیں۔ چار سویپ چار آپریشن ہیں۔ یہ سیکشن نو آپریشن فراہم کرتا ہے۔ اب تک کل پچیس آپریشنز ہو چکے ہیں (16 + 9 = 25)۔ نتیجہ حسب ذیل ہے:
40 50 60 70 80 | 30 20 10
انڈیکس پانچ میں، 30 کی حرکت ہوتی ہے۔ 30 کا 80 سے موازنہ کیا جاتا ہے، پھر 30 اور 80 کو تبدیل کیا جاتا ہے۔ 30 کا موازنہ 70 سے کیا جاتا ہے، پھر 30 اور 70 کو تبدیل کیا جاتا ہے۔ 30 کا 60 سے موازنہ کیا جاتا ہے، پھر 30 اور 60 کو تبدیل کیا جاتا ہے۔ 30 کا 50 سے موازنہ کیا جاتا ہے، پھر 30 اور 50 کو تبدیل کیا جاتا ہے۔ 30 کا موازنہ 40 سے کیا جاتا ہے، پھر 30 اور 40 کو تبدیل کیا جاتا ہے۔ ایک تحریک ایک آپریشن ہے۔ پانچ موازنہ پانچ آپریشن ہیں۔ پانچ تبادلہ پانچ آپریشن ہیں۔ یہ سیکشن گیارہ آپریشنز فراہم کرتا ہے۔ اب تک کل چھتیس آپریشنز ہو چکے ہیں (25 + 11 = 36)۔ نتیجہ حسب ذیل ہے:
30 40 50 60 70 80 | 20 10
انڈیکس چھ میں، 20 کی حرکت ہوتی ہے۔ 20 کا 80 سے موازنہ کیا جاتا ہے، پھر 20 اور 80 کو تبدیل کیا جاتا ہے۔ 20 کا موازنہ 70 سے کیا جاتا ہے، پھر 20 اور 70 کو تبدیل کیا جاتا ہے۔ 20 کا موازنہ 60 سے کیا جاتا ہے، پھر 20 اور 60 کو تبدیل کیا جاتا ہے۔ 20 کا موازنہ 50 سے کیا جاتا ہے، پھر 20 اور 50 کو تبدیل کیا جاتا ہے۔ 20 کا موازنہ 40 سے کیا جاتا ہے، پھر 20 اور 40 کو تبدیل کیا جاتا ہے۔ 20 کا موازنہ 30 سے کیا جاتا ہے، پھر 20 اور 30 کو تبدیل کیا جاتا ہے۔ ایک تحریک ایک آپریشن ہے۔ چھ موازنہ چھ آپریشنز ہیں۔ چھ تبادلہ چھ آپریشن ہیں۔ یہ سیکشن تیرہ آپریشنز فراہم کرتا ہے۔ اب تک کل انتالیس آپریشنز ہو چکے ہیں (36+13=49)۔ نتیجہ حسب ذیل ہے:
20 30 40 50 60 70 80 | 10
انڈیکس سات میں، 10 کی حرکت ہوتی ہے۔ 10 کا 80 سے موازنہ کیا جاتا ہے، پھر 10 اور 80 کو تبدیل کیا جاتا ہے۔ 10 کا موازنہ 70 سے کیا جاتا ہے، پھر 10 اور 70 کو تبدیل کیا جاتا ہے۔ 10 کا موازنہ 60 سے کیا جاتا ہے، پھر 10 اور 60 کو تبدیل کیا جاتا ہے۔ 10 کا موازنہ 50 سے کیا جاتا ہے، پھر 10 اور 50 کو تبدیل کیا جاتا ہے۔ 10 کا موازنہ 30 سے کیا جاتا ہے، پھر 10 اور 40 کو تبدیل کیا جاتا ہے۔ 10 کا موازنہ 30 سے کیا جاتا ہے، پھر 10 اور 30 کو تبدیل کیا جاتا ہے۔ 10 کا موازنہ 20 سے کیا جاتا ہے، پھر 10 اور 20 کو تبدیل کیا جاتا ہے۔ ایک تحریک ایک آپریشن ہے۔ سات موازنہ سات آپریشنز ہیں۔ سات ادل بدل سات آپریشن ہیں۔ یہ سیکشن پندرہ آپریشن فراہم کرتا ہے۔ اب تک کل چونسٹھ آپریشنز ہو چکے ہیں (49+15=64)۔ نتیجہ حسب ذیل ہے:
10 20 30 40 50 60 70 80 10 |
کام ہو گیا! 64 آپریشنز شامل تھے۔
64 = 8 x 8 = 8 دو
اندراج کی ترتیب کے لیے وقت کی پیچیدگی
اگر اندراج کی ترتیب کے ساتھ ترتیب دینے کے لیے n عناصر موجود ہیں، تو ممکنہ کارروائیوں کی زیادہ سے زیادہ تعداد n2 ہوگی، جیسا کہ پہلے دکھایا گیا ہے۔ داخل کرنے کی ترتیب کے وقت کی پیچیدگی یہ ہے:
O(n دو )
یہ Big-O اشارے کا استعمال کرتا ہے۔ بگ-O اشارے بڑے حروف میں O سے شروع ہوتا ہے، اس کے بعد قوسین ہوتا ہے۔ قوسین کے اندر آپریشنز کی زیادہ سے زیادہ ممکنہ تعداد کا اظہار ہے۔
سی میں کوڈنگ
اسکین کے بالکل شروع میں، پہلا عنصر اپنی پوزیشن کو تبدیل نہیں کر سکتا۔ پروگرام بنیادی طور پر درج ذیل ہے:
# شامل کریںباطل اندراج کی ترتیب ( int A [ ] int N ) {
کے لیے ( int میں = 0 ; میں < ن; i++ ) {
int j = i؛
جبکہ ( اے [ جے ] < اے [ j- 1 ] && j- 1 > = 0 ) {
int temp = A [ جے ] ; اے [ جے ] = اے [ j- 1 ] ; اے [ j- 1 ] = درجہ حرارت؛ // تبادلہ
j--;
}
}
}
insertionSort() فنکشن کی تعریف الگورتھم کا استعمال کرتی ہے جیسا کہ بیان کیا گیا ہے۔ دوران لوپ کی شرائط کو نوٹ کریں۔ اس پروگرام کے لیے ایک مناسب C مین فنکشن یہ ہے:
{
int n = 8 ;
int A [ ] = { پچاس , 60 , 30 , 10 , 80 , 70 , بیس , 40 } ;
insertionSort ( ایک ) ;
کے لیے ( int میں = 0 ; میں < n i++ ) {
printf ( '٪میں ' ، اے [ میں ] ) ;
}
printf ( ' \n ' ) ;
واپسی 0 ;
}
نتیجہ
اندراج کی ترتیب کے لیے وقت کی پیچیدگی اس طرح دی گئی ہے:
O(n دو )
قارئین نے بدترین کیس ٹائم پیچیدگی، اوسط کیس ٹائم پیچیدگی اور بہترین کیس ٹائم پیچیدگی کے بارے میں سنا ہوگا۔ اندراج کی ترتیب کے وقت کی پیچیدگی کے ان تغیرات پر ہماری ویب سائٹ کے اگلے مضمون میں بحث کی گئی ہے۔