ఒక ప్రోగ్రామింగ్ పద్ధతిగా Quicksort

1960 లో, K. A. హోర్, సమాచారం వేగంగా విభజన కోసం ఒక పద్ధతి అభివృద్ధి అత్యంత ప్రసిద్ధ మారింది. నేడు ఇది విస్తృతంగా సానుకూల లక్షణాలు చాలా ఉన్నాయి అని, ప్రోగ్రామింగ్ ఉపయోగిస్తారు: ఇది సాధారణ సందర్భాలలో ఉపయోగించవచ్చు, అది అదనపు మెమరీ లో ఒక చిన్న పెరుగుదల, మరియు జాబితాలు వివిధ రకాల అనుకూలంగా అమలు సులభం అవసరం. ఉపయోగించి పని తప్పులను చాలా అనుమతించింది మరియు దానిని కొంతవరకు అస్థిర ఉంది: కానీ కలిగి Quicksort, నష్టాలు కూడా ఉన్నాయి.

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

Quicksort ఇది ప్రతిచోటా చూడవచ్చు, సర్వసాధారణం. దాని ఆధారంగా పద్ధతి TList.Sort, అన్ని వెర్షన్లు డెల్ఫీ, సమయం లైబ్రరీ ఫంక్షన్ అది సి లో పూర్తి, qsort ++ పట్టింది (1 తప్ప) ప్రస్తుతం అమలు చేయబడుతుంది.

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

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

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

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