వస్తువులపై మనం చేసే ప్రాథమిక కార్యకలాపాలలో సార్టింగ్ ఒకటి. బాల్యంలో కూడా, పిల్లలు వారి ఆలోచనా నైపుణ్యాలను పెంపొందించే విధంగా క్రమబద్ధీకరించడం నేర్పుతారు. కంప్యూటర్లు మరియు సాఫ్ట్‌వేర్ మినహాయింపు కాదు. జావాలో అనేక రకాల సార్టింగ్ అల్గారిథమ్‌లు ఉన్నాయి . అవి ఏమిటో మరియు అవి ఎలా పని చేస్తాయో మీరు తనిఖీ చేయాలని నేను సూచిస్తున్నాను. ఏదో ఒక ఇంటర్వ్యూలో మిమ్మల్ని వారిలో ఒకరి గురించి అడిగితే?
పరిచయం
డెవలపర్ తప్పనిసరిగా తెలుసుకోవలసిన అల్గారిథమ్‌ల వర్గాలలో సార్టింగ్ ఎలిమెంట్స్ ఒకటి. నేను పాఠశాలలో ఉన్నప్పుడు కంప్యూటర్ సైన్స్‌ను ఒకప్పుడు సీరియస్‌గా తీసుకోకపోతే, నేటి విద్యార్థులు సార్టింగ్ అల్గారిథమ్‌లను అమలు చేసి అర్థం చేసుకోగలగాలి. ప్రాథమిక అల్గారిథమ్‌లు, సరళమైనవి, లూప్‌ని ఉపయోగించి అమలు చేయబడతాయి . సహజంగానే, శ్రేణి వంటి అంశాల సేకరణను క్రమబద్ధీకరించడానికి, మీరు ఏదో ఒకవిధంగా సేకరణ ద్వారా వెళ్లాలి. ఉదాహరణకి:
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" లేదా "అసింప్టోటిక్ బిహేవియర్" అని కూడా అంటారు. కానీ నువ్వు గుర్తుపెట్టుకోగలవు"
మనకు శ్రేణి ఉందని అనుకుందాం మరియు దాని ద్వారా మనం పునరావృతం చేయవచ్చు. గొప్ప. ఇప్పుడు దానిని ఆరోహణ క్రమంలో క్రమబద్ధీకరించడానికి ప్రయత్నిద్దాం. దీని అర్థం ఏమిటి? అంటే రెండు మూలకాలు (ఉదాహరణకు, a = 6, b = 5) ఇవ్వబడినందున, మనం తప్పక క్రమాన్ని మార్చాలి aమరియు (అయితే ) కంటే ఎక్కువగా ఉంటే b. మేము సేకరణతో పని చేయడానికి సూచికను ఉపయోగిస్తున్నప్పుడు దీని అర్థం ఏమిటి (అరే విషయంలో వలె)? ఇండెక్స్ ( ) తో ఉన్న మూలకం కంటే ఇండెక్స్ aతో ఉన్న మూలకం పెద్దదిగా ఉంటే , ఆ మూలకాలు తప్పనిసరిగా మార్పిడి చేయబడాలి. స్థలాలను మార్చడానికి వివిధ మార్గాలు ఉన్నాయి. కానీ మేము సరళమైన, అర్థమయ్యే మరియు గుర్తుంచుకోవడానికి సులభమైన సాంకేతికతను ఉపయోగిస్తాము: aba > 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)మూలకం యొక్క గరిష్ట విలువ. ఈ అల్గారిథమ్‌లో ఒక లోపం ఉంది: శ్రేణిలోని కనిష్ట మరియు గరిష్ట విలువలను మనం తెలుసుకోవాలి. లెక్కింపు క్రమానికి ఇక్కడ ఒక ఉదాహరణ: nk
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మేము మూలకాలను మార్చుకోవడానికి ప్రయత్నిస్తాము . అప్పుడు మనం 1 ద్వారా కుడి వైపుకు మారాము మరియు మేము 1 ద్వారా ఎడమ వైపుకు మారుస్తాము. మార్కర్ మార్కర్‌ను దాటి కదిలినప్పుడు , మార్పిడి పూర్తయిందని అర్థం: చిన్న విలువలు ఎడమ వైపున ఉంటాయి , పెద్ద విలువలు కుడి వైపున ఉంటాయి
LRLRLRpivotpivot. దీని తరువాత, మేము అదే విధమైన పద్ధతిని సబ్‌రేలలో పునరావృతంగా పిలుస్తాము - విభాగం ప్రారంభం నుండి కుడి మార్కర్‌కు మరియు ఎడమ మార్కర్ నుండి క్రమబద్ధీకరించబడే విభాగం చివరి వరకు. ఎందుకు ప్రారంభం నుండి కుడి మార్కర్ వరకు? ఎందుకంటే పునరావృతం ముగింపులో, కుడి మార్కర్ ఎడమ భాగం యొక్క సరిహద్దుగా మారడానికి తగినంతగా కదులుతుంది. ఈ అల్గోరిథం సాధారణ సార్టింగ్ కంటే చాలా క్లిష్టంగా ఉంటుంది, కాబట్టి దీన్ని స్కెచ్ చేయడం ఉత్తమం. ఒక తెల్లటి కాగితాన్ని తీసుకొని వ్రాయండి: 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 కంటే తక్కువ, కాబట్టి
Rమార్కర్‌ను 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 ను తరలించగలము . మేము aని నిర్వహించము , ఎందుకంటే 1 6 కంటే తక్కువగా ఉంది. ప్రస్తుత పరిస్థితిని వ్రాయండి: 4 2 3 1 6. సర్కిల్ 6 ( ). ద్వారా మారుతుంది మరియు కదలకుండా ఆగిపోతుంది. కదలదు. మేము స్వాప్ చేయము. షిఫ్ట్ మరియు ఒక స్థానం ద్వారా. మార్కర్‌ను 1 కింద వ్రాయండి. మార్కర్ హద్దులు దాటి ఉంది. హద్దులు దాటినందున , మనం ఏమీ చేయము. కానీ, మేము మళ్ళీ 4 2 3 1 అని వ్రాస్తాము, ఎందుకంటే ఇది మన ఎడమ వైపు, ఇది (6) కంటే తక్కువ. కొత్తదాన్ని ఎంచుకుని , అన్నింటినీ మళ్లీ ప్రారంభించండి :)
చివరి సంఖ్య 7 అయితే:RpivotswappivotLpivotRLRRLLpivotpivot
మార్కర్‌ను 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 నిర్ణయం 1 1.01 ఒక అల్గారిథమ్ ట్రేసింగ్ . వినోదం కోసం, మీరు క్రమబద్ధీకరణలో అల్గారిథమ్ విజువలైజేషన్‌లను చూడవచ్చు
.visualgo.net .
GO TO FULL VERSION