CodeGym /جاوا بلاگ /Random-SD /نظريي ۽ عمل ۾ الگورتھم کي ترتيب ڏيڻ

سطح

San Francisco

14 February 2023
64 views
0 comments

نظريي ۽ عمل ۾ الگورتھم کي ترتيب ڏيڻ

ترتيب ڏيڻ بنيادي عملن مان هڪ آهي جيڪو اسان شين تي انجام ڏيون ٿا. جيتوڻيڪ ننڍپڻ ۾، ٻارن کي ترتيب ڏيڻ سيکاريو ويندو آهي جيئن اهي انهن جي سوچ جي صلاحيتن کي ترقي ڪن. ڪمپيوٽر ۽ سافٽ ويئر ڪو به استثنا نه آهن. جاوا ۾ ترتيب ڏيڻ واري الگورتھم جا تمام وڏا قسم آھن . مان صلاح ڏيان ٿو ته توهان چيڪ ڪريو ته اهي ڇا آهن ۽ اهي ڪيئن ڪم ڪن ٿا. ڇا جيڪڏهن توهان انهن مان ڪنهن جي باري ۾ پڇيو ته ڪنهن ڏينهن انٽرويو ۾؟

تعارف

عناصر کي ترتيب ڏيڻ الورورٿم جي قسمن مان هڪ آهي جيڪو هڪ ڊولپر کي ڄاڻڻ گهرجي. جيڪڏهن ڪمپيوٽر سائنس کي ڪنهن وقت سنجيدگيءَ سان نه ورتو ويو هو جڏهن آئون اسڪول ۾ هئس، ته اڄ جي شاگردن کي ترتيب ڏيڻ واري الگورتھم کي لاڳو ڪرڻ ۽ سمجهڻ جي قابل هوندو. بنيادي الگورتھم، آسان ترين، لوپ لاء استعمال ڪندي لاڳو ڪيا ويا آھن . قدرتي طور، عناصر جي مجموعي کي ترتيب ڏيڻ لاء، جهڙوڪ هڪ صف، توهان کي ڪنهن به طريقي سان گڏ ڪرڻ جي ضرورت آهي. مثال طور:

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. جيڪڏهن اسان جي پروگرام ۾ هڪ واحد لوپ آهي، عملدرآمد جو وقت لڪيريء سان وڌندو آهي: وڌيڪ عناصر موجود آهن، وڌيڪ عملدرآمد وقت. اهو ظاهر ٿئي ٿو ته مٿيون الورورٿم لڪير واري وقت ۾ ڪم ڪري ٿو (ن جي هڪ لڪير فنڪشن). اهڙين حالتن ۾، اسان چئون ٿا ته الگورتھم جي پيچيدگي "O (n)" آهي. اهو اشارو پڻ سڏيو ويندو آهي "وڏو O" يا "asymptotic رويي". پر توهان صرف "الگورٿم جي پيچيدگي" کي ياد ڪري سگهو ٿا.

آسان ترين ترتيب ڏيڻ وارو الگورتھم (بلبل ترتيب)

فرض ڪريو اسان وٽ هڪ صف آهي ۽ اسان ان جي ذريعي ٻيهر ڪري سگهون ٿا. زبردست. هاڻي اچو ته ان کي ترتيب ڏيڻ جي ڪوشش ڪريون وڌندي ترتيب ۾. هن جو مطلب ڇا آهي؟ ان جو مطلب اهو آهي ته ڏنل ٻه عنصر (مثال طور a = 6،، b = 5)، اسان کي ٻيهر ترتيب ڏيڻ گهرجي a۽ bجيڪڏهن (جيڪڏهن ) aکان وڏو آهي . ان جو مطلب ڇا آھي جڏھن اسان ھڪڙي انڊيڪس استعمال ڪري رھيا آھيون ھڪڙي مجموعي سان ڪم ڪرڻ لاءِ (جيئن ھڪڙي صف سان معاملو آھي)؟ ان جو مطلب اهو آهي ته جيڪڏهن عنصر انڊيڪس 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]انڊيڪس لاء غلط آهي 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) کي ٻيهر ورجائيندا آهيون جيستائين اسان اهو فيصلو ڪريون ته وڌيڪ ورهاڱي جي ضرورت ناهي. ڊفالٽ طور، هر نئين iteration کان اڳ، اسان فرض ڪريون ٿا ته اسان جي صف ترتيب ڏنل آهي ۽ اسان کي وڌيڪ لوپ ڪرڻ جي ضرورت ناهي. ان جي مطابق، اسان عناصر جي ذريعي ترتيب سان منتقل ڪريون ٿا ۽ هن مفروضي کي چيڪ ڪريو. پر جيڪڏهن عناصر ترتيب ۾ نه آهن، ته پوء اسان عناصر کي تبديل ڪريون ٿا ۽ سمجهون ٿا ته اسان وٽ هاڻي ڪا به ضمانت نه آهي ته عناصر صحيح ترتيب ۾ آهن. ان جو مطلب اهو آهي ته اسان کي هڪ ٻيو عمل ڪرڻو پوندو. مثال طور، فرض ڪريو اسان وٽ آهي [3, 5, 2]. 5کان وڌيڪ آهي 3- سڀ ٺيڪ آهي. پر 2کان گهٽ آهي 5. جڏهن ته، [3, 2, 5]هڪ ٻئي پاس جي ضرورت آهي، جتان 3 > 2۽ انهن کي تبديل ڪرڻ جي ضرورت آهي. ڇاڪاڻ ته اسان هڪ لوپ اندر لوپ استعمال ڪري رهيا آهيون، اسان جي الگورتھم جي پيچيدگي وڌائي ٿي. ڏنل nعناصر، اهو ٿي ويندو آهي n * n، اهو آهي، O(n^2). ان کي چئبو آهي quadratic complexity. عام طور تي، اسان اهو نه ٿا ڄاڻون ته ڪيترين ئي ڳالهين جي ضرورت پوندي. هڪ الگورتھم جي پيچيدگي جو اظهار ڏيکاري ٿو ته ڪيئن پيچيدگي بدترين صورت ۾ وڌي ٿي. اھو آھي، اھو ظاھر ڪري ٿو ته عملدرآمد جو وقت ڪيترو وڌندو جيئن عناصر جو تعداد nتبديل ٿيندو. بلبل جي ترتيب هڪ آسان ۽ سڀ کان وڌيڪ غير موثر ترتيب ڏيڻ واري الگورتھم مان هڪ آهي. اهو پڻ ڪڏهن ڪڏهن سڏيو ويندو آهي "بيوقوف ترتيب". هن موضوع تي مواد:

"هيڪر رينڪ: الگورتھم - بلبل ترتيب "

چونڊ جي ترتيب

هڪ ٻيو ترتيب ڏيڻ وارو الگورتھم چونڊ ترتيب آهي. ان ۾ پڻ quadratic پيچيدگي آهي، پر ان تي وڌيڪ بعد ۾. تنهنڪري خيال سادو آهي. هر پاس تي، اسان سڀ کان ننڍڙو عنصر چونڊيو ۽ ان کي شروعات ۾ ڦيرايو. اضافي طور تي، هر پاس هڪ قدم ساڄي طرف شروع ٿئي ٿو. ٻين لفظن ۾، پهريون پاس zeroth عنصر کان شروع ٿئي ٿو، ٻيو پاس پهرين کان، وغيره. اهو هن طرح نظر ايندو:

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: چونڊ ترتيب"

داخل ٿيڻ جي ترتيب

داخل ڪرڻ جي ترتيب ۾ پڻ quadratic پيچيدگي آهي، ڇاڪاڻ ته اسان وٽ وري هڪ لوپ اندر هڪ لوپ آهي. ڇا داخل ڪرڻ جي ترتيب کي مختلف بڻائي ٿو؟ هي ترتيب ڏيڻ وارو الگورتھم "مستحڪم" آهي. هن جو مطلب آهي ته هڪجهڙائي عنصرن سندن لاڳاپو ترتيب تبديل نه ڪندو. ٻيهر، اسان جو مطلب آهي هڪجهڙائي جي لحاظ کان خاصيتن جي لحاظ کان جيڪو اسان ترتيب ڏئي رهيا آهيون.

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 انگن سان

ضم ڪرڻ جي ترتيب

انهن سادي ترتيب ڏيڻ واري الگورتھم کان علاوه، وڌيڪ پيچيده ترتيب ڏيڻ وارا الگورتھم پڻ آهن. مثال طور، ضم ڪرڻ جي ترتيب. نوٽ ڪرڻ لاء ٻه شيون آهن. پهريون، ٻيهر هتي اسان جي بچاء لاء اچي ٿو. ٻيو، الورورٿم جي پيچيدگي هاڻي ڪوڊراٽڪ نه آهي، جيئن اسان کي استعمال ڪيو ويو آهي. هن الگورتھم جي پيچيدگي logarithmic آهي. هي لکيل آهي 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 حصن ۾ ورهائي سگهجي ٿو، ته پوءِ اسين ترتيب جي طريقي کي سڏيندا آهيون سر جي ٻن حصن لاءِ بار بار. اسان هڪ معاون بفر تيار ڪندا آهيون جتي اسان ترتيب ڏنل سيڪشن داخل ڪنداسين. اڳيون، انڊيڪس کي سيڪشن جي شروعات ۾ ترتيب ڏيو ۽ خالي بفر جي هر عنصر ذريعي هلڻ شروع ڪريو، ان کي ننڍن عناصر سان ڀريو. جيڪڏهن انڊيڪس طرفان اشارو ڪيل عنصر ڊيليميٽر طرفان اشارو ڪيل عنصر کان گهٽ آهي، اسان عنصر کي بفر ۾ رکون ٿا ۽ انڊيڪس کي ڦيرايو. ٻي صورت ۾، اسان ڊيليميٽر طرفان اشارو ڪيل عنصر کي بفر ۾ رکون ٿا ۽ ڊيليميٽر کي شفٽ ڪريو. جيئن ئي ڊيليميٽر ترتيب ڏنل حصي جي حدن کان ٻاهر نڪري وڃي ٿو يا اسان پوري صف کي ڀريون ٿا، مخصوص حد کي ترتيب ڏنو وڃي ٿو. هن موضوع تي مواد:

ڳڻپ جي ترتيب ۽ ريڊيڪس ترتيب

هڪ ٻيو دلچسپ ترتيب ڏيڻ وارو الگورتھم ڳڻپ جي ترتيب آهي. الورورٿمڪ پيچيدگي هتي آهي 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، ان جو مطلب آھي ادل بدلائڻ مڪمل ٿي ويو آھي: ننڍڙا قدر 1 جي کاٻي پاسي آھن 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 آهي: L مارڪر کي 1 ڏانهن منتقل ڪريو ، ڇاڪاڻ ته اسان منتقل ڪري سگهون ٿا. 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 ڏانھن منتقل ڪيو ويو آھي، ۽ Rمارڪر کي 3 ڏانھن منتقل ڪيو ويو آھي. اھو سمجھ ۾ نٿو اچي ته حصي کي Lآخر تائين ترتيب ڏيو، ڇاڪاڻ⁠تہ صرف 1 عنصر آھي. تنهن هوندي، اسان ترتيب ڏيڻ لاء 4 کان مارڪر ڏانهن حصو موڪليندا آهيون R. اسان هڪ چونڊيندا آهيون pivot۽ سڀ ٻيهر شروع ڪندا آهيون :) پهرين نظر ۾، اهو لڳي سگهي ٿو ته جيڪڏهن توهان جي برابر ڪيتريون ئي قيمتون شامل ڪريو pivot، ته پوء توهان الگورتھم کي ٽوڙيندا. پر اهو معاملو ناهي. توهان مشڪل مجموعن تي سوچي سگهو ٿا ۽ ڪاغذ تي پنهنجو پاڻ کي قائل ڪري سگهو ٿا ته سڀ ڪجهه صحيح آهي ۽ حيرت انگيز آهي ته اهڙيون سادي ڪارناما اهڙي قابل اعتماد ترتيب واري ميڪانيزم کي لاڳو ڪن ٿيون. صرف نقصان اهو آهي ته هي ترتيب ڏيڻ وارو الگورتھم مستحڪم نه آهي. ڇاڪاڻ ته هڪ ادل بدلجي سگهي ٿو هڪجهڙائي واري عنصرن جي لاڳاپي واري ترتيب کي جيڪڏهن انهن مان هڪ کي سامهون اچي ويو آهي ان کان اڳ جو pivotٻيو عنصر اڳئين حصي ۾ تبديل ڪيو وڃي pivot.

هيٺيون لڪير

مٿي، اسان جاوا ۾ لاڳو ڪيل الگورتھم ترتيب ڏيڻ جي هڪ "حضور جي" سيٽ تي نظر آئي. الگورتھم عام طور تي مفيد آھن، ٻئي لاڳو ٿيل نقطي نظر کان ۽ سکڻ جي لحاظ کان ڪيئن سوچڻ لاء. ڪجھ آسان آھن، ڪجھ وڌيڪ پيچيده آھن. سمارٽ ماڻهن ڪجهه لاءِ پنهنجي مقالي جو دفاع ڪيو. ٻين لاءِ، هنن سپر موٽي ڪتاب لکيا. مون کي اميد آهي ته اضافي مواد توهان کي اڃا به وڌيڪ سکڻ ۾ مدد ڏيندو، ڇو ته هي مضمون صرف هڪ جائزو آهي جيڪو اڳ ۾ ئي وزنائتو ٿي چڪو آهي. ۽ ان جو مقصد هڪ ننڍڙو تعارف مهيا ڪرڻ آهي. جيڪڏھن توھان پڙھندا آھيو ته الورورٿمس جو تعارف پڻ ڳولي سگھو ٿا "گروڪنگ الگورٿمز ". مون کي جڪ براون جي پبليڪيشن پڻ پسند آهي: AQA Decision 1 1.01 Tracing an Algorithm . تفريح لاءِ، توهان sorting.at ۽ visualgo.net تي الگورٿم بصريات ڏسي سگهو ٿا .

تبصرا

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION