Quicksort అనేది ఒక విభజన-ఆధిపత్య సార్టింగ్ విధానం, ఇది pivot ను ఎంచుకుంటుంది, దానిని కంటే చిన్నవి మరియు పెద్దవిగా భాగాలుగా విభజిస్తుంది, ఆపై ప్రతి వైపు పునరావృతంగా సార్టులు చేస్తుంది. సగటు O(n log n), చెత్త సందర్భం O(n²).
భాగీకరణ పివోట్ను దాని చివరి సార్టు చేసిన స్థానానికి ఉంచుతుంది; ఎడమవైపు అన్నీ చిన్నవి, కుడివైపు అన్నీ పెద్దవి. రెండు వైపులా పునరావృతంగా చేయండి.
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²) చెత్త సందర్భాన్ని ఎందుకు కారణమవుతుందో అర్థం చేసుకోవడం ఒక ముఖ్య పాఠం నేర్పిస్తుంది: సగటు మరియు చెత్త సందర్భం తీవ్రంగా భిన్నంగా ఉంటాయి.
ఇది ఈ సూక్ష్మమైన చిక్కు కారణంగా ఒక ఇష్టమైన ఇంటర్వ్యూ విషయం.