छँटाई उन बुनियादी क्रियाओं में से एक है जो हम वस्तुओं पर करते हैं। बचपन में भी, बच्चों को उनके सोचने के कौशल को विकसित करने के लिए क्रमबद्ध करना सिखाया जाता है। कंप्यूटर और सॉफ्टवेयर कोई अपवाद नहीं हैं। जावा में सॉर्टिंग एल्गोरिदम की एक विशाल विविधता है । मेरा सुझाव है कि आप जांचें कि वे क्या हैं और वे कैसे काम करते हैं। क्या होगा अगर किसी दिन एक साक्षात्कार में आपसे उनमें से किसी एक के बारे में पूछा जाए?
परिचय
छँटाई तत्व एल्गोरिदम की श्रेणियों में से एक है जिसे एक डेवलपर को पता होना चाहिए। जब मैं स्कूल में था तब अगर कंप्यूटर साइंस को गंभीरता से नहीं लिया जाता था, तो आज के छात्रों को सॉर्टिंग एल्गोरिदम को लागू करने और समझने में सक्षम होना चाहिए। बुनियादी एल्गोरिदम, सबसे सरल, लूप का उपयोग करके कार्यान्वित किया जाता है। स्वाभाविक रूप से, तत्वों के संग्रह को क्रमबद्ध करने के लिए, जैसे कि एक सरणी, आपको किसी तरह संग्रह से गुजरने की आवश्यकता है। उदाहरण के लिए:
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)" है। इस अंकन को "बिग ओ" या "एसिम्प्टोटिक बिहेवियर" भी कहा जाता है। लेकिन आप सिर्फ याद कर सकते हैं "
सबसे सरल छँटाई एल्गोरिथ्म (बुलबुला छँटाई)
मान लीजिए हमारे पास एक सरणी है और हम इसके माध्यम से पुनरावृति कर सकते हैं। महान। अब इसे आरोही क्रम में क्रमबद्ध करने का प्रयास करते हैं। इसका अर्थ क्या है? इसका अर्थ है कि दिए गए दो तत्व (उदाहरण के लिए, a = 6, b = 5), हमें पुनर्व्यवस्थित करना चाहिए aऔर bयदि (यदि ) 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) को तब तक दोहराते हैं जब तक हम यह तय नहीं कर लेते कि और पुनरावृत्तियों की आवश्यकता नहीं है। डिफ़ॉल्ट रूप से, प्रत्येक नए पुनरावृत्ति से पहले, हम मानते हैं कि हमारी सरणी क्रमबद्ध है और हमें अब लूप करने की आवश्यकता नहीं है। तदनुसार, हम तत्वों के माध्यम से क्रमिक रूप से आगे बढ़ते हैं और इस धारणा की जांच करते हैं। लेकिन अगर तत्व क्रम में नहीं हैं, तो हम तत्वों की अदला-बदली करते हैं और समझते हैं कि अब हमारे पास कोई गारंटी नहीं है कि तत्व सही क्रम में हैं। इसका मतलब है कि हमें एक और पुनरावृत्ति करने की जरूरत है। उदाहरण के लिए, मान लीजिए हमारे पास है [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));
यह छँटाई अस्थिर है, क्योंकि समान तत्व (तत्वों को क्रमबद्ध करने के लिए हम जो भी विशेषता का उपयोग कर रहे हैं) उनके सापेक्ष स्थिति को बदल सकते हैं। चयन प्रकार पर विकिपीडिया आलेख में एक अच्छा उदाहरण है । इस विषय पर सामग्री:
सम्मिलन छँटाई में द्विघात जटिलता भी होती है, क्योंकि हमारे पास फिर से एक लूप के भीतर एक लूप होता है। सम्मिलन प्रकार अलग क्या बनाता है? यह छँटाई एल्गोरिथ्म "स्थिर" है। इसका अर्थ है कि समान तत्व अपने आपेक्षिक क्रम को नहीं बदलेंगे। फिर से, हमारा मतलब उन विशेषताओं के संदर्भ में समान है जिनके द्वारा हम छँटाई कर रहे हैं।
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));
एक अन्य सरल छँटाई एल्गोरिथ्म शेल छँटाई है। इसका सार बबल सॉर्ट के समान है, लेकिन प्रत्येक पुनरावृत्ति में हमारे पास तुलना किए गए तत्वों के बीच एक अलग अंतर होता है। यह प्रत्येक पुनरावृत्ति के साथ आधा में कट जाता है। यहाँ एक कार्यान्वयन है:
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));
इन सरल छँटाई एल्गोरिदम के अलावा, अधिक जटिल छँटाई एल्गोरिदम भी हैं। उदाहरण के लिए, मर्ज सॉर्ट करें। ध्यान देने योग्य दो बातें हैं। सबसे पहले, रिकर्सन यहाँ हमारे बचाव में आता है। दूसरा, एल्गोरिथम की जटिलता अब द्विघात नहीं है, जैसा कि हम अभ्यस्त हैं। इस एल्गोरिथ्म की जटिलता लघुगणकीय है। इसे इस प्रकार लिखा जाता है 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। यदि कोई छोटा मान नहीं मिलता है, तो
ल के बराबर हो जाता है
pivot। फिर हम
Rमार्कर को तब तक घुमाते हैं जब तक हमें से छोटा मान नहीं मिल जाता
pivot। यदि कोई बड़ा मान नहीं मिलता है, तो
Rके बराबर हो जाता है
pivot। अगला, यदि
Lमार्कर मार्कर से पहले है
Rया इसके साथ मेल खाता है, तो हम तत्वों को तत्व
Lसे कम होने पर तत्वों को स्वैप करने का प्रयास करते हैं।
Rफिर हम
L1 से दाईं ओर शिफ्ट होते हैं, और हम
Rबाईं ओर 1 से शिफ्ट होते हैं। जब
Lमार्कर मार्कर से आगे बढ़ता है
R, तो इसका मतलब है कि स्वैपिंग पूर्ण हो गई है: छोटे मान के बाईं ओर हैं
pivot, बड़े मान के दाईं ओर हैं
pivot. इसके बाद, हम एक ही तरह की विधि को पुनरावर्ती रूप से उप-सरणियों पर कॉल करते हैं - अनुभाग की शुरुआत से दाएं मार्कर को क्रमबद्ध करने के लिए, और बाएं मार्कर से अनुभाग के अंत तक क्रमबद्ध करने के लिए। शुरुआत से दाएं मार्कर तक क्यों? क्योंकि पुनरावृत्ति के अंत में, यह पता चला है कि दायां मार्कर बाएं भाग की सीमा बनने के लिए पर्याप्त चलता है। यह एल्गोरिथ्म सरल छँटाई की तुलना में अधिक जटिल है, इसलिए इसे स्केच करना सबसे अच्छा है।
pivotकागज की एक सफेद शीट लें और लिखें: 4 2 6 7 3. फिर बीच में, यानी संख्या 6 के नीचे लिखें। इसे सर्कल करें। 4 के नीचे लिखो
Lऔर 3 के नीचे लिखो
R। 6 से 4 कम, 6 से
L2 कम
pivot।
Lpivot, शर्त के अनुसार। फिर से 4 2 6 7 3 लिखें। 6 (
pivot) पर गोला बनाएं और
Lउसके नीचे रखें। अब
Rमार्कर को हिलाएं। 3, 6 से छोटा है, इसलिए
Rमार्कर को 3 पर रखें। चूँकि 3, 6 (
pivot) से छोटा है, हम a करते हैं
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। हम a नहीं करते हैं
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 तत्व है। हालांकि, हम छँटाई के लिए
Lभाग को 4 से मार्कर तक भेजते हैं ।
Rहम एक चुनते हैं
pivotऔर फिर से शुरू करते हैं :) पहली नज़र में, ऐसा लग सकता है कि यदि आप बहुत सारे मान जोड़ते हैं तो बराबर
pivot, तो आप एल्गोरिथम तोड़ देंगे। लेकिन ऐसा नहीं है। आप मुश्किल संयोजनों के बारे में सोच सकते हैं और कागज पर खुद को समझा सकते हैं कि सब कुछ सही है और आश्चर्य होता है कि इस तरह की सरल क्रियाएं इस तरह के एक विश्वसनीय छँटाई तंत्र को लागू करती हैं। केवल नकारात्मक पक्ष यह है कि यह छँटाई एल्गोरिथ्म स्थिर नहीं है। क्योंकि एक स्वैप समान तत्वों के सापेक्ष क्रम को बदल सकता है यदि उनमें से एक का सामना
pivotदूसरे तत्व से पहले भाग में स्वैप करने से पहले होता है
pivot।
तल - रेखा
ऊपर, हमने जावा में कार्यान्वित सॉर्टिंग एल्गोरिदम के "सज्जनों" के सेट को देखा। एल्गोरिदम आम तौर पर उपयोगी होते हैं, दोनों एक लागू परिप्रेक्ष्य से और सीखने के तरीके के बारे में सोचने के मामले में। कुछ सरल हैं, कुछ अधिक जटिल हैं। स्मार्ट लोगों ने कुछ के लिए अपने शोध प्रबंधों का बचाव किया। दूसरों के लिए, उन्होंने अत्यधिक मोटी पुस्तकें लिखीं। मुझे उम्मीद है कि पूरक सामग्री आपको और भी अधिक सीखने में मदद करेगी, क्योंकि यह लेख केवल एक सिंहावलोकन है जो पहले से ही महत्वपूर्ण हो गया है। और इसका उद्देश्य एक छोटा सा परिचय देना है।
यदि आप "ग्रोकिंग एल्गोरिथम " पढ़ते हैं तो आप एल्गोरिदम का परिचय भी पा सकते हैं । मुझे जैक ब्राउन की प्लेलिस्ट भी पसंद है:
AQA Decision 1 1.01 Tracing an Algorithm । मनोरंजन के लिए, आप
छँटाई के समय एल्गोरिथम विज़ुअलाइज़ेशन देख सकते हैं।Visualgo.net ।
GO TO FULL VERSION