జావాస్క్రిప్ట్‌లో క్విక్‌సర్ట్ అల్గోరిథం

త్వరిత క్రమబద్ధీకరణ అంటే ఏమిటి?

త్వరిత క్రమబద్ధీకరణ అల్గోరిథం డివైడ్ మరియు కాంక్వెర్ విధానాన్ని అనుసరిస్తుంది. ఇది కొన్ని షరతుల ఆధారంగా మూలకాలను చిన్న భాగాలుగా విభజిస్తుంది మరియు విభజించబడిన చిన్న భాగాలపై విధమైన కార్యకలాపాలను నిర్వహిస్తుంది.

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

క్రమబద్ధీకరణ అంటే ఏమిటి?

క్రమబద్ధీకరణ అనేది మరేమీ కాదు, మూలకాలను మనకు కావలసిన క్రమంలో అమర్చడం. మీ పాఠశాల లేదా కళాశాల రోజుల్లో మీరు దీనిని ఎదుర్కొన్నారు. చిన్న నుండి పెద్ద (ఆరోహణ) లేదా పెద్ద నుండి చిన్న (అవరోహణ) వరకు సంఖ్యలను అమర్చడం వంటివి మనం ఇప్పటి వరకు చూశాము మరియు సార్టింగ్ అంటారు.

జావాస్క్రిప్ట్‌లో డిఫాల్ట్ సార్టింగ్

ముందు చెప్పినట్లుగా, జావాస్క్రిప్ట్ ఉంది క్రమబద్ధీకరించు () . [5,3,7,6,2,9] వంటి కొన్ని మూలకాల శ్రేణితో ఒక ఉదాహరణ తీసుకుందాం మరియు ఈ శ్రేణి మూలకాలను ఆరోహణ క్రమంలో క్రమబద్ధీకరించాలనుకుంటున్నాము. కాల్ చేయండి క్రమబద్ధీకరించు () అంశాల శ్రేణిపై మరియు ఇది శ్రేణి మూలకాలను ఆరోహణ క్రమంలో క్రమబద్ధీకరిస్తుంది.

కోడ్:

 var items = [5,3,7,6,2,9]; console.log(items.sort()); //prints [2, 3, 5, 6, 7, 9] 

జావాస్క్రిప్ట్‌లో డిఫాల్ట్ సార్ట్‌ () కంటే క్విక్ సార్ట్‌ని ఎంచుకోవడానికి కారణం ఏమిటి

సార్ట్ () మనకు కావలసిన ఫలితాన్ని ఇచ్చినప్పటికీ, శ్రేణి మూలకాలను క్రమబద్ధీకరించే విధానంతో సమస్య ఉంది. జావాస్క్రిప్ట్ ఉపయోగాలలో డిఫాల్ట్ క్రమబద్ధీకరణ () చొప్పించే క్రమం ద్వారా Chrome యొక్క V8 ఇంజిన్ మరియు విధమైన విలీనం ద్వారా మొజిల్లా ఫైర్ ఫాక్స్ మరియు సఫారి .

కానీ, మీరు పెద్ద సంఖ్యలో ఎలిమెంట్‌లను క్రమబద్ధీకరించాల్సిన అవసరం ఉన్నట్లయితే ఇది సరిపోదు. కాబట్టి, పెద్ద డేటాసెట్ కోసం క్విక్ సార్ట్‌ని ఉపయోగించడం పరిష్కారం.

కాబట్టి, పూర్తిగా అర్థం చేసుకోవడానికి, త్వరిత క్రమబద్ధీకరణ ఎలా పనిచేస్తుందో మీరు తెలుసుకోవాలి మరియు దానిని ఇప్పుడు వివరంగా చూద్దాం.

త్వరిత క్రమబద్ధీకరణ అంటే ఏమిటి?

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

  1. ముందుగా పిలవబడే ఒక మూలకాన్ని ఎంచుకోండి ఇరుసు మూలకం.
  2. తరువాత, ఎంచుకున్న పివోట్ ఎలిమెంట్‌తో అన్ని అర్రే ఎలిమెంట్‌లను సరిపోల్చండి మరియు పివోట్ ఎలిమెంట్ కంటే తక్కువ ఎలిమెంట్‌లు దాని ఎడమ వైపున మరియు పివోట్ కంటే కుడి వైపున ఉండే విధంగా వాటిని అమర్చండి.
  3. చివరగా, పైవట్ మూలకానికి ఎడమ మరియు కుడి వైపు మూలకాలపై అదే కార్యకలాపాలను నిర్వహించండి.

కాబట్టి, ఇది త్వరిత క్రమం యొక్క ప్రాథమిక రూపురేఖ. త్వరిత క్రమబద్ధీకరణ చేయడానికి ఒక్కొక్కటిగా అనుసరించాల్సిన దశలు ఇక్కడ ఉన్నాయి.

QuickSort ఎలా పని చేస్తుంది

  1. మొదట కనుగొనండి 'ఇరుసు' శ్రేణిలోని మూలకం.
  2. శ్రేణి యొక్క మొదటి మూలకం వద్ద ఎడమ పాయింటర్‌ను ప్రారంభించండి.
  3. శ్రేణి యొక్క చివరి మూలకం వద్ద కుడి పాయింటర్‌ను ప్రారంభించండి.
  4. ఎలిమెంట్ పాయింటింగ్‌ను ఎడమ పాయింటర్‌తో సరిపోల్చండి మరియు అది పివోట్ ఎలిమెంట్ కంటే తక్కువగా ఉంటే, ఎడమ పాయింటర్‌ను కుడి వైపుకు తరలించండి (1 ఎడమ ఇండెక్స్‌కు 1 జోడించండి). ఎడమ వైపు మూలకం పివోట్ మూలకం కంటే ఎక్కువ లేదా సమానంగా ఉండే వరకు దీన్ని కొనసాగించండి.
  5. ఎలిమెంట్ పాయింట్‌ని కుడి పాయింటర్‌తో పోల్చండి మరియు అది పివోట్ ఎలిమెంట్ కంటే ఎక్కువగా ఉంటే, కుడి పాయింటర్‌ను ఎడమ వైపుకు తరలించండి (1 ను కుడి ఇండెక్స్‌కు తీసివేయండి). కుడి వైపు మూలకం పివోట్ మూలకం కంటే తక్కువగా లేదా సమానంగా ఉండే వరకు దీన్ని కొనసాగించండి.
  6. ఎడమ పాయింటర్ కుడి పాయింటర్ కంటే తక్కువగా లేదా సమానంగా ఉందో లేదో తనిఖీ చేయండి, ఆపై ఈ పాయింటర్ల స్థానాల్లో మూలకాలను చూసింది.
  7. ఎడమ పాయింటర్‌ను పెంచండి మరియు కుడి పాయింటర్‌ను తగ్గించండి.
  8. ఎడమ పాయింటర్ సూచిక ఇప్పటికీ కుడి పాయింటర్ సూచిక కంటే తక్కువగా ఉంటే, ఆ ప్రక్రియను పునరావృతం చేయండి; లేకపోతే ఎడమ పాయింటర్ యొక్క సూచికను తిరిగి ఇవ్వండి.

కాబట్టి, ఈ దశలను ఉదాహరణతో చూద్దాం. మనం క్రమబద్ధీకరించాల్సిన మూలకాల శ్రేణిని పరిశీలిద్దాం [5,3,7,6,2,9].

పివోట్ మూలకాన్ని నిర్ణయించండి

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

త్వరిత క్రమబద్ధీకరణకు సంబంధించిన దశలు ఇక్కడ ఉన్నాయి, ఇవి ఉదాహరణతో చూపబడతాయి [5,3,7,6,2,9].

దశ 1: మధ్య మూలకం వలె ఇరుసును నిర్ణయించండి. కాబట్టి, 7 కీలకమైన అంశం.

దశ 2: వరుసగా మొదటి మరియు చివరి మూలకాలుగా ఎడమ మరియు కుడి పాయింటర్‌లను ప్రారంభించండి. కాబట్టి, ఎడమ పాయింటర్ సూచిస్తుంది 5 ఇండెక్స్ 0 వద్ద మరియు కుడి పాయింటర్ సూచించబడుతోంది 9 సూచిక 5 వద్ద.

దశ 3: పివోట్ మూలకంతో ఎడమ పాయింటర్‌లోని మూలకాన్ని సరిపోల్చండి. నుండి, 5<6 shift left pointer to the right to index 1.

దశ 4: ఇప్పుడు, ఇంకా 3 6 ఎడమ పాయింటర్‌ను పెంచడం ఆపండి మరియు ఇప్పుడు ఎడమ పాయింటర్ ఇండెక్స్ 2 వద్ద ఉంది.

దశ 5: ఇప్పుడు, కుడి పాయింటర్ వద్ద విలువను పివోట్ మూలకంతో సరిపోల్చండి. 9> 6 నుండి కుడి పాయింటర్‌ను ఎడమవైపుకు తరలించండి. ఇప్పుడు 2 గా<6 stop moving the right pointer.

దశ 6: ఎడమ మరియు కుడి పాయింటర్‌లలో ఉన్న రెండు విలువలను ఒకదానితో ఒకటి మార్చుకోండి.

దశ 7: రెండు పాయింటర్‌లను మరో అడుగుకు తరలించండి.

దశ 8: 6 = 6 నుండి, పాయింటర్‌లను మరో దశకు తరలించి, ఎడమ పాయింటర్ కుడి పాయింటర్‌ను దాటినప్పుడు ఆగి, ఎడమ పాయింటర్ యొక్క ఇండెక్స్‌ను తిరిగి ఇవ్వండి.

కాబట్టి, పై విధానం ఆధారంగా ఇక్కడ, మూలకాలను మార్చుకోవడం మరియు పైన పేర్కొన్న దశలలో పేర్కొన్న విధంగా శ్రేణిని విభజించడం కోసం మేము కోడ్ రాయాలి.

జావాస్క్రిప్ట్‌లో రెండు సంఖ్యలను మార్చుకోవడానికి కోడ్:

 function swap(items, leftIndex, rightIndex){ var temp = items[leftIndex]; items[leftIndex] = items[rightIndex]; items[rightIndex] = temp; } 

పై దశల్లో పేర్కొన్న విధంగా విభజనను నిర్వహించడానికి కోడ్:

 function partition(items, left, right) { var pivot = items[Math.floor((right + left) / 2)], //middle element i = left, //left pointer j = right; //right pointer while (i <= j) { while (items[i] pivot) { j--; } if (i <= j) { swap(items, i, j); //swap two elements i++; j--; } } return i; } 

పునరావృత ఆపరేషన్ చేయండి

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

కాబట్టి, ఎడమ శ్రేణి మరియు కుడి శ్రేణిలోని అన్ని మూలకాలు క్రమబద్ధీకరించబడే వరకు త్వరిత క్రమబద్ధీకరణ జరుగుతుంది.

గమనిక: త్వరిత క్రమబద్ధీకరణ ఒకే శ్రేణిలో జరుగుతుంది మరియు ప్రక్రియలో కొత్త శ్రేణులు సృష్టించబడవు.

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

 function quickSort(items, left, right) { var index; if (items.length > 1) { index = partition(items, left, right); //index returned from partition if (left  

త్వరిత క్రమబద్ధీకరణ కోడ్‌ను పూర్తి చేయండి:

 var items = [5,3,7,6,2,9]; function swap(items, leftIndex, rightIndex){ var temp = items[leftIndex]; items[leftIndex] = items[rightIndex]; items[rightIndex] = temp; } function partition(items, left, right) { var pivot = items[Math.floor((right + left) / 2)], //middle element i = left, //left pointer j = right; //right pointer while (i <= j) { while (items[i] pivot) { j--; } if (i 1) { index = partition(items, left, right); //index returned from partition if (left < index - 1) { //more elements on the left side of the pivot quickSort(items, left, index - 1); } if (index < right) { //more elements on the right side of the pivot quickSort(items, index, right); } } return items; } // first call to quick sort var sortedArray = quickSort(items, 0, items.length - 1); console.log(sortedArray); //prints [2,3,5,6,7,9] 

గమనిక: త్వరిత క్రమబద్ధీకరణ సమయ సంక్లిష్టతతో నడుస్తుంది ఓ (న్లోగ్న్).