త్వరిత సార్టింగ్ ఎలా కనిపిస్తుంది, మరియు దాని యొక్క చెత్త సందర్భం ఏమిటి?

Question

IT Interview Practice · Accepted Answer

**Quicksort** అనేది ఒక విభజన-ఆధిపత్య సార్టింగ్ విధానం, ఇది **pivot** ను ఎంచుకుంటుంది, దానిని కంటే చిన్నవి మరియు పెద్దవిగా భాగాలుగా విభజిస్తుంది, ఆపై ప్రతి వైపు పునరావృతంగా సార్టులు చేస్తుంది. సగటు **O(n log n)**, చెత్త సందర్భం **O(n²)**. ## ఆలోచన భాగీకరణ పివోట్‌ను దాని చివరి సార్టు చేసిన స్థానానికి ఉంచుతుంది; ఎడమవైపు అన్నీ చిన్నవి, కుడివైపు అన్నీ పెద్దవి. రెండు వైపులా పునరావృతంగా చేయండి. ## ఉదాహరణ ```python def quicksort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] # pick a pivot left = [x for x in arr if x < pivot] # smaller mid = [x for x in arr if x == pivot] # equal right = [x for x in arr if x > pivot] # larger return quicksort(left) + mid + quicksort(right) quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8] ``` (ఆచరణలో మెమోరీని ఆదా చేయడానికి ఇన్-ప్లేస్ భాగీకరణ ఉపయోగించబడుతుంది.) ## సంక్లిష్టత | సందర్భం | సమయం | కారణం | |---------|------|--------| | Best/Average | O(n log n) | సమతుల్య భాగీకరణలు | | Worst | O(n²) | ఇప్పటికే చెడ్డ పివోట్‌తో సార్టు చేయబడింది | ఇన్-ప్లేస్ విరేచన O(log n) స్టాక్ స్పేస్ ఉపయోగిస్తుంది. ## ఎప్పుడు ఉపయోగించాలి / ఆపదలు సాధారణంగా **ఆచరణలో వేగవంతమైనది** కాష్ బంధుత్వం మరియు నీచ ఓవర్‌హెడ్ కారణంగా, మరియు ఇది ఇన్-ప్లేస్. **యాదృచ్ఛిక** లేదా **మూడు-మధ్యస్థ** పివోట్‌తో O(n²) చెత్త సందర్భం నివారించబడుతుంది. **స్థిరమైనది కాదు**. ## ఇది ఎందుకు ముఖ్యమైనది విరేచన అనేది చాలా ప్రామాణిక లైబ్రరీలలో డిఫాల్ట్, ఇది అద్భుత సగటు-కేస్ వేగం మరియు తక్కువ మెమోరీ ఉపయోగం కారణంగా. పివోట్ ఎంపిక O(n²) చెత్త సందర్భాన్ని ఎందుకు కారణమవుతుందో అర్థం చేసుకోవడం ఒక ముఖ్య పాఠం నేర్పిస్తుంది: సగటు మరియు చెత్త సందర్భం తీవ్రంగా భిన్నంగా ఉంటాయి. ఇది ఈ సూక్ష్మమైన చిక్కు కారణంగా ఒక ఇష్టమైన ఇంటర్‌వ్యూ విషయం.

సందర్భం	సమయం	కారణం
Best/Average	O(n log n)	సమతుల్య భాగీకరణలు
Worst	O(n²)	ఇప్పటికే చెడ్డ పివోట్‌తో సార్టు చేయబడింది

ఆలోచన

ఉదాహరణ

సంక్లిష్టత

ఎప్పుడు ఉపయోగించాలి / ఆపదలు

ఇది ఎందుకు ముఖ్యమైనది

సంబంధిత ప్రశ్నలు