సార్టింగ్ మరియు సెర్చింగ్
వేగంగా కనుగొనడం
Google search చేసినప్పుడు, ఫలితాలు ఒక సెకను లోపు కనిపిస్తాయి - అత్యంత relevant నుండి తక్కువ relevant వరకు rank చేయబడి. Netflix సినిమాలు recommend చేసేటప్పుడు, మీరు ఎంత ఇష్టపడతారో ఆధారంగా వేలాది titles sort చేస్తుంది. ప్రతి వేగవంతమైన lookup మరియు ranked list వెనుక ఒక sorting లేదా searching algorithm ఉంటుంది.
Sorting ఎందుకు ముఖ్యం
Sorted data శక్తివంతమైన data. List క్రమంలో ఉంటే:
- Binary search ఉపయోగించి సమర్థవంతంగా search చేయవచ్చు.
- Duplicates కనుగొనడం - అవి పక్కపక్కనే ఉంటాయి.
- Top-N ఫలితాలు కనుగొనడం - మొదటి N items తీసుకోండి.
- Datasets merge చేయడం - రెండు sorted lists కలపడం unsorted వాటి కంటే చాలా వేగం.
Bubble Sort - సరళం కానీ నెమ్మది
Bubble sort పదేపదే list ద్వారా నడుస్తుంది, పక్కపక్కన ఉన్న items ను పోల్చి తప్పు క్రమంలో ఉంటే swap చేస్తుంది. పెద్ద విలువలు చివరికి "bubble" అవుతాయి.
[5, 3, 8, 1, 2]
↕
[3, 5, 8, 1, 2] → 5 మరియు 3 swap
[3, 5, 1, 8, 2] → 8 మరియు 1 swap
[3, 5, 1, 2, 8] → 8 మరియు 2 swap
... swaps అవసరం లేనంత వరకు కొనసాగించండి
Time complexity: O(n²). 1,000,000 items తో? ట్రిలియన్ comparisons. AI workloads కి practical కాదు.
Bubble sort దాదాపు n² comparisons తీసుకుంటే, వెయ్యి items తో పోలిస్తే మిలియన్ items sort చేయడం ఎంత నెమ్మదిగా ఉంటుంది? (1,000,000)² vs (1,000)² నిష్పత్తి ఆలోచించండి. అది మిలియన్ రెట్లు నెమ్మది - కేవలం వెయ్యి రెట్లు ఎక్కువ data కోసం.
Merge Sort - Divide and Conquer
Merge sort list ను రెండుగా split చేసి, ప్రతి సగాన్ని sort చేసి, రెండు sorted halves ను merge చేస్తుంది.
[5, 3, 8, 1, 2, 7, 4, 6]
split
[5, 3, 8, 1] [2, 7, 4, 6]
split split
[5, 3] [8, 1] [2, 7] [4, 6]
↓ ↓ ↓ ↓
[3, 5] [1, 8] [2, 7] [4, 6]
merge merge
[1, 3, 5, 8] [2, 4, 6, 7]
merge
[1, 2, 3, 4, 5, 6, 7, 8]
Time complexity: O(n log n) - నాటకీయంగా వేగం. మిలియన్ items కి ట్రిలియన్ బదులు దాదాపు 20 మిలియన్ comparisons.
Python built-in sort Timsort ఉపయోగిస్తుంది - merge sort మరియు insertion sort కలిపిన hybrid algorithm. Tim Peters 2002 లో కనుగొన్నారు, ఇప్పుడు Python, Java మరియు Android లో ఉపయోగిస్తారు. ఇది ఇప్పటికే partially sorted ఉన్న real-world data పై బాగా పనిచేయడానికి ప్రత్యేకంగా రూపొందించబడింది.
Discussion
Sign in to join the discussion