ఉద్యోగ ఇంటర్వ్యూల నుండి ప్రశ్నోత్తరాలు: జావాలోని అల్గారిథమ్స్, పార్ట్ 1

డెవలప్‌మెంట్ ప్రాజెక్ట్‌లు మీరు అనుకున్నదానికంటే చాలా తరచుగా వివిధ అల్గారిథమ్‌లను ఉపయోగిస్తాయి. ఉదాహరణకు, మనం కొంత డేటాను నిర్దిష్ట పారామితులు (నిలువు వరుసలు) ద్వారా క్రమబద్ధీకరించాలి కాబట్టి మనం ఎక్కువ శ్రమ లేకుండా డేటా ద్వారా నావిగేట్ చేయవచ్చు. కాబట్టి ఉద్యోగ ఇంటర్వ్యూ చేసే వ్యక్తి మిమ్మల్ని నిర్దిష్ట ప్రాథమిక అల్గారిథమ్ గురించి అడగడం మరియు కోడ్‌ని ఉపయోగించి దాన్ని అమలు చేసే పనిని ఇవ్వడం వింతగా ఉండదు. మరియు మీరు ఈ వెబ్‌సైట్‌లో ఉన్నందున, మీరు జావాలో వ్రాస్తున్నారని ఊహించేంత ధైర్యంగా ఉంటాను. అందుకే ఈ రోజు నేను కొన్ని ప్రాథమిక అల్గారిథమ్‌లతో మరియు జావాలో వాటిని ఎలా అమలు చేయాలో నిర్దిష్ట ఉదాహరణలతో మిమ్మల్ని పరిచయం చేసుకోవాలని సూచిస్తున్నాను. "కొన్ని" ద్వారా, నా ఉద్దేశ్యం:

1. అర్రే సార్టింగ్ అల్గారిథమ్‌ల అవలోకనం:
   • బుడగ రకం,
   • ఎంపిక రకం,
   • చొప్పించే క్రమం,
   • షెల్ క్రమబద్ధీకరణ,
   • త్వరిత క్రమబద్ధీకరణ,
   • విలీన క్రమము,
2. అత్యాశ అల్గోరిథంలు
3. పాత్‌ఫైండింగ్ అల్గోరిథంలు
   • లోతు-మొదటి శోధన
   • వెడల్పు-మొదటి శోధన
4. Dijkstra యొక్క చిన్నదైన మార్గం మొదటి అల్గోరిథం

సరే, ఇక ఆలస్యం చేయకుండా, వ్యాపారానికి దిగుదాం.

1. క్రమబద్ధీకరణ అల్గారిథమ్‌ల అవలోకనం

బబుల్ క్రమబద్ధీకరణ

ఈ క్రమబద్ధీకరణ అల్గోరిథం ప్రాథమికంగా దాని సరళతకు ప్రసిద్ధి చెందింది, అయితే ఇది చాలా నెమ్మదిగా ఉంటుంది. ఉదాహరణగా, ఆరోహణ క్రమంలో సంఖ్యల కోసం బబుల్ క్రమాన్ని పరిశీలిద్దాం. సంఖ్యల యాదృచ్ఛిక క్రమాన్ని ఊహించుకుందాం. సీక్వెన్స్ ప్రారంభం నుండి మేము ఈ సంఖ్యలపై క్రింది దశలను చేస్తాము:

• రెండు సంఖ్యలను సరిపోల్చండి;
• ఎడమవైపు సంఖ్య పెద్దగా ఉంటే, వాటిని మార్చుకోండి;
• ఒక స్థానాన్ని కుడి వైపుకు తరలించండి.

మొత్తం క్రమంలో ఈ దశలను పూర్తి చేసిన తర్వాత, మన సంఖ్యల శ్రేణి చివరిలో అతిపెద్ద సంఖ్య ఉన్నట్లు మేము కనుగొంటాము. అప్పుడు మేము సీక్వెన్స్‌పై మరొక పాస్ చేస్తాము, పైన పేర్కొన్న దశలను సరిగ్గా అమలు చేస్తాము. కానీ ఈసారి మేము జాబితాలోని చివరి మూలకాన్ని చేర్చము, ఎందుకంటే ఇది అతిపెద్ద సంఖ్య మరియు సంఖ్యలు క్రమబద్ధీకరించబడినప్పుడు అది ఖచ్చితంగా ఎక్కడ ఉండాలి. మరోసారి, మేము తదుపరి అతిపెద్ద సంఖ్యను మా శ్రేణి ముగింపుకు తరలిస్తాము. వాస్తవానికి, రెండు అతిపెద్ద సంఖ్యలు వాటి సరైన స్థానాల్లో నిలబడి ఉన్నాయని అర్థం. మళ్ళీ, అన్ని మూలకాలు అవసరమైన క్రమంలో ఉండే వరకు, వాటి స్థానాల్లో ఇప్పటికే ఉన్న మూలకాలను మినహాయించి, మేము క్రమం మీద పాస్‌లు చేస్తాము. జావా కోడ్‌లో బబుల్ సార్ట్ ఎలా అమలు చేయబడుతుందో చూద్దాం:

public class Solution {
   public static void main(String[] args) {
    int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
    bubbleSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void  bubbleSort(int[] array) {
       for(int i = array.length -1; i > 1; i--) {
         for (int j = 0; j < i; j++) { //
             if (array[j] > array[j+1]) {
                 int temp = array[j];
                 array[j] = array[j+1];
                 array[j+1] = temp;
             }
         }
       }
   }
}

మీరు గమనిస్తే, ఇక్కడ సంక్లిష్టంగా ఏమీ లేదు. ప్రతిదీ చాలా గొప్పగా అనిపిస్తుంది మరియు అది ఒక లోపం కోసం కాకపోతే - బబుల్ క్రమబద్ధీకరణ చాలా చాలా నెమ్మదిగా ఉంటుంది. మేము సమూహ లూప్‌లను కలిగి ఉన్నందున ఇది సమయ సంక్లిష్టత O(N²). మూలకాలపై బాహ్య లూప్ N సార్లు ప్రదర్శించబడుతుంది. లోపలి లూప్ కూడా N సార్లు అమలు చేయబడుతుంది. ఫలితంగా, మేము N*N, లేదా N², పునరావృతాలను పొందుతాము.

ఎంపిక క్రమబద్ధీకరణ

ఈ అల్గోరిథం బబుల్ క్రమాన్ని పోలి ఉంటుంది, కానీ ఇది కొంచెం వేగంగా పని చేస్తుంది. మళ్ళీ, ఉదాహరణగా, మనం ఆరోహణ క్రమంలో అమర్చాలనుకుంటున్న సంఖ్యల క్రమాన్ని తీసుకుందాం. ఈ అల్గోరిథం యొక్క సారాంశం ఏమిటంటే, అన్ని సంఖ్యల ద్వారా క్రమానుగతంగా పునరావృతం చేయడం మరియు చిన్న మూలకాన్ని ఎంచుకోవడం, దానిని మనం తీసుకొని ఎడమవైపు ఉన్న మూలకం (0వ మూలకం)తో మార్పిడి చేస్తాము. ఇక్కడ మేము బబుల్ క్రమాన్ని పోలిన పరిస్థితిని కలిగి ఉన్నాము, కానీ ఈ సందర్భంలో మా క్రమబద్ధీకరించబడిన మూలకం చిన్నదిగా ఉంటుంది. అందువల్ల, మూలకాల ద్వారా తదుపరి పాస్ సూచిక 1తో మూలకం నుండి ప్రారంభమవుతుంది. అన్ని మూలకాలు క్రమబద్ధీకరించబడే వరకు మేము ఈ పాస్‌లను పునరావృతం చేస్తాము. జావాలో అమలు:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {

       for (int i = 0; i < array.length-1; i++) { // An ordinary outer loop
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // Put the sorted number in the proper cell
           array[i] = array[min];
           array[min] = temp;
       }
   }
}

ఈ అల్గోరిథం బబుల్ క్రమబద్ధీకరణ కంటే మెరుగైనది, ఎందుకంటే ఇక్కడ అవసరమైన షిఫ్ట్‌ల సంఖ్య O(N²) నుండి O(N)కి తగ్గించబడింది. మేము మొత్తం జాబితా ద్వారా ఒక మూలకాన్ని నడపడం లేదు, కానీ పోలికల సంఖ్య ఇప్పటికీ O(N²)గానే ఉంది.

చొప్పించే క్రమబద్ధీకరణ

మేము ఆరోహణ క్రమంలో అమర్చాలనుకుంటున్న మరొక సంఖ్య క్రమాన్ని పరిశీలిస్తాము. ఈ అల్గోరిథం మార్కర్‌ను ఉంచడంలో ఉంటుంది, ఇక్కడ మార్కర్ యొక్క ఎడమ వైపున ఉన్న అన్ని మూలకాలు ఇప్పటికే వాటి మధ్య పాక్షికంగా క్రమబద్ధీకరించబడ్డాయి. అల్గోరిథం యొక్క ప్రతి దశలో, మూలకాలలో ఒకటి ఎంపిక చేయబడుతుంది మరియు పాక్షికంగా క్రమబద్ధీకరించబడిన క్రమంలో కావలసిన స్థానంలో ఉంచబడుతుంది. అందువలన, అన్ని అంశాలను పరిశీలించే వరకు క్రమబద్ధీకరించబడిన భాగం పెరుగుతుంది. మీరు ఇప్పటికే క్రమబద్ధీకరించబడిన మూలకాల ఉపసమితిని ఎలా పొందుతారని మరియు మార్కర్‌ను ఎక్కడ ఉంచాలో మేము ఎలా నిర్ణయిస్తాము అని మీరు ఆలోచిస్తున్నారా? కానీ మొదటి మూలకంతో కూడిన శ్రేణి ఇప్పటికే క్రమబద్ధీకరించబడింది, కాదా? జావాలో అమలును పరిశీలిద్దాం:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       insertionSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void insertionSort(int[] array) {

       for (int i = 1; i < array.length; i++) { // i is the dividing marker
           int temp = array[i]; // Make a temporary copy of the marked element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // Until a smaller element is found
               array[j] = array[j - 1]; // We shift the element to the right
               --j;
           }
           array[j] = temp;   // Insert the marked element in its proper place
       }
   }
}

ఈ రకమైన క్రమబద్ధీకరణ పైన వివరించిన వాటి కంటే మెరుగైనది, ఎందుకంటే దీనికి ఒకే O(N²) రన్నింగ్ టైమ్ ఉన్నప్పటికీ, ఈ అల్గోరిథం బబుల్ సార్ట్ కంటే రెండింతలు వేగంగా ఉంటుంది మరియు ఎంపిక క్రమబద్ధీకరణ కంటే కొంచెం వేగంగా ఉంటుంది.

షెల్ క్రమబద్ధీకరణ

ఈ క్రమబద్ధీకరణ తప్పనిసరిగా సవరించిన చొప్పించే క్రమబద్ధీకరణ. నేను దేని గురించి మాట్లాడుతున్నాను? మొదటి విషయాలు ముందు ఉంచుదాం. మనం ముందుగా విరామాన్ని ఎంచుకోవాలి. ఈ ఎంపిక చేయడానికి అనేక విధానాలు ఉన్నాయి. మేము దీని గురించి చాలా వివరంగా చెప్పము. మన శ్రేణిని సగానికి విభజించి కొంత సంఖ్యను పొందండి — ఇది మన విరామం అవుతుంది. కాబట్టి, మన శ్రేణిలో 9 మూలకాలు ఉంటే, అప్పుడు మన విరామం 9/2 = 4.5 అవుతుంది. శ్రేణి సూచికలు పూర్ణాంకాలు మాత్రమే కాబట్టి మేము భిన్న భాగాన్ని విస్మరించి 4ని పొందుతాము. మేము మా సమూహాలను రూపొందించడానికి ఈ విరామాన్ని ఉపయోగిస్తాము. ఒక మూలకం ఇండెక్స్ 0ని కలిగి ఉంటే, దాని సమూహంలోని తదుపరి మూలకం యొక్క సూచిక 0+4, అంటే 4. మూడవ మూలకం సూచిక 4+4, నాల్గవది - 8+4 మరియు మొదలైనవి కలిగి ఉంటుంది. రెండో గ్రూపులో మొదటి ఎలిమెంట్ 1,5,9... మూడు, నాల్గవ గ్రూపుల్లో కూడా ఇదే పరిస్థితి ఉంటుంది. ఫలితంగా, సంఖ్య శ్రేణి {6,3,8,8,6,9,4,11,1} నుండి మనకు నాలుగు సమూహాలు లభిస్తాయి: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} వారు సాధారణ శ్రేణిలో తమ స్థానాలను నిలుపుకుంటారు, కానీ మేము అదే సమూహంలోని సభ్యులుగా గుర్తించాము: {6,3,8,8,6,9,4,11,1} తదుపరి, చొప్పించడం క్రమబద్ధీకరణ ఈ సమూహాలకు వర్తించబడుతుంది, ఆపై అవి ఇలా కనిపిస్తాయి: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} సాధారణ శ్రేణిలో, ది సమూహాలచే ఆక్రమించబడిన సెల్‌లు అలాగే ఉంటాయి, కానీ పైన ఉన్న సమూహాల క్రమం ప్రకారం వాటి అంతర్గత క్రమం మారుతుంది: {1,3,4,8,6,9,8,11,6} శ్రేణి ఒక కొంచెం ఎక్కువ ఆర్డర్ చేయబడింది, కాదా? తదుపరి విరామం 2 ద్వారా భాగించబడుతుంది: 4/2 = 2 మనకు రెండు సమూహాలు ఉన్నాయి: I — {1,4,6,8,6} II — {3,8,9,11} సాధారణ శ్రేణిలో, మనకు ఉంది : {1,3,4,8,6,9,8,11,6} మేము రెండు సమూహాలలో చొప్పించే క్రమబద్ధీకరణ అల్గోరిథంను అమలు చేస్తాము మరియు ఈ శ్రేణిని పొందుతాము: {1,3,4,8,6,9,6, 11, 8} ఇప్పుడు మా శ్రేణి దాదాపుగా క్రమబద్ధీకరించబడింది. మేము అల్గోరిథం యొక్క తుది పునరావృత్తిని నిర్వహించాలి: మేము విరామాన్ని 2: 2/2 = 1తో భాగిస్తాము. మేము మొత్తం శ్రేణితో కూడిన సమూహాన్ని పొందుతాము: {1,3,4,8,6,9,6,11 ,8} దానిపై చొప్పించే క్రమబద్ధీకరణ అల్గారిథమ్‌ను అమలు చేయడం ద్వారా, మనకు లభిస్తుంది: {1,3,4,6,6,8,8,9,11} జావా కోడ్‌లో మనం ఈ రకానికి ఎలా జీవం పోయవచ్చో చూద్దాం:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {
       int length = array.length;
       int step = length / 2;
       while (step > 0) {
           for (int numberOfGroup = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // Shrink the interval
       }
   }
}

ప్రస్తుతానికి, Shellsort యొక్క పనితీరును వర్గీకరించడం అంత సులభం కాదు, ఎందుకంటే ఫలితాలు వేర్వేరు పరిస్థితులలో విభిన్నంగా ఉంటాయి. ప్రయోగాత్మక అంచనాలు O(N ^3/2 ) నుండి O(N ^7/6 ) వరకు ఉంటాయి.

త్వరితక్రమం

ఇది అత్యంత ప్రజాదరణ పొందిన అల్గోరిథంలలో ఒకటి, కాబట్టి దీనికి ప్రత్యేక శ్రద్ధ పెట్టడం విలువ. ఈ అల్గారిథమ్ యొక్క సారాంశం ఏమిటంటే, మూలకాల జాబితాలో పివోట్ మూలకం ఎంచుకోబడుతుంది. మేము పివోట్ మూలకానికి సంబంధించి అన్ని ఇతర మూలకాలను క్రమబద్ధీకరిస్తాము. పివోట్ మూలకం కంటే తక్కువ విలువలు ఎడమవైపు ఉన్నాయి. కుడివైపున దాని కంటే ఎక్కువ విలువలు ఉన్నాయి. తరువాత, పివోట్ మూలకాలు కుడి మరియు ఎడమ భాగాలలో కూడా ఎంపిక చేయబడతాయి మరియు అదే జరుగుతుంది: విలువలు ఈ మూలకాలకు సంబంధించి క్రమబద్ధీకరించబడతాయి. అప్పుడు పివోట్ ఎలిమెంట్స్ కొత్తగా ఏర్పడిన భాగాలలో ఎంపిక చేయబడతాయి మరియు మనం క్రమబద్ధీకరించబడిన క్రమాన్ని పొందే వరకు. ఈ అల్గోరిథం యొక్క క్రింది జావా అమలు పునరావృత్తిని ఉపయోగిస్తుంది:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       fastSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void fastSort(int[] array) {
       recursionFastSort(array, 0, array.length - 1);
   }


   public static void recursionFastSort(int[] array, int min, int max) {
       if (array.length == 0) // Condition for exiting recursion if the array length is 0
           return;

       if (min> = max) // Terminate the recursion, since there is nothing to divide
           return;


       int middle = min + (max - min) / 2; // Select the middle
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) { // Swap places
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // Make a recursive call on the elements that are less than middle
           recursionFastSort(array, min, j);

       if (max > i) // Make a recursive call on the elements larger than middle
           recursionFastSort(array, i, max);
   }
}

సందేహం లేకుండా, శీఘ్రక్రమం అల్గోరిథం అత్యంత ప్రజాదరణ పొందింది, ఎందుకంటే చాలా సందర్భాలలో ఇది ఇతరులకన్నా వేగంగా నడుస్తుంది. దీని సమయ సంక్లిష్టత O(N*logN).

విలీన క్రమాన్ని

ఈ రకం కూడా ప్రజాదరణ పొందింది. "విభజించు మరియు జయించు" సూత్రంపై ఆధారపడే అనేక అల్గారిథమ్‌లలో ఇది ఒకటి. ఇటువంటి అల్గోరిథంలు మొదట సమస్యను నిర్వహించదగిన భాగాలుగా విభజిస్తాయి (క్విక్‌సార్ట్ అటువంటి అల్గారిథమ్‌కి మరొక ఉదాహరణ). కాబట్టి ఈ అల్గోరిథం యొక్క సారాంశం ఏమిటి?

విభజించు:

శ్రేణి దాదాపు ఒకే పరిమాణంలో రెండు భాగాలుగా విభజించబడింది. ఈ రెండు భాగాలలో ప్రతి ఒక్కటి మరో రెండు భాగాలుగా విభజించబడింది మరియు సాధ్యమైనంత చిన్న విడదీయరాని భాగాలు మిగిలిపోయే వరకు. ప్రతి శ్రేణికి ఒక మూలకం ఉన్నప్పుడు, అంటే ఇప్పటికే క్రమబద్ధీకరించబడిన శ్రేణిని కలిగి ఉన్నప్పుడు మనకు అతిచిన్న అవిభాజ్య భాగాలు ఉంటాయి.

జయించు:

ఇక్కడే మేము అల్గారిథమ్‌కు దాని పేరును అందించిన ప్రక్రియను ప్రారంభిస్తాము: విలీనం. దీన్ని చేయడానికి, మేము రెండు క్రమబద్ధీకరించబడిన శ్రేణులను తీసుకొని వాటిని ఒకటిగా విలీనం చేస్తాము. ఈ సందర్భంలో, రెండు శ్రేణులలోని మొదటి మూలకాలలో చిన్నది ఫలిత శ్రేణిలో వ్రాయబడుతుంది. ఈ రెండు శ్రేణులలోని అన్ని మూలకాలు కాపీ చేయబడే వరకు ఈ ఆపరేషన్ పునరావృతమవుతుంది. అంటే, మనకు రెండు కనిష్ట శ్రేణులు {6} మరియు {4} ఉంటే, మేము వాటి విలువలను సరిపోల్చండి మరియు ఈ విలీన ఫలితాన్ని రూపొందిస్తాము: {4,6}. మేము {4,6} మరియు {2,8} శ్రేణులను క్రమబద్ధీకరించినట్లయితే, మేము మొదట 4 మరియు 2 విలువలను సరిపోల్చండి, ఆపై ఫలిత శ్రేణిలో 2 వ్రాస్తాము. ఆ తర్వాత, 4 మరియు 8 పోల్చబడతాయి మరియు మేము 4 వ్రాస్తాము. చివరగా, 6 మరియు 8 పోల్చబడతాయి. దీని ప్రకారం, మేము 6ని వ్రాస్తాము మరియు దాని తర్వాత మాత్రమే 8ని వ్రాస్తాము. ఫలితంగా, మేము క్రింది విలీన శ్రేణిని పొందుతాము: {2,4,6,8}. జావా కోడ్‌లో ఇది ఎలా కనిపిస్తుంది? ఈ అల్గారిథమ్‌ని అమలు చేయడానికి, రికర్షన్‌ని ఉపయోగించడం మాకు సౌకర్యంగా ఉంటుంది:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       testArr = mergeSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static int[] mergeSort(int[] array1) {
       int[] sortArr = Arrays.copyOf(array1, array1.length); // Array for sorting
       int[] bufferArr = new int[array1.length];// Buffer array
       return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
           return sortArr;
       }

       // Make a recursive call to get two sorted arrays:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Merge the sorted arrays:
       int firstIndex = startIndex;
       int secondIndex = middle;
       int destIndex = startIndex;
       int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
       while (firstIndex < middle && secondIndex < endIndex) {
           result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
                   ? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
       }
       while (firstIndex < middle) {
           result[destIndex++] = firstSortArr[firstIndex++];
       }
       while (secondIndex < endIndex) {
           result[destIndex++] = secondSortArr[secondIndex++];
       }
       return result;
   }
}

త్వరిత క్రమబద్ధీకరణలో వలె, మేము పునరావృత పద్ధతిని ఇంటర్మీడియట్ పద్ధతికి తరలిస్తాము, తద్వారా వినియోగదారు క్రమబద్ధీకరించబడే శ్రేణిని మాత్రమే సరఫరా చేయాలి మరియు ఏదైనా అదనపు డిఫాల్ట్ ఆర్గ్యుమెంట్‌లను అందించడం గురించి ఆందోళన చెందాల్సిన అవసరం లేదు. ఈ అల్గోరిథం క్విక్‌సార్ట్‌తో సారూప్యతలను కలిగి ఉంది మరియు ఆశ్చర్యకరంగా దాని అమలు వేగం ఒకే విధంగా ఉంటుంది: O(N*logN).

2. అత్యాశ అల్గోరిథంలు

అత్యాశ అల్గోరిథం అనేది ప్రతి దశలో స్థానికంగా సరైన నిర్ణయాలు తీసుకునే విధానం, తుది పరిష్కారం కూడా సరైనదేనని ఊహిస్తారు. ఏదైనా నిర్దిష్ట దశ/దశలో అత్యంత స్పష్టమైన మరియు తక్షణ ప్రయోజనాన్ని అందించే "ఆప్టిమల్" పరిష్కారం ఉంటుంది. ఈ అల్గారిథమ్‌ని అన్వేషించడానికి, చాలా సాధారణమైన సమస్యను తీసుకుందాం - నాప్‌సాక్ సమస్య. మీరు దొంగ అని ఒక్క క్షణం నటించండి. మీరు నాప్‌కిన్ (బ్యాక్‌ప్యాక్)తో రాత్రిపూట దుకాణంలోకి ప్రవేశించారు. మీరు దొంగిలించగల అనేక వస్తువులు మీ ముందు ఉన్నాయి. కానీ అదే సమయంలో, మీ నాప్‌కిన్ పరిమిత సామర్థ్యాన్ని కలిగి ఉంటుంది. ఇది 30 యూనిట్ల కంటే ఎక్కువ బరువును మోయదు. మీరు వీపున తగిలించుకొనే సామాను సంచికి సరిపోయే అత్యంత విలువైన వస్తువులను కూడా తీసుకెళ్లాలనుకుంటున్నారు. మీ బ్యాగ్‌లో ఏమి ఉంచాలో మీరు ఎలా నిర్ణయిస్తారు? కాబట్టి,

1. ఇంకా తీసుకోని అత్యంత ఖరీదైన వస్తువును ఎంచుకోండి.
2. నాప్‌కిన్‌లో సరిపోతే చాలు.. లేకపోతే వదిలేయండి.
3. మేము ఇప్పటికే ప్రతిదీ దొంగిలించామా? కాకపోతే, మేము దశ 1కి తిరిగి వస్తాము. అవును అయితే, మేము చేయాలనుకున్న పనిని పూర్తి చేసినందున, మేము స్టోర్ నుండి త్వరగా తప్పించుకుంటాము.

దీన్ని చూద్దాం, కానీ జావాలో. ఐటెమ్ క్లాస్ ఇలా కనిపిస్తుంది:

public class Item implements Comparable {
   private String name;
   private int weight;
   private int value;

   public Item(String name, int weight, int value) {
       this.name = name;
       this.weight = weight;
       this.value = value;
   }

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getValue() {
       return value;
   }

   @Override
   public int compareTo(Item o) {
       return this.value > o.value ? -1 : 1;
   }
}

ఇక్కడ ప్రత్యేకంగా ఏమీ లేదు: వస్తువు యొక్క లక్షణాలను నిర్వచించే మూడు ఫీల్డ్‌లు (పేరు, బరువు, విలువ). అలాగే, మీరు చూడగలిగినట్లుగా, మా వస్తువులను ధర ద్వారా క్రమబద్ధీకరించడానికి మమ్మల్ని అనుమతించడానికి పోల్చదగిన ఇంటర్‌ఫేస్ అమలు చేయబడింది. తర్వాత, మన నాప్‌సాక్‌ని సూచించే బ్యాగ్ క్లాస్‌ని చూద్దాం:

public class Bag {
   private final int maxWeight;
   private List<Item> items;
   private int currentWeight;
   private int currentValue;

   public Bag(int maxWeight) {
       this.maxWeight = maxWeight;
       items = new ArrayList<>();
       currentValue = 0;
   }

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentValue() {
       return currentValue;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

   public void addItem(Item item) {
       items.add(item);
       currentWeight += item.getWeight();
       currentValue += item.getValue();
   }
}

• maxWeight అనేది మన బ్యాక్‌ప్యాక్ సామర్థ్యం, ​​ఇది మనం వస్తువును సృష్టించినప్పుడు సెట్ చేయబడుతుంది;
• అంశాలు మన బ్యాక్‌ప్యాక్‌లోని వస్తువులను సూచిస్తాయి;
• ప్రస్తుత బరువు , ప్రస్తుత విలువ — ఈ ఫీల్డ్‌లు బ్యాక్‌ప్యాక్‌లోని అన్ని వస్తువుల ప్రస్తుత బరువు మరియు విలువను నిల్వ చేస్తాయి, వీటిని మనం addItem పద్ధతిలో జోడించినప్పుడు పెంచుతాము.

ఏమైనప్పటికీ, ఇప్పుడు అన్ని చర్యలు జరిగే తరగతికి వెళ్దాం:

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("Guitar", 7, 800));
       items.add(new Item("Iron", 6, 500));
       items.add(new Item("Tea pot", 3, 300));
       items.add(new Item("Lamp", 4, 500));
       items.add(new Item("Television", 15, 2000));
       items.add(new Item("Vase", 2, 450));
       items.add(new Item("Mixer", 2, 400));
       items.add(new Item("Blender", 3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
               ". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
}

మొదట, మేము అంశాల జాబితాను సృష్టించి, దానిని క్రమబద్ధీకరించండి. మేము 30-యూనిట్ సామర్థ్యంతో బ్యాగ్ వస్తువును సృష్టిస్తాము. తర్వాత, మేము ఐటెమ్‌లను మరియు బ్యాగ్ ఆబ్జెక్ట్‌ను ఫిల్‌బ్యాక్‌ప్యాక్ పద్ధతికి పంపుతాము, ఇది మా అత్యాశ అల్గారిథమ్ ప్రకారం నాప్‌సాక్‌ను నింపుతుంది:

public static void fillBackpack(Bag bag, List<Item> items) {
   for (Item item : items) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
            bag.addItem(item);
       }
   }
}

ఇది చాలా సులభం: మేము ధర ప్రకారం క్రమబద్ధీకరించబడిన వస్తువుల జాబితాను చూడటం ప్రారంభిస్తాము మరియు దాని సామర్థ్యం అనుమతించినట్లయితే వాటిని బ్యాగ్‌లో ఉంచడం ప్రారంభిస్తాము. తగినంత స్థలం లేనట్లయితే, అంశం దాటవేయబడుతుంది మరియు మేము జాబితా ముగింపుకు చేరుకునే వరకు మిగిలిన వస్తువులపై ప్రయాణం చేస్తూనే ఉంటాము. మేము మెయిన్‌ని అమలు చేసిన తర్వాత, మనకు లభించే కన్సోల్ అవుట్‌పుట్ ఇక్కడ ఉంది: ఇది అత్యాశతో కూడిన అల్గారిథమ్‌కు ఉదాహరణ: ప్రతి దశలో, స్థానికంగా సరైన పరిష్కారం ఎంపిక చేయబడుతుంది మరియు చివరికి, మీరు ప్రపంచవ్యాప్తంగా సరైన పరిష్కారాన్ని పొందుతారు. మా విషయంలో, ఉత్తమ ఎంపిక అత్యంత ఖరీదైన అంశం. అయితే ఇది ఉత్తమ పరిష్కారమా? మా బ్యాక్‌ప్యాక్‌ను ఇంకా ఎక్కువ మొత్తం విలువ కలిగిన వస్తువులతో నింపడానికి మా పరిష్కారాన్ని కొద్దిగా మెరుగుపరచడం సాధ్యమవుతుందని మీరు అనుకోలేదా? దీన్ని ఎలా చేయవచ్చో చూద్దాం.

public static void effectiveFillBackpack(Bag bag, List items) {
   Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
   for (Item item : items) {
       sortByRatio.put((double)item.getValue() / item.getWeight(), item);
   }

   for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
           bag.addItem(entry.getValue());
       }
   }
}

ఇక్కడ మనం మొదట ప్రతి వస్తువుకు విలువ-బరువు నిష్పత్తిని గణిస్తాము. ఇది ఇచ్చిన వస్తువు యొక్క ప్రతి యూనిట్ విలువను మాకు తెలియజేస్తుంది. ఆపై మేము మా వస్తువులను క్రమబద్ధీకరించడానికి మరియు వాటిని మా బ్యాగ్‌కి జోడించడానికి ఈ నిష్పత్తులను ఉపయోగిస్తాము. కింది వాటిని అమలు చేద్దాం:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

System.out.println("The weight of the knapsack is " + secondBag.getCurrentWeight() +
       ". The total cost of items in the knapsack is " + secondBag.getCurrentValue());

మేము ఈ కన్సోల్ అవుట్‌పుట్‌ని పొందుతాము: కొంచెం బెటర్ కదా? అత్యాశతో కూడిన అల్గోరిథం అడుగడుగునా స్థానికంగా సరైన ఎంపికను చేస్తుంది, తుది పరిష్కారం కూడా సరైనదని ఆశిస్తోంది. ఈ ఊహ ఎల్లప్పుడూ చెల్లదు, కానీ అనేక పనులకు, అత్యాశతో కూడిన అల్గారిథమ్‌లు సరైన తుది పరిష్కారాన్ని అందిస్తాయి. ఈ అల్గోరిథం యొక్క సమయ సంక్లిష్టత O(N). చాలా బాగుంది, అవునా?