छँटाई उन बुनियादी क्रियाओं में से एक है जो हम वस्तुओं पर करते हैं। बचपन में भी, बच्चों को उनके सोचने के कौशल को विकसित करने के लिए क्रमबद्ध करना सिखाया जाता है। कंप्यूटर और सॉफ्टवेयर कोई अपवाद नहीं हैं। जावा में सॉर्टिंग एल्गोरिदम की एक विशाल विविधता है । मेरा सुझाव है कि आप जांचें कि वे क्या हैं और वे कैसे काम करते हैं। क्या होगा अगर किसी दिन एक साक्षात्कार में आपसे उनमें से किसी एक के बारे में पूछा जाए?
ल के बराबर हो जाता है
परिचय
छँटाई तत्व एल्गोरिदम की श्रेणियों में से एक है जिसे एक डेवलपर को पता होना चाहिए। जब मैं स्कूल में था तब अगर कंप्यूटर साइंस को गंभीरता से नहीं लिया जाता था, तो आज के छात्रों को सॉर्टिंग एल्गोरिदम को लागू करने और समझने में सक्षम होना चाहिए। बुनियादी एल्गोरिदम, सबसे सरल, लूप का उपयोग करके कार्यान्वित किया जाता है। स्वाभाविक रूप से, तत्वों के संग्रह को क्रमबद्ध करने के लिए, जैसे कि एक सरणी, आपको किसी तरह संग्रह से गुजरने की आवश्यकता है। उदाहरण के लिए: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
से बड़ा है । इसका क्या मतलब है जब हम संग्रह के साथ काम करने के लिए एक इंडेक्स का उपयोग कर रहे हैं (जैसा कि सरणी के मामले में है)? इसका अर्थ यह है कि यदि इंडेक्स वाला तत्व इंडेक्स ( ) वाले तत्व से बड़ा है, तो तत्वों को स्वैप किया जाना चाहिए। स्थान बदलने के विभिन्न तरीके हैं। लेकिन हम एक ऐसी तकनीक का उपयोग करेंगे जो सरल, समझने योग्य और याद रखने में आसान हो: b
a > b
b
array[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
फिर हम
L
1 से दाईं ओर शिफ्ट होते हैं, और हम
R
बाईं ओर 1 से शिफ्ट होते हैं। जब
L
मार्कर मार्कर से आगे बढ़ता है
R
, तो इसका मतलब है कि स्वैपिंग पूर्ण हो गई है: छोटे मान के बाईं ओर हैं
pivot
, बड़े मान के दाईं ओर हैं
pivot
. इसके बाद, हम एक ही तरह की विधि को पुनरावर्ती रूप से उप-सरणियों पर कॉल करते हैं - अनुभाग की शुरुआत से दाएं मार्कर को क्रमबद्ध करने के लिए, और बाएं मार्कर से अनुभाग के अंत तक क्रमबद्ध करने के लिए। शुरुआत से दाएं मार्कर तक क्यों? क्योंकि पुनरावृत्ति के अंत में, यह पता चला है कि दायां मार्कर बाएं भाग की सीमा बनने के लिए पर्याप्त चलता है। यह एल्गोरिथ्म सरल छँटाई की तुलना में अधिक जटिल है, इसलिए इसे स्केच करना सबसे अच्छा है।
pivot
कागज की एक सफेद शीट लें और लिखें: 4 2 6 7 3. फिर बीच में, यानी संख्या 6 के नीचे लिखें। इसे सर्कल करें। 4 के नीचे लिखो
L
और 3 के नीचे लिखो
R
। 6 से 4 कम, 6 से
L
2 कम
pivot
।
L
pivot
, शर्त के अनुसार। फिर से 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
. मार्कर
L
3 पर है।
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
।