सॉर्टिंग हे मूलभूत ऑपरेशन्सपैकी एक आहे जे आपण ऑब्जेक्ट्सवर करतो. अगदी बालपणातही, मुलांची विचार करण्याची क्षमता विकसित होत असताना वर्गीकरण करायला शिकवले जाते. संगणक आणि सॉफ्टवेअर अपवाद नाहीत. Java मध्ये अनेक प्रकारचे सॉर्टिंग अल्गोरिदम आहेत . मी सुचवितो की ते काय आहेत आणि ते कसे कार्य करतात ते तपासा. एखाद्या दिवशी मुलाखतीत तुम्हाला त्यापैकी एकाबद्दल विचारले गेले तर?
परिचय
घटकांची क्रमवारी लावणे ही अल्गोरिदमच्या श्रेणींपैकी एक आहे जी विकसकाला माहित असणे आवश्यक आहे. मी शाळेत असताना संगणक विज्ञानाला एकेकाळी गांभीर्याने घेतले नाही, तर आजचे विद्यार्थी वर्गीकरण अल्गोरिदम लागू करण्यास आणि समजून घेण्यास सक्षम असले पाहिजेत. मूलभूत अल्गोरिदम, सर्वात सोपा, फॉर लूप वापरून लागू केले जातात. साहजिकच, अॅरेसारख्या घटकांच्या संग्रहाची क्रमवारी लावण्यासाठी, तुम्हाला कसा तरी संग्रहातून जावे लागेल. उदाहरणार्थ:
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)" आहे. या नोटेशनला "बिग ओ" किंवा "असिम्प्टोटिक वर्तन" असेही म्हणतात. पण तुम्ही फक्त लक्षात ठेवू शकता "
सर्वात सोपा क्रमवारी अल्गोरिदम (बबल क्रमवारी)
समजा आपल्याकडे अॅरे आहे आणि आपण त्याद्वारे पुनरावृत्ती करू शकतो. मस्त. आता चढत्या क्रमाने क्रमवारी लावण्याचा प्रयत्न करूया. याचा अर्थ काय? याचा अर्थ असा की दोन घटक दिलेले (उदाहरणार्थ, 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));
जसे आपण पाहू शकता, घटक खरोखर स्वॅप केले गेले. array[i] < array[i-1]आम्ही अनुक्रमणिका 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). हे वर्गीकरण अल्गोरिदम टोनी होरे यांनी विकसित केले होते. विशेष म्हणजे, सोव्हिएत युनियनमध्ये राहत असताना त्यांनी याचा शोध लावला, जिथे त्यांनी मॉस्को विद्यापीठात मशीन भाषांतराचा अभ्यास केला आणि एक रशियन-इंग्रजी वाक्यांश पुस्तक विकसित केले. इतकेच काय, Java मध्ये या अल्गोरिदमची अधिक जटिल आवृत्ती वापरते 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.
Lमग आपण 1 ने उजवीकडे सरकतो आणि
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. 3 हे 6 पेक्षा कमी आहे, म्हणून मार्कर 3 वर ठेवा. 3 हे 6 ( )
Rपेक्षा कमी असल्याने आम्ही एक करतो . परिणाम लिहा: 4 2 3 7 6. वर्तुळ 6, कारण ते अजूनही आहे . मार्कर 3 वर आहे. मार्कर 6 वर आहे. लक्षात ठेवा की आम्ही मार्कर पुढे जाईपर्यंत हलवतो . पुढील क्रमांकावर जा . येथे मला दोन शक्यता एक्सप्लोर करायच्या आहेत: 1) ज्या केसमध्ये उपांत्य संख्या 7 आहे आणि 2) केस जेथे 1 आहे, 7 नाही.
जर उपांत्य संख्या 1 असेल तर: मार्कर 1 वर हलवा , कारण आपण हलवू शकतो जोपर्यंत
pivotswappivotLRLRLLLLमार्कर पेक्षा लहान संख्येकडे निर्देश करतो
pivot.
Rपरंतु आपण 6 वरून पुढे जाऊ शकत नाही , कारण जर
Rमार्कर पेक्षा मोठ्या संख्येकडे निर्देश करतो तरच आपण R हलवू शकतो
pivot. आम्ही कार्य करत नाही
swap, कारण 1 6 पेक्षा कमी आहे. वर्तमान स्थिती लिहा: 4 2 3 1 6. वर्तुळ 6 (
pivot).
Lसरकते
pivotआणि हालचाल थांबवते.
Rहलत नाही. आम्ही स्वॅप करत नाही. शिफ्ट
Lआणि
Rएका स्थितीत.
R1 खाली मार्कर लिहा.
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.
तळ ओळ
वर, आम्ही Java मध्ये लागू केलेल्या सॉर्टिंग अल्गोरिदमचा "सज्जन" संच पाहिला. लागू केलेल्या दृष्टीकोनातून आणि विचार कसा करावा हे शिकण्याच्या दृष्टीने अल्गोरिदम सामान्यतः उपयुक्त असतात. काही सोपे आहेत, काही अधिक क्लिष्ट आहेत. हुशार लोकांनी काहींसाठी त्यांच्या प्रबंधांचा बचाव केला. इतरांसाठी, त्यांनी खूप जाड पुस्तके लिहिली. मला आशा आहे की पूरक सामग्री तुम्हाला आणखी शिकण्यास मदत करेल, कारण हा लेख फक्त एक विहंगावलोकन आहे जो आधीच वजनदार असल्याचे दिसून आले आहे. आणि त्याचा उद्देश एक छोटासा परिचय देणे हा आहे.
तुम्ही "ग्रोकिंग अल्गोरिदम " वाचल्यास तुम्हाला अल्गोरिदमची ओळख देखील मिळेल . मला जॅक ब्राउनची प्लेलिस्ट देखील आवडते:
AQA निर्णय 1 1.01 ट्रेसिंग अॅन अल्गोरिदम . मनोरंजनासाठी, तुम्ही
क्रमवारी करताना अल्गोरिदम व्हिज्युअलायझेशन पाहू शकता.visualgo.net _
GO TO FULL VERSION