جاوا میں اندراج کی ترتیب

صفوں کو چھانٹنا سب سے عام کاموں میں سے ایک ہے جو جاوا کے ابتدائیہ کو معلوم ہونا چاہیے کہ اسے کیسے کرنا ہے۔ اگرچہ arrays ہمیشہ ڈیٹا کو ترتیب دینے کا سب سے آسان طریقہ نہیں ہوتا ہے اور یہ زیادہ تر چھوٹی تعداد پر لاگو ہوتا ہے، لیکن ارے چھانٹنے کے پیچھے تصور پیچیدہ سافٹ ویئر اور ڈیٹا سائنس میں بہت ساری ایپلی کیشنز رکھتا ہے۔ اس پوسٹ میں، ہم اس بات کا بغور جائزہ لیں گے کہ اندراج کی ترتیب کیا ہے۔ ہم نے کچھ مثالیں اور مشق کے مسائل شامل کیے ہیں تاکہ آپ کو اس تصور کو مکمل طور پر سمجھنے میں مدد ملے۔

اندراج کی ترتیب کیا ہے؟

بنیادی طور پر، اندراج کی ترتیب ایک الگورتھم ہے جسے ڈویلپر چھوٹے نمبروں کے تاروں کو منظم کرنے کے لیے استعمال کرتے ہیں۔ یہ تمام اقدار کو دو ڈھیروں میں تقسیم کرتا ہے - ایک ترتیب شدہ اور ایک غیر ترتیب شدہ۔ ایک ایک کرکے، "غیر ترتیب شدہ" اسٹیک میں نمبروں کو نکال کر صحیح ترتیب میں رکھا جاتا ہے۔ آئیے اندراج کی ترتیب کے ان پٹ اور آؤٹ پٹ کو قریب سے دیکھتے ہیں:

• ان پٹ: غیر ترتیب شدہ عددی عناصر کے ساتھ ایک صف A: A[0,1, n, n-2...]۔
• آؤٹ پٹ: ایک صف جس میں ایک جیسے نمبر ہوں لیکن مکمل طور پر ترتیب دی گئی ہو۔ اسے عام طور پر B: B[0]B[1]...B[n-1] کہا جاتا ہے۔

اندراج کی ترتیب کو استعمال کرنے کے مٹھی بھر طریقے ہیں - یہاں سب سے زیادہ مقبول ہیں:

• عددی ترتیب (بڑھتی ہوئی ترتیب): [1، 2، 3، 4، 5]
• عددی چھانٹی (گھٹتی ہوئی ترتیب): [5، 4، 3، 2، 1]
• حروف تہجی کی ترتیب: [a, b, c, d]

نوٹ: اگر آپ کے پاس خالی صف یا سنگلٹن ہے، تو ان کو بطور ڈیفالٹ ترتیب دیا جاتا ہے۔

نظریہ اندراج کی ترتیب کو سمجھنا

اندراج کی ترتیب کے پیچھے کوڈ کو دریافت کرنے سے پہلے، آئیے غیر تکنیکی زبان کا استعمال کرتے ہوئے الگورتھم کو توڑ دیں۔ چونکہ ہم صعودی ترتیب میں ترتیب دینے کے لیے کوڈ دکھا رہے ہیں، اس لیے اس پوسٹ میں الگورتھم کی مرحلہ وار وضاحت کرنا سمجھ میں آتا ہے۔ مرحلہ 1۔ عددی قدر عام طور پر 10 سے کم کہاں arr[1]اور arr[n]کہاں کے درمیان تکرار کرنا ۔ مرحلہ 2۔ طریقہ کا استعمال کرتے ہوئے ترتیب کے پچھلے نمبر سے آپ نے جس عنصر کا انتخاب کیا ہے (جسے کہا جاتا ہے) کا موازنہ کریں ۔ مرحلہ 3۔ اگر تمام عناصر اپنے جانشینوں سے چھوٹے ہیں، تو موازنہ کو دہرائیں جب تک کہ آپ کو کوئی بڑی قیمت نہ مل جائے۔ مرحلہ 4۔ ایک ترتیب شدہ ترتیب بنانے کے لیے ایک بڑی قدر والی ایک پوزیشن کو چھوٹی والی سے آگے تبدیل کریں۔ مرحلہ 5۔ اس عمل کو اس وقت تک دہرائیں جب تک کہ آپ کو حروف کی ترتیب نہ ملےnkeysort()

قدیم صفوں کو چھانٹنا

چونکہ الگورتھم جاوا کے سب سے آسان آپریشنز میں سے ایک ہے، یہاں تک کہ مکمل ابتدائی افراد کو بھی اسے لاگو کرنے میں زیادہ پریشانی نہیں ہونی چاہیے۔ ایک صف کو ترتیب دینے کے لیے یہاں ایک مرحلہ وار گائیڈ ہے۔

1. چھانٹنے کے لیے ایک صف کا اعلان کریں۔

شروع کرنے کے لیے، آئیے اقدار کا ایک سٹرنگ بنائیں جو ہم بعد میں جاوا کا استعمال کرتے ہوئے ڈسپلے کریں گے۔ اندراج کی ترتیب کو استعمال کرنے کے لیے، آپ کو ایک صف بنانے کی ضرورت ہے۔ اس کے لیے استعمال کریں۔int[]

int[] arrayA = {10, 14, 20, 30};

2. الگورتھم کو نافذ کرنے کے لیے sort_arr استعمال کریں۔

sort_arr طریقہ داخل کرنے کی ترتیب کو نافذ کرنے کے سب سے عام طریقوں میں سے ایک ہے۔ عملی طور پر، یہ اس طرح لگتا ہے:

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. ایک لوپ اور ایٹریٹر بنائیں

اندراج کی ترتیب کے الگورتھم میں لوپ کا استعمال کرتے ہوئے، ڈویلپرز کو ہر عنصر کے لیے منطق کو دہرانے کی ضرورت نہیں ہے۔ اگرچہ لوپس بنانا پیچیدہ معلوم ہوتا ہے، لیکن یہ کافی آسان ہے - یہاں ایک مثال ہے:

for(int i=0; i< sort_arr.length; ++i){

اب جب کہ آپ کے پاس ایک کام کرنے والا لوپ ہے، اب وقت آگیا ہے کہ ایک ایٹریٹر بنائیں جو تمام عناصر کو مطلوبہ ترتیب میں ترتیب دے گا۔ اب سے، ہم تکرار کرنے والے کو " j" کے طور پر حوالہ دیں گے۔

int j = i;

4. "وائل لوپ" بنانا

جب داخل کرنے کی ترتیب کی بات آتی ہے تو، ایک نئی، ترتیب شدہ صف کے لیے "جبکہ" لوپ ضروری ہے۔ اسے صعودی ترتیب کے اندراج کی ترتیب کے لیے ترتیب دینے کے لیے، ایک ڈویلپر کو دو شرائط کی تعمیل کرنے کی ضرورت ہے:

• j کو تفویض کردہ قدر 0 سے زیادہ ہونی چاہیے۔
• تفویض کردہ قدر انڈیکس j-1سے زیادہ ہونی چاہیے۔j

جیسے ہی جب لوپ میں دونوں حالات درست ہوں گے، صف کی کلیدی قدر jانڈیکس کے برابر ہو جائے گی۔

5. صف کو ترتیب دینا

آپ کے while لوپ سیٹ اپ کرنے کے بعد، jاور j-1ویلیوز کو تب تک تبدیل کر دیا جائے گا جب تک کہ while لوپ میں ایک یا دونوں شرائط ناکام نہ ہو جائیں۔ اسی طرح، for loop میں ہر قدر کے لیے چھانٹی کو دہرایا جائے گا جب تک کہ for-loop حالات بھی ناکام نہ ہو جائیں۔ یہاں یہ ہے کہ داخل کرنے کی ترتیب کا عمل عملی طور پر کیسے کام کرتا ہے:

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

ایک ArrayList کو ترتیب دینا

اگرچہ داخل کرنے کی ترتیب کے پیچھے ریاضی کو سمجھنا ضروری ہے، جب حقیقی زندگی کے سافٹ ویئر کی ترقی کی بات آتی ہے، تو آپ ابتدائی صفوں میں ترتیب سے کہیں زیادہ ArrayLists کو چھانٹ رہے ہوں گے۔ ArrayList کو ترتیب دینے کے لیے یہاں ایک مرحلہ وار گائیڈ ہے:

1. Elementمجموعہ سے تعلق رکھنے والی اشیاء کے لیے ایک نئی کلاس بنائیں ۔

   public class Element {
       private int id;
   
       public Element(int id) {
           this.id = id;
       }

2. ایک مجموعہ کے اندر، ایک طریقہ ہے compareTo()- ہم اسے دو عناصر کی ids کا موازنہ کرنے کے لیے استعمال کریں گے۔

   public int compareTo(Element element) {
           int res = 0;
           if (this.id < element.getId()) {
               res = -1;
           }
           if (this.id > element.getId()) {
               res = 1;
           }
           return res;
       }
   }

3. الگورتھم کا اطلاق کریں اور اشیاء کا ArrayListموازنہ کرنے کے بجائے ان کو ترتیب دینے کے لیے کچھ لوپس بنائیں۔

   public static void insertionSortArrayList(List<element> list) {
       for (int j = 1; j < list.size(); j++) {
           Element current = list.get(j);
           int i = j-1;
           while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
               list.set(i+1, list.get(i));
               i--;
           }
           list.set(i+1, current);
       }
   }

4. آپ مزید عناصر کو ArrayListبھی شامل کر سکتے ہیں، جیسا کہ ذیل میں دکھایا گیا ہے:

   List<element> list = new ArrayList<>();
   
   // Create elements w/ IDs 0-24
   for (int i = 0; i < 25; i++) {
       list.add(new Element(i));
   }
   
   // To use insertion sort, shuffle the values
   Collections.shuffle(list);

5. اب یہ ترتیب دینے کا وقت ہے:

   // This helps print values before sorting
   list.forEach(e -> System.out.print(e.getId() + ", "));
   
   // Sort the list
   insertionSortArrayList(list);
   
   System.out.println();
   
   // Display a sorted array
   list.forEach(e -> System.out.print(e.getId() + ", "));

6. اب آئیے ان پٹ اور آؤٹ پٹ کا موازنہ کریں تاکہ یہ یقینی بنایا جا سکے کہ ہم نے کوئی غلطی نہیں کی۔ یہاں اس سٹرنگ کا موازنہ ہے جسے ہم نے بطور مثال استعمال کیا ہے۔

   
   4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

داخل کرنے کی ترتیب کی مشق کے مسائل

اب جب کہ آپ نے اس الگورتھم کو چھانٹ لیا ہے، اب وقت آگیا ہے کہ آپ اپنی نظریاتی اور عملی صلاحیتوں کو پرکھیں۔ تھیوری کوئز #1 آپ کو ایک صف دی گئی ہے [1, 4, 6, 8] اور اس میں ایک نیا عنصر n = 7 شامل کر رہے ہیں۔ نمبروں کی ترتیب شدہ ترتیب حاصل کرنے کے لیے آپ کو کتنی تعداد میں موازنہ کرنے کی ضرورت ہوگی؟ صف میں انڈیکس n کی حتمی قدر کی نشاندہی کریں۔ تھیوری کوئز #2 نوکری کے انٹرویو میں، ایک ٹیم لیڈ آپ سے یہ ثابت کرنے کے لیے کہتی ہے کہ چھانٹ داخل کرنا ایک غیر موثر طریقہ ہے۔ [0, 3, 6, 8, 9] کی عددی تار کو دیکھتے ہوئے، ترتیب دینے کے لیے درکار وقت کو زیادہ سے زیادہ کرنے کے لیے آپ کے ان پٹ کی ترتیب کا کیا ہونا چاہیے؟ پریکٹس کا مسئلہ جاوا کے لیے اندراج کی ترتیب کا استعمال کرتے ہوئے [0، 1، 4، 5، 2، 3، 7، 9، 8] صف کو صعودی ترتیب میں ترتیب دیں۔

نتیجہ

اندراج کی ترتیب کو سمجھنے میں سب سے بڑا چیلنج یہ سمجھنا ہے کہ عمل کیسے کام کرتا ہے۔ ایک بار جب آپ نے اسے ہینگ کر لیا تو، ٹیمپلیٹ کو کوڈ میں تبدیل کرنا کیک کا ایک ٹکڑا ہے۔ جب تک آپ مشق کریں گے اور وقت کے ساتھ ساتھ متعلقہ پریکٹس کے مسائل پر نظرثانی کریں گے، آپ تیزی سے اپنے اندراج کی ترتیب کی رفتار کو بہتر بنائیں گے۔