نظریہ اور عملی طور پر الگورتھم کو ترتیب دینا

چھانٹنا بنیادی کارروائیوں میں سے ایک ہے جو ہم اشیاء پر انجام دیتے ہیں۔ بچپن میں بھی، بچوں کو ترتیب دینا سکھایا جاتا ہے کیونکہ وہ اپنی سوچنے کی صلاحیتوں کو فروغ دیتے ہیں۔ کمپیوٹر اور سافٹ ویئر بھی اس سے مستثنیٰ نہیں ہیں۔ جاوا میں الگورتھم چھانٹنے کی بہت بڑی قسمیں ہیں ۔ میرا مشورہ ہے کہ آپ دیکھیں کہ وہ کیا ہیں اور وہ کیسے کام کرتے ہیں۔ اگر کسی دن انٹرویو میں آپ سے ان میں سے کسی کے بارے میں پوچھا جائے تو کیا ہوگا؟

تعارف

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

int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
	System.out.println(array[i]);
}

کوڈ کے اس حصے کے بارے میں کیا کہا جا سکتا ہے؟ ہمارے پاس ایک لوپ ہے جس میں ہم انڈیکس ( int i) کو 0 سے آخری عنصر میں تبدیل کرتے ہیں۔ درحقیقت، ہم صرف ہر ایک عنصر کو صف میں لے جا رہے ہیں اور اس کے مواد کو پرنٹ کر رہے ہیں۔ صف میں جتنے زیادہ عناصر ہوں گے، کوڈ کو ختم ہونے میں اتنا ہی زیادہ وقت لگے گا۔ یعنی، اگر nعناصر کی تعداد ہے، جب n = 10پروگرام کو چلنے میں دوگنا وقت لگے گا جب سے n = 5۔ اگر ہمارے پروگرام میں ایک ہی لوپ ہے، تو عملدرآمد کا وقت خطی طور پر بڑھتا ہے: جتنے زیادہ عناصر ہوں گے، عملدرآمد کا وقت اتنا ہی لمبا ہوگا۔ اس سے پتہ چلتا ہے کہ اوپر والا الگورتھم لکیری وقت (n کا ایک لکیری فعل) میں کام کرتا ہے۔ ایسے معاملات میں، ہم کہتے ہیں کہ الگورتھم کی پیچیدگی "O(n)" ہے۔ اس اشارے کو "بڑا O" یا "asymptotic برتاؤ" بھی کہا جاتا ہے۔ لیکن آپ صرف "الگورتھم کی پیچیدگی" کو یاد رکھ سکتے ہیں۔

سب سے آسان چھانٹنے والا الگورتھم (بلبلے کی ترتیب)

فرض کریں کہ ہمارے پاس ایک صف ہے اور ہم اس کے ذریعے اعادہ کر سکتے ہیں۔ زبردست. اب اسے صعودی ترتیب میں ترتیب دینے کی کوشش کرتے ہیں۔ اس کا کیا مطلب ہے؟ اس کا مطلب ہے کہ دو عناصر دیئے گئے (مثال کے طور پر a = 6، , b = 5)، ہمیں دوبارہ ترتیب دینا چاہیے aاور bاگر (if ) aسے بڑا ہو اس کا کیا مطلب ہے جب ہم کسی مجموعہ کے ساتھ کام کرنے کے لیے انڈیکس استعمال کر رہے ہیں (جیسا کہ ایک صف کا معاملہ ہے)؟ اس کا مطلب ہے کہ اگر انڈیکس اے والا عنصر انڈیکس ( ) والے عنصر سے بڑا ہے تو عناصر کو تبدیل کرنا ضروری ہے۔ جگہوں کو تبدیل کرنے کے مختلف طریقے ہیں۔ لیکن ہم ایک ایسی تکنیک استعمال کریں گے جو سادہ، قابل فہم اور یاد رکھنے میں آسان ہو: ba > bbarray[a] > array[b]

private void swap(int[] array, int ind1, int ind2) {
    int tmp = array[ind1];
    array[ind1] = array[ind2];
    array[ind2] = tmp;
}

اب ہم مندرجہ ذیل لکھ سکتے ہیں:

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
	if (array[i] < array[i - 1]) {	
		swap(array, i, i-1);
	}
}
System.out.println(Arrays.toString(array));

جیسا کہ آپ دیکھ سکتے ہیں، عناصر کو واقعی تبدیل کر دیا گیا تھا. ہم نے انڈیکس 1 سے آغاز کیا، کیونکہ اگر صف میں صرف ایک عنصر ہے، تو اظہار array[i] < array[i-1]index کے لیے غلط ہے 0۔ ایسا کرنا ہمیں ایسے معاملات سے بھی بچاتا ہے جہاں سرنی میں کوئی عنصر نہیں ہوتا ہے یا صرف ایک عنصر ہوتا ہے، اور یہ کوڈ کو بہتر بناتا ہے۔ لیکن نتیجہ خیز صف کو ابھی بھی ترتیب نہیں دیا گیا ہے، کیونکہ چھانٹنے کے لیے ایک پاس کافی نہیں ہے۔ ہمیں ایک اور لوپ شامل کرنا پڑے گا جس میں ہم بار بار پاسز کریں گے جب تک کہ ہمیں ترتیب شدہ صف نہیں مل جاتی:

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
	needIteration = false;
	for (int i = 1; i < array.length; i++) {
		if (array[i] < array[i - 1]) {
			swap(array, i, i-1);
			needIteration = true;
		}
	}
}
System.out.println(Arrays.toString(array));

تو ہم نے اپنا پہلا ترتیب دینے والا الگورتھم ختم کیا۔ ہم بیرونی لوپ ( while) کو دہراتے ہیں جب تک کہ ہم یہ فیصلہ نہ کر لیں کہ مزید تکرار کی ضرورت نہیں ہے۔ پہلے سے طے شدہ طور پر، ہر نئی تکرار سے پہلے، ہم فرض کرتے ہیں کہ ہماری صف ترتیب دی گئی ہے اور ہمیں مزید لوپ کرنے کی ضرورت نہیں ہے۔ اس کے مطابق، ہم عناصر کے ذریعے ترتیب وار حرکت کرتے ہیں اور اس مفروضے کو چیک کرتے ہیں۔ لیکن اگر عناصر ترتیب میں نہیں ہیں، تو ہم عناصر کو تبدیل کرتے ہیں اور سمجھتے ہیں کہ اب ہمارے پاس کوئی ضمانت نہیں ہے کہ عناصر صحیح ترتیب میں ہیں۔ اس کا مطلب ہے کہ ہمیں ایک اور تکرار کرنے کی ضرورت ہے۔ مثال کے طور پر، فرض کریں کہ ہمارے پاس ہے [3, 5, 2]۔ 5سے زیادہ ہے 3- سب ٹھیک ہے۔ لیکن 2اس سے کم ہے 5۔ تاہم، [3, 2, 5]ایک اور پاس کی ضرورت ہے، کیونکہ 3 > 2اور انہیں تبدیل کرنے کی ضرورت ہے۔ چونکہ ہم ایک لوپ کے اندر ایک لوپ استعمال کر رہے ہیں، ہمارے الگورتھم کی پیچیدگی بڑھ جاتی ہے۔ عناصر کو دیکھتے ہوئے n، یہ بن جاتا ہے n * n، یعنی O(n^2). اسے چوکور پیچیدگی کہتے ہیں۔ عام طور پر، ہم بالکل نہیں جان سکتے کہ کتنی تکرار کی ضرورت ہوگی۔ الگورتھم کی پیچیدگی کا اظہار ظاہر کرتا ہے کہ بدترین صورت میں پیچیدگی کیسے بڑھ جاتی ہے۔ nیعنی، یہ بتاتا ہے کہ عناصر کی تعداد میں تبدیلی کے ساتھ عملدرآمد کا وقت کتنا بڑھ جائے گا ۔ ببل ترتیب سب سے آسان اور غیر موثر ترتیب دینے والے الگورتھم میں سے ایک ہے۔ اسے بعض اوقات "احمقانہ ترتیب" بھی کہا جاتا ہے۔ اس موضوع پر مواد:

• "ہیکر رینک: الگورتھم - بلبلے کی ترتیب "

انتخاب کی ترتیب

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

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
	int minInd = left;
	for (int i = left; i < array.length; i++) {
		if (array[i] < array[minInd]) {
			minInd = i;
		}
	}
	swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));

یہ ترتیب غیر مستحکم ہے، کیونکہ ایک جیسے عناصر (جو بھی خصوصیت کے لحاظ سے ہم عناصر کو ترتیب دینے کے لیے استعمال کر رہے ہیں) اپنی متعلقہ پوزیشن کو تبدیل کر سکتے ہیں۔ اس کی ایک اچھی مثال ویکیپیڈیا مضمون میں انتخاب کی ترتیب پر ہے ۔ اس موضوع پر مواد:

• "CS50: انتخاب کی ترتیب"

اندراج کی ترتیب

داخل کرنے کی ترتیب میں چوکور پیچیدگی بھی ہوتی ہے، کیونکہ ہمارے پاس پھر سے ایک لوپ کے اندر ایک لوپ ہوتا ہے۔ کیا اندراج کی ترتیب کو مختلف بناتا ہے؟ یہ ترتیب دینے والا الگورتھم "مستحکم" ہے۔ اس کا مطلب یہ ہے کہ ایک جیسے عناصر اپنے متعلقہ ترتیب کو تبدیل نہیں کریں گے۔ ایک بار پھر، ہمارا مطلب ان خصوصیات کے لحاظ سے یکساں ہے جن کو ہم ترتیب دے رہے ہیں۔

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
	// Get an element
	int value = array[left];
	// Iterate through the elements that are in front of this element
	int i = left - 1;
	for (; i >= 0; i--) {
		// If the current element is smaller, then move the larger element to the right.
		if (value < array[i]) {
			array[i + 1] = array[i];
		} else {
			// If the current element is larger, we stop
			break;
		}
	}
	// Insert the current value in the empty space
	array[i + 1] = value;
}
System.out.println(Arrays.toString(array));

شٹل کی ترتیب

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

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
	if (array[i] < array[i - 1]) {
		swap(array, i, i - 1);
		for (int z = i - 1; (z - 1) >= 0; z--) {
			if (array[z] < array[z - 1]) {
				swap(array, z, z - 1);
			} else {
				break;
			}
		}
	}
}
System.out.println(Arrays.toString(array));

اس موضوع پر مواد:

• AQA فیصلہ 1 2.02a جیک براؤن کی طرف سے شٹل ترتیب متعارف کروا رہا ہے۔

شیل کی ترتیب

ایک اور آسان چھانٹنے والا الگورتھم شیل ترتیب ہے۔ اس کا خلاصہ بلبلے کی ترتیب سے ملتا جلتا ہے، لیکن ہر تکرار میں ہمارے پاس موازنہ عناصر کے درمیان فرق ہوتا ہے۔ اسے ہر تکرار کے ساتھ نصف میں کاٹا جاتا ہے۔ یہاں ایک نفاذ ہے:

int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
    for (int right = 0; right < array.length; right++) {
        // Shift the right index until we find one for which
        // there is the necessary gap between it and the element before it
       for (int c = right - gap; c >= 0; c -= gap) {
           if (array[c] > array[c + gap]) {
               swap(array, c, c + gap);
           }
        }
    }
    // Recalculate the gap
    gap = gap / 2;
}
System.out.println(Arrays.toString(array));

اس موضوع پر مواد:

• AQA فیصلہ 1 2.03a شیل ترتیب - 8 نمبروں کے ساتھ ایک مثال

ترتیب کو ضم کریں۔

ان آسان چھانٹنے والے الگورتھم کے علاوہ، مزید پیچیدہ ترتیب دینے والے الگورتھم بھی ہیں۔ مثال کے طور پر، ترتیب کو ضم کریں۔ دو باتیں قابلِ غور ہیں۔ سب سے پہلے، تکرار یہاں ہمارے بچاؤ کے لیے آتی ہے۔ دوسرا، الگورتھم کی پیچیدگی اب چوکور نہیں ہے، جیسا کہ ہم عادی ہیں۔ اس الگورتھم کی پیچیدگی لوگاریتھمک ہے۔ یہ اس طرح لکھا جاتا ہے O(n log n)۔ تو آئیے اس پر عمل درآمد کریں۔ سب سے پہلے، ہم ترتیب کے طریقہ پر ایک بار بار کال لکھیں گے:

public static void mergeSort(int[] source, int left, int right) {
        // Select the delimiter, i.e. split the input array in half
        int delimiter = left + ((right - left) / 2) + 1;
        // Recursively execute this function on the two halves (if we can split the input array)
        if (delimiter > 0 && right > (left + 1)) {
            mergeSort(source, left, delimiter - 1);
            mergeSort(source, delimiter, right);
        }
}

اب، آئیے اپنے نفاذ میں اہم کارروائی شامل کریں۔ ہمارا سپر طریقہ یہ ہے:

public static void mergeSort(int[] source, int left, int right) {
        // Select the delimiter, i.e. split the input array in half
        int delimiter = left + ((right - left) / 2) + 1;
        // Recursively execute this function on the two halves (if we can split the input array)
        if (delimiter > 0 && right > (left + 1)) {
            mergeSort(source, left, delimiter - 1);
            mergeSort(source, delimiter, right);
        }
        // Create a temporary array with the required size
        int[] buffer = new int[right - left + 1];
        // Starting from the specified left index, go through each element.
        int cursor = left;
        for (int i = 0; i < buffer.length; i++) {
            // We use delimeter to point to the element on the right half
            // If delimeter> right, then the right half has no elements that haven't been added
            if (delimiter > right || source[cursor] > source[delimiter]) {
                buffer[i] = source[cursor];
                cursor++;
            } else {
                buffer[i] = source[delimiter];
                delimiter++;
            }
        }
        System.arraycopy(buffer, 0, source, left, buffer.length);
}

ہم کال کرکے اپنی مثال چلا سکتے ہیں mergeSort(array, 0, array.length-1)۔ جیسا کہ آپ دیکھ سکتے ہیں، یہ عمل ان پٹ سرنی کو قبول کرنے کے ساتھ ساتھ اس حصے کے آغاز اور اختتام کے اشارے کے ساتھ ابلتا ہے جسے ترتیب دینے کی ضرورت ہے۔ جب چھانٹنا شروع ہوتا ہے، یہ صف کا آغاز اور اختتام ہوتا ہے۔ پھر ہم حد بندی کا حساب لگاتے ہیں، جو انڈیکس ہے جہاں ہم صف کو تقسیم کریں گے۔ اگر صف کو 2 حصوں میں تقسیم کیا جا سکتا ہے، تو ہم صف کے دو حصوں کے لیے بار بار ترتیب دینے کا طریقہ کہتے ہیں۔ ہم ایک معاون بفر تیار کرتے ہیں جہاں ہم ترتیب شدہ سیکشن داخل کریں گے۔ اس کے بعد، ترتیب دینے کے لیے سیکشن کے شروع میں انڈیکس سیٹ کریں اور خالی بفر کے ہر عنصر کے ذریعے چلنا شروع کریں، اسے چھوٹے عناصر سے بھریں۔ اگر انڈیکس کے ذریعہ اشارہ کیا گیا عنصر حد بندی کے ذریعہ اشارہ کردہ عنصر سے کم ہے، تو ہم عنصر کو بفر میں ڈالتے ہیں اور انڈیکس کو شفٹ کرتے ہیں۔ بصورت دیگر، ہم حد بندی کے ذریعہ اشارہ کردہ عنصر کو بفر میں رکھتے ہیں اور حد بندی کو شفٹ کرتے ہیں۔ جیسے ہی حد بندی ترتیب دیے جانے والے حصے کی حدود سے باہر جاتی ہے یا ہم پوری صف کو بھرتے ہیں، مخصوص رینج کو ترتیب دیا جاتا ہے۔ اس موضوع پر مواد:

• CS50: ترتیب کو ضم کریں۔
• آئیڈیا ہدایات - ضم ترتیب دیں۔

گنتی کی ترتیب اور ریڈکس ترتیب

ایک اور دلچسپ ترتیب دینے والا الگورتھم گنتی کی ترتیب ہے۔ یہاں الگورتھمک پیچیدگی ہے O(n+k)، nعناصر کی تعداد کہاں ہے اور kعنصر کی زیادہ سے زیادہ قدر ہے۔ اس الگورتھم میں ایک کمی ہے: ہمیں صف میں کم از کم اور زیادہ سے زیادہ قدروں کو جاننے کی ضرورت ہے۔ گنتی کی ترتیب کی ایک مثال یہ ہے:

public static int[] countingSort(int[] theArray, int maxValue) {
        // An array of "counters", ranging from 0 to the maximum value
        int numCounts[] = new int[maxValue + 1];
        // We increase the counter in the corresponding cell (index = value)
        for (int num : theArray) {
            numCounts[num]++;
        }
        // Create an array to hold the sorted result
        int[] sortedArray = new int[theArray.length];
        int currentSortedIndex = 0;
        // Run through the array of "counters"
        for (int n = 0; n < numCounts.length; n++) {
            int count = numCounts[n];
            // Run through the number of values
            for (int k = 0; k < count; k++) {
                sortedArray[currentSortedIndex] = n;
                currentSortedIndex++;
            }
        }
        return sortedArray;
    }

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

• گنتی کی ترتیب کے بارے میں ویڈیو
• گنتی ترتیب الگورتھم

فوری ترتیب

ٹھیک ہے، یہ میٹھے کا وقت ہے - فوری ترتیب، سب سے مشہور ترتیب دینے والے الگورتھم میں سے ایک۔ اس میں لوگارتھمک پیچیدگی ہے: O(n log n). یہ ترتیب دینے والا الگورتھم ٹونی ہوئر نے تیار کیا تھا۔ دلچسپ بات یہ ہے کہ اس نے اسے سوویت یونین میں رہتے ہوئے ایجاد کیا، جہاں اس نے ماسکو یونیورسٹی میں مشینی ترجمہ کی تعلیم حاصل کی اور ایک روسی-انگریزی فقرے کی کتاب تیار کی۔ مزید کیا ہے، جاوا اس الگورتھم کا زیادہ پیچیدہ ورژن میں استعمال کرتا ہے Arrays.sort۔ Collections.sortکے بارے میں کیوں نہ اس پر ایک نظر ڈالیں کہ چیزوں کو "ہڈ کے نیچے" کیسے ترتیب دیا جاتا ہے؟ یہ کوڈ ہے:

public static void quickSort(int[] source, int leftBorder, int rightBorder) {
        int leftMarker = leftBorder;
        int rightMarker = rightBorder;
        int pivot = source[(leftMarker + rightMarker) / 2];
        do {
            // Move the left marker from left to right as long as the element is less than pivot
            while (source[leftMarker] < pivot) {
                leftMarker++;
            }
            // Move the right marker as long as the element is greater than pivot
            while (source[rightMarker] > pivot) {
                rightMarker--;
            }
            // Check whether we need to swap the elements pointed to by the markers
            if (leftMarker <= rightMarker) {
                // The left marker will be less than the right one only if we need to do a swap
                if (leftMarker < rightMarker) {
                    int tmp = source[leftMarker];
                    source[leftMarker] = source[rightMarker];
                    source[rightMarker] = tmp;
                }
                // Shift the markers to get new borders
                leftMarker++;
                rightMarker--;
            }
        } while (leftMarker <= rightMarker);

        // Execute recursively on the parts
        if (leftMarker < rightBorder) {
            quickSort(source, leftMarker, rightBorder);
        }
        if (leftBorder < rightMarker) {
            quickSort(source, leftBorder, rightMarker);
        }
}

یہ سب بہت خوفناک چیز ہے، تو آئیے اس میں کھودتے ہیں۔ ان پٹ اری ( int[]ذریعہ) کے لیے، ہم دو مارکر بناتے ہیں: بائیں ( L) اور دائیں ( R)۔ پہلے طریقہ کال کے دوران، وہ صف کے آغاز اور اختتام سے مطابقت رکھتے ہیں۔ پھر ہم محور عنصر کی شناخت کرتے ہیں، جسے مناسب طور پر نام دیا گیا ہے pivot۔ pivotاس کے بعد، ہمارا کام یہ ہے کہ قدروں کو بائیں سے چھوٹی pivot، اور بڑی کو — دائیں طرف منتقل کریں۔ ایسا کرنے کے لیے، ہم سب سے پہلے Lمارکر کو اس وقت تک منتقل کرتے ہیں جب تک کہ ہمیں اس سے بڑی قدر نہ مل جائے pivot۔ اگر کوئی چھوٹی قدر نہیں ملتی ہے، تو L کے برابر ہو جاتا ہے pivot۔ پھر ہم Rمارکر کو اس وقت تک منتقل کرتے ہیں جب تک کہ ہمیں اس سے چھوٹی قدر نہ مل جائے pivot۔ اگر کوئی بڑی قدر نہیں ملتی ہے، تو Rبرابر ہو جاتا ہے pivot۔ اگلا، اگر Lمارکر مارکر سے پہلے ہے Rیا اس کے ساتھ موافق ہے، تو ہم عناصر کو تبدیل کرنے کی کوشش کرتے ہیں اگر Lعنصر عنصر سے کم ہو R۔ پھر ہم L1 سے دائیں طرف شفٹ ہوتے ہیں، اور ہم R1 سے بائیں طرف شفٹ ہوتے ہیں۔ جب Lمارکر مارکر سے آگے بڑھتا ہے R، تو اس کا مطلب ہے کہ تبادلہ مکمل ہو گیا ہے: چھوٹی قدریں کے بائیں pivot، بڑی قدریں دائیں طرف ہیں pivot۔ اس کے بعد، ہم ذیلی ریزوں پر بار بار اسی ترتیب کے طریقہ کو کہتے ہیں — جس حصے کو ترتیب دیا جانا ہے اس کے شروع سے لے کر دائیں مارکر تک، اور ترتیب دینے کے لیے بائیں مارکر سے سیکشن کے آخر تک۔ شروع سے صحیح مارکر تک کیوں؟ کیونکہ تکرار کے اختتام پر، یہ پتہ چلتا ہے کہ دائیں مارکر بائیں حصے کی حد بننے کے لیے کافی حرکت کرتا ہے۔ یہ الگورتھم سادہ چھانٹی سے زیادہ پیچیدہ ہے، اس لیے اس کا خاکہ بنانا بہتر ہے۔ کاغذ کی ایک سفید شیٹ لیں اور لکھیں: 4 2 6 7 3۔ پھر pivotدرمیان میں لکھیں، یعنی نمبر 6 کے نیچے۔ اس پر چکر لگائیں۔ 4 کے تحت، لکھیں L، اور 3 کے نیچے، لکھیں R۔ L6 سے 4 کم، 6 سے 2 کم۔ ہم پوزیشن پر چلے جاتے ہیں pivot، کیونکہ شرط کے مطابق، Lماضی میں نہیں جا سکتے ۔ pivotدوبارہ لکھیں 4 2 6 7 3۔ دائرہ 6 ( pivot) اور Lاس کے نیچے رکھیں۔ اب Rمارکر کو حرکت دیں۔ R3 6 سے کم ہے، اس لیے مارکر کو 3 پر رکھیں۔ چونکہ 3 6 سے کم ہے ( pivotاس لیے ہم ایک کرتے ہیں swap۔ نتیجہ لکھیں: 4 2 3 7 6. حلقہ 6، کیونکہ یہ اب بھی ہے pivot۔ مارکر L3 پر ہے۔ Rمارکر 6 پر ہے۔ یاد رکھیں کہ ہم مارکر کو اس وقت تک منتقل کرتے ہیں جب تک کہ Lآگے نہ بڑھیں R۔ Lاگلے نمبر پر جائیں ۔ یہاں میں دو امکانات کو تلاش کرنا چاہوں گا: 1) وہ کیس جہاں آخری نمبر 7 ہے اور 2) وہ معاملہ جہاں یہ 1 ہے، 7 نہیں۔ اگر آخری نمبر 1 ہے: مارکر کو 1 پر منتقل کریں L، کیونکہ ہم منتقل کر سکتے ہیں۔ Lجب تک Lمارکر اس سے چھوٹے نمبر کی طرف اشارہ کرتا ہے pivot۔ لیکن ہم 6 سے ہٹ نہیں سکتے R، کیونکہ ہم صرف R کو منتقل کر سکتے ہیں اگر Rمارکر کسی ایسے نمبر کی طرف اشارہ کرے جو اس سے زیادہ ہو pivot۔ ہم انجام نہیں دیتے swapکیونکہ 1 6 سے کم ہے۔ موجودہ صورتحال لکھیں: 4 2 3 1 6۔ حلقہ 6 ( pivot)۔ Lمنتقل ہوتا ہے pivotاور حرکت کرنا بند کر دیتا ہے۔ Rحرکت نہیں کرتا. ہم تبادلہ نہیں کرتے ہیں۔ شفٹ Lاور Rایک پوزیشن سے۔ Rمارکر کو 1 کے نیچے لکھیں۔ Lمارکر حد سے باہر ہے۔ کیونکہ Lحد سے باہر ہے، ہم کچھ نہیں کرتے۔ لیکن، ہم دوبارہ 4 2 3 1 لکھتے ہیں، کیونکہ یہ ہماری بائیں طرف ہے، جو pivot(6) سے کم ہے۔ نیا منتخب کریں pivotاور سب کچھ دوبارہ شروع کریں :) اگر آخری نمبر 7 ہے: مارکر کو 7 پر منتقل کریں L۔ ہم صحیح مارکر کو منتقل نہیں کر سکتے، کیونکہ یہ پہلے ہی محور کی طرف اشارہ کر رہا ہے۔ 7 سے بڑا ہے pivot، اس لیے ہم ایک کرتے ہیں swap۔ نتیجہ لکھیں: 4 2 3 6 7. حلقہ 6، کیونکہ یہ ہے pivot۔ مارکر Lاب 7 پر شفٹ ہو گیا ہے، اور مارکر 3 پر شفٹ ہو گیا ہے۔ اس حصے کو آخر تک Rچھانٹنا کوئی معنی نہیں رکھتا ، کیونکہ صرف 1 عنصر ہے۔ تاہم، ہم چھانٹنے کے لیے L4 سے حصہ مارکر کو بھیجتے ہیں ۔ Rہم ایک کا انتخاب کرتے ہیں pivotاور دوبارہ شروع کرتے ہیں :) پہلی نظر میں، ایسا لگتا ہے کہ اگر آپ کے برابر بہت سی قدریں شامل کریں pivot، تو آپ الگورتھم کو توڑ دیں گے۔ لیکن یہ معاملہ نہیں ہے۔ آپ مشکل امتزاج کے بارے میں سوچ سکتے ہیں اور کاغذ پر اپنے آپ کو قائل کر سکتے ہیں کہ سب کچھ درست ہے اور حیرت ہے کہ اس طرح کے سادہ اقدامات اس طرح کے قابل اعتماد چھانٹنے والے طریقہ کار کو نافذ کرتے ہیں۔ صرف منفی پہلو یہ ہے کہ یہ ترتیب دینے والا الگورتھم مستحکم نہیں ہے۔ کیونکہ ایک سویپ یکساں عناصر کے رشتہ دار ترتیب کو تبدیل کر سکتا ہے اگر ان میں سے کسی ایک کا سامنا اس سے پہلے ہو کہ pivotدوسرے عنصر کو اس سے پہلے کے حصے میں تبدیل کیا جائے pivot۔

نیچے کی لکیر

اوپر، ہم نے جاوا میں لاگو کردہ الگورتھم کی ترتیب کے ایک "جنٹل مین" سیٹ کو دیکھا۔ الگورتھم عام طور پر مفید ہوتے ہیں، دونوں اطلاقی نقطہ نظر سے اور سوچنا سیکھنے کے لحاظ سے۔ کچھ آسان ہیں، کچھ زیادہ پیچیدہ ہیں۔ ہوشیار لوگوں نے کچھ کے لئے اپنے مقالوں کا دفاع کیا۔ دوسروں کے لیے، انہوں نے انتہائی موٹی کتابیں لکھیں۔ مجھے امید ہے کہ ضمنی مواد آپ کو مزید جاننے میں مدد کرے گا، کیونکہ یہ مضمون صرف ایک جائزہ ہے جو پہلے ہی وزنی نکلا ہے۔ اور اس کا مقصد ایک چھوٹا سا تعارف پیش کرنا ہے۔ اگر آپ "گروکنگ الگورتھم " پڑھتے ہیں تو آپ الگورتھم کا تعارف بھی حاصل کر سکتے ہیں ۔ مجھے جیک براؤن کی پلے لسٹ بھی پسند ہے: AQA Decision 1 1.01 Tracing an Algorithm . تفریح ​​کے لیے، آپ sorting.at اور visualgo.net پر الگورتھم کے تصورات دیکھ سکتے ہیں ۔