Sorting और Searching
चीज़ें तेज़ी से ढूँढना
Google पर search करो तो results एक second से कम में आते हैं - relevance से ranked। Netflix films recommend करता है तो हज़ारों titles आपकी पसंद से sort करता है। हर fast lookup और ranked list के पीछे sorting या searching algorithm है।
Sorting क्यों ज़रूरी है
Sorted data powerful data है। List order में आ जाए तो:
- Binary search से efficiently ढूँढ सकते हो।
- Duplicates ढूँढना आसान - एक-दूसरे के बगल में होंगे।
- Top-N results - बस पहले N items उठा लो।
- Datasets merge करना - दो sorted lists combine करना unsorted से काफ़ी तेज़ है।
Bubble Sort - Simple लेकिन Slow
Bubble sort list में बार-बार adjacent items compare करता है और गलत order में हों तो swap करता है। बड़ी values "bubble" करके end पर पहुँचती हैं।
[5, 3, 8, 1, 2]
↕
[3, 5, 8, 1, 2] → swapped 5 and 3
[3, 5, 1, 8, 2] → swapped 8 and 1
[3, 5, 1, 2, 8] → swapped 8 and 2
... जब तक कोई swap ज़रूरी न हो
Time complexity: O(n²) - 1,000 items पर 10 लाख comparisons। 10 लाख items पर? एक trillion। AI workloads के लिए practical नहीं।
अगर bubble sort ~n² comparisons लेता है, तो 10 लाख items sort करना 1,000 items से कितना slow होगा? Ratio सोचो: (1,000,000)² vs (1,000)²। 10 लाख गुना slow - सिर्फ 1,000 गुना ज़्यादा data होने से।
Merge Sort - Divide and Conquer
Merge sort smarter approach अपनाता है: list आधी तोड़ो, दोनों halves 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) - बहुत तेज़। 10 लाख items पर ~2 करोड़ comparisons, trillion नहीं। यही algorithms real AI systems possible बनाते हैं।
Python का built-in sort Timsort इस्तेमाल करता है - merge sort और insertion sort का hybrid। Tim Peters ने 2002 में बनाया और अब Python, Java, और Android में इस्तेमाल होता है। Real-world partially sorted data पर बेहतर perform करने के लिए designed है।
Discussion
Sign in to join the discussion