डेटा स्ट्रक्चर: यूनिट 3 नोट्स

टॉपिक्स

1. Searching

   • Linear Search
   • Binary Search
   • Index Sequential Search

2. Sorting

   • Insertion Sort
   • Selection Sort
   • Bubble Sort
   • Heap Sort
   • Merge Sort
   • Quick Sort
   • Radix Sort

3. Hashing

   • Hash Function
   • Collision Resolution Techniques

Searching

• Searching क्या है?
  • यह किसी दिए गए आइटम की स्थिति को खोजने की प्रक्रिया है।
  • Internal Search: जब डेटा मुख्य मेमोरी में हो।
  • External Search: जब डेटा फ़ाइलों या डिस्क में हो।

Searching Techniques

1. Linear Search

   • हर तत्व का एक-एक करके मुकाबला करें।
   • समय जटिलता: O(n)
   • उदाहरण:
     • डेटा: [1, 2, 3, 4, 5]
     • खोजें: 3
       • 1 (नहीं)
       • 2 (नहीं)
       • 3 (मिला)

2. Binary Search

   • केवल सॉर्टेड एरे पर कार्य करता है।
   • समय जटिलता: O(log n)
   • प्रक्रिया:
     • मध्य तत्व खोजें और तुलना करें।
     • यदि मध्य तत्व छोटा है, तो दाएं भाग पर जाएं।
     • यदि बड़ा है, तो बाएं भाग पर जाएं।

3. Index Sequential Search

   • समूहों में विभाजित करें और क्रमिक रूप से खोजें।

Sorting

Sorting Techniques

1. Insertion Sort

   • एक सॉर्टेड और एक अनसॉर्टेड भाग में विभाजित करें।
   • समय जटिलता: O(n²)

2. Selection Sort

   • सबसे छोटे तत्व को खोजें और उसे सॉर्टेड भाग में डालें।
   • समय जटिलता: O(n²)

3. Bubble Sort

   • बबल की तरह सबसे बड़े तत्व को ऊपर लाते हैं।
   • समय जटिलता: O(n²)

4. Merge Sort

   • डिवाइड और कांकर के सिद्धांत पर आधारित।
   • समय जटिलता: O(n log n)

5. Quick Sort

   • पिवट तत्व का उपयोग करें और विभाजित करें।
   • समय जटिलता: O(n log n) (सर्वश्रेष्ठ स्थिति O(n²))

6. Radix Sort

   • डी और एन के आधार पर।
   • समय जटिलता: D × N + M
   • D = डिजिट्स की संख्या, N = तत्वों की संख्या, M = नंबर सिस्टम का बेस।

Hashing

• Hash Table: एक एरे जो विशेष इंडेक्स में डेटा को मैप करता है।
• Collision: जब दो कुंजी एक ही स्थिति पर मैप होती हैं।

Collision Resolution Techniques

1. Open Addressing
   • Linear Probing: H(K) = H(K) + i (mod m)
   • Quadratic Probing: H(K) = H(K) + C1 * i + C2 * i² (mod m)
   • Double Hashing: H(K) = H1(K) + i * H2(K) (mod m)

Hash Function Types

1. Division Method: H(K) = K mod m
2. Mid Square Method: कुंजी का वर्ग लें और मध्य के अंश को उपयोग करें।
3. Folding Method: कुंजी के अंशों को जोड़ें।

निष्कर्ष

• सभी मुख्य तकनीकों को अच्छी तरह से समझना और अभ्यास करना महत्वपूर्ण है।
• परीक्षा में विशेष रूप से खोज और वर्गीकरण से संबंधित प्रश्नों पर ध्यान दें।
• हेशिंग की तकनीकें भी महत्वपूर्ण हैं, विशेष रूप से कोलिज़न के साथ।