ડેટા સ્ટ્રક્ચર્સ અને એલ્ગોરિધમ્સ — કોર ટેકનિકલ રિવિઝનData Structures & Algorithms Core Revision
ટાઈમ કોમ્પ્લેક્સિટી, સોર્ટિંગ સ્ટેબિલિટી, બાઈનરી સર્ચ ટ્રી, માસ્ટર થિયરમ, અને ગ્રાફ એલ્ગોરિધમ્સ (Dijkstra, Kruskal).Time & space complexities, sorting stability, BST & AVL trees, heaps, Master theorem, and graph algorithms.
📚 ડેટા સ્ટ્રક્ચર્સ અને એલ્ગોરિધમ્સ (DSA) — કોર ટેકનિકલ રિવિઝન ગાઈડ
🎯 ટેકનિકલ પરીક્ષા સંદર્ભ: GPSC ICT ઓફિસર (વર્ગ-૨), આસિસ્ટન્ટ એન્જિનિયર (કમ્પ્યુટર/IT), ગૌણ સેવા હેડ ક્લાર્ક/પ્રોગ્રામર અને ટેકનિકલ CBT પરીક્ષાઓ માટે DSA એક અનિવાર્ય વિષય છે. ટાઈમ કોમ્પ્લેક્સિટી, સોર્ટિંગ સ્ટેબિલિટી, ટ્રી અને ગ્રાફ એલ્ગોરિધમ્સમાંથી સીધા કન્સેપ્ચ્યુઅલ પ્રશ્નો પૂછાય છે.
🔗 ૧. લિનિયર ડેટા સ્ટ્રક્ચર્સ અને ટાઈમ કોમ્પ્લેક્સિટી
| ડેટા સ્ટ્રક્ચર | Access ટાઈમ | Search ટાઈમ | Insertion (ઉમેરવું) | Deletion (કાઢી નાખવું) | મુખ્ય ટેકનિકલ ગુણધર્મ |
|---|---|---|---|---|---|
| Array (એરે) | $O(1)$ | $O(n)$ | $O(n)$ | $O(n)$ | સળંગ મેમરી એલોકેશન; ઇન્ડેક્સિંગ સૌથી ઝડપી. |
| Singly Linked List | $O(n)$ | $O(n)$ | Head: $O(1)$ | Tail: $O(n)$ | Head: $O(1)$ | Middle: $O(n)$ | ડાયનેમિક સાઈઝ, પોઇન્ટર માટે વધારાની સ્પેસ જોઈએ. |
| Doubly Linked List | $O(n)$ | $O(n)$ | બંને છેડે $O(1)$ | આપેલ નોડ માટે $O(1)$ | આગળ અને પાછળ બંને તરફ ટ્રાવર્સલ શક્ય; ૨ પોઇન્ટર જરૂરી. |
| Stack (સ્ટેક - LIFO) | $O(n)$ | $O(n)$ | Push: $O(1)$ | Pop: $O(1)$ | લાસ્ટ ઇન ફર્સ્ટ આઉટ; ફંક્શન કોલ અને DFS માં વપરાય. |
| Queue (ક્યૂ - FIFO) | $O(n)$ | $O(n)$ | Enqueue: $O(1)$ | Dequeue: $O(1)$ | ફર્સ્ટ ઇન ફર્સ્ટ આઉટ; CPU શેડ્યુલિંગ અને BFS માં વપરાય. |
🌳 ૨. બાઈનરી સર્ચ ટ્રી (BST) અને બેલેન્સ્ડ ટ્રી
- બાઈનરી સર્ચ ટ્રી (BST): ડાબું સબટ્રી < રૂટ (Root) < જમણું સબટ્રી.
- ઇન-ઓર્ડર ટ્રાવર્સલ (Inorder): BST નું ઇન-ઓર્ડર ટ્રાવર્સલ હંમેશાં ચડતા ક્રમમાં (Ascending Sorted) પરિણામ આપે છે!
- શોધ/ઉમેરવાનો સમય: સરેરાશ $O(log n)$; પરંતુ જો ટ્રી એકતરફી (Skewed) હોય તો વર્સ્ટ કેસ $O(n)$ થાય.
- ટ્રી બનાવવાનો નિયમ: જો ઇન-ઓર્ડર + પ્રી-ઓર્ડર અથવા ઇન-ઓર્ડર + પોસ્ટ-ઓર્ડર આપેલા હોય, તો જ યુનિક (અનન્ય) બાઈનરી ટ્રી બનાવી શકાય.
- AVL ટ્રી: સેલ્ફ-બેલેન્સિંગ બાઈનરી સર્ચ ટ્રી. પ્રત્યેક નોડનો બેલેન્સ ફેક્ટર $BF = |h_L - h_R| leq 1$ હોવો ફરજિયાત છે. રોટેશન: LL, RR, LR, RL. તમામ ઓપરેશન્સ ગેરંટેડ $O(log n)$ સમયમાં થાય.
- હીપ (Binary Heap): કમ્પલીટ બાઈનરી ટ્રી. Max-Heap માં પેરેન્ટ નોડ બાળકો કરતાં મોટો હોય; Min-Heap માં પેરેન્ટ સૌથી નાનો હોય. રૂટ એક્સેસ $O(1)$ સમયમાં થાય.
⚠️ GPSC ટેકનિકલ ટ્રેપ — સોર્ટિંગ સ્ટેબિલિટી અને વર્સ્ટ-કેસ ભૂલો:
- સ્ટેબલ સોર્ટિંગ (Stable Sort): જો સમાન કિંમત ધરાવતા એલિમેન્ટ્સ પોતાનો મૂળ ક્રમ જાળવી રાખે તો તેને સ્ટેબલ કહેવાય.
• સ્ટેબલ સોર્ટ્સ: Bubble Sort, Insertion Sort, Merge Sort.
• અનસ્ટેબલ સોર્ટ્સ (Unstable): Quick Sort, Heap Sort, Selection Sort. - Quick Sort ટ્રેપ: ક્વિક સોર્ટનો સરેરાશ સમય $O(n log n)$ છે, પરંતુ જો એરે પહેલેથી જ સોર્ટ થયેલો હોય અને પ્રથમ એલિમેન્ટ પીવટ લેવાય તો વર્સ્ટ કેસ $O(n^2)$ થાય છે!
- Merge Sort: વર્સ્ટ કેસમાં પણ $O(n log n)$ જ સમય લે છે, પરંતુ તેને $O(n)$ જેટલી વધારાની મેમરી (Auxiliary Space) જોઈએ છે.
📊 ૩. સોર્ટિંગ એલ્ગોરિધમ્સ માસ્ટર સરખામણી કોષ્ટક
| એલ્ગોરિધમ | શ્રેષ્ઠ સમય (Best) | સરેરાશ સમય (Average) | વર્સ્ટ કેસ (Worst) | સ્પેસ (Space) | સ્ટેબલ? | મુખ્ય કાર્યપદ્ધતિ |
|---|---|---|---|---|---|---|
| Bubble Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | હા (Yes) | પાસપાસેના ઘટકોની અદલાબદલી. |
| Selection Sort | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | ના (No) | સૌથી નાનો ઘટક શોધી આગળ મૂકવો ($O(n)$ સ્વેપ). |
| Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | હા (Yes) | લગભગ સોર્ટ થયેલા એરે માટે સૌથી ઝડપી. |
| Merge Sort | $O(n log n)$ | $O(n log n)$ | $O(n log n)$ | $O(n)$ | હા (Yes) | ડિવાઈડ એન્ડ કોન્કર; બાહ્ય સોર્ટિંગ માટે શ્રેષ્ઠ. |
| Quick Sort | $O(n log n)$ | $O(n log n)$ | $O(n^2)$ | $O(log n)$ | ના (No) | પીવટ આધારિત વિભાજન; પ્રેક્ટિકલમાં સૌથી ઝડપી. |
| Heap Sort | $O(n log n)$ | $O(n log n)$ | $O(n log n)$ | $O(1)$ | ના (No) | In-place મેમરી સાથે ગેરંટેડ $O(n log n)$. |
🌐 ૪. ગ્રાફ એલ્ગોરિધમ્સ અને મિનિમમ સ્પેનિંગ ટ્રી (MST)
| એલ્ગોરિધમ | પદ્ધતિ (Paradigm) | ટાઈમ કોમ્પ્લેક્સિટી | નેગેટિવ વજન? | મુખ્ય ઉપયોગ અને વિશેષતા |
|---|---|---|---|---|
| BFS | ક્યૂ આધારિત ટ્રાવર્સલ | $$O(V + E)$$ | લાગુ નથી | અનવેઈટેડ ગ્રાફમાં ટૂંકો રસ્તો શોધવા; લેવલ ઓર્ડર. |
| DFS | સ્ટેક / રિકર્ઝન | $$O(V + E)$$ | લાગુ નથી | ટોપોલોજીકલ સોર્ટિંગ (DAG) અને સાયકલ ડિટેક્શન. |
| ડિજિક્સ્ટ્રા (Dijkstra) | ગ્રીડી (Min-Heap) | $$O((V + E) log V)$$ | ના (નિષ્ફળ જાય) | માત્ર ધન વજનવાળા ગ્રાફ માટે સિંગલ સોર્સ શોર્ટેસ્ટ પાથ. |
| બેલમેન-ફોર્ડ (Bellman-Ford) | ડાયનેમિક પ્રોગ્રામિંગ | $$O(V imes E)$$ | હા (સાયકલ પકડે) | નેગેટિવ વજન ધરાવતા ગ્રાફ અને નેગેટિવ સાયકલ પકડવા. |
| ફ્લોઈડ-વોર્શલ (Floyd-Warshall) | ડાયનેમિક પ્રોગ્રામિંગ | $$O(V^3)$$ | હા | ઓલ-પેયર્સ (તમામ જોડીઓ વચ્ચે) શોર્ટેસ્ટ પાથ મેટ્રિક્સ. |
| ક્રુસ્કલ (Kruskal) | ગ્રીડી (DSU) | $$O(E log E)$$ | હા | મિનિમમ સ્પેનિંગ ટ્રી; એજ (Edges) નું વૈશ્વિક સોર્ટિંગ. |
| પ્રિમ્સ (Prim's) | ગ્રીડી (Priority Queue) | $$O(E log V)$$ | હા | મિનિમમ સ્પેનિંગ ટ્રી; ઘટ્ટ (Dense) ગ્રાફ માટે આદર્શ. |
⚡ માસ્ટર પ્રમેય (Master Theorem) શોર્ટકટ:
રિકરન્સ સંબંધ: $$T(n) = aT(n/b) + Theta(n^k log^p n)$$ માટે $log_b a$ ની સરખામણી $k$ સાથે કરો:
- જો $log_b a > k$ હોય, તો $T(n) = Theta(n^{log_b a})$ થાય.
- જો $log_b a = k$ અને $p = 0$ હોય, તો $T(n) = Theta(n^k log n)$ થાય (Merge sort: $2T(n/2) + O(n) o O(n log n)$).
- જો $log_b a < k$ હોય, તો $T(n) = Theta(n^k log^p n)$ થાય.
📚 પ્રમાણિત સંદર્ભ સાહિત્ય
- Introduction to Algorithms (CLRS): Cormen, Leiserson, Rivest, Stein.
- Data Structures and Algorithms Made Easy: Narasimha Karumanchi.
- GATE Computer Science & IT Solved Papers: Made Easy.
📚 Data Structures & Algorithms — Complete Technical & Exam Revision Guide
🎯 Technical Exam Relevance: Crucial for GPSC ICT Officer (Class 2), Assistant Engineer (IT/Computer), GSSSB Assistant Programmer, and CBT Technical screening papers. Questions focus heavily on asymptotic bounds, sorting stability, tree traversals, and graph algorithm paradigms.
🔗 1. Linear Data Structures & Asymptotic Complexities
| Data Structure | Access Time | Search Time | Insertion (Head / Tail) | Deletion | Key Technical Property |
|---|---|---|---|---|---|
| Array | $O(1)$ | $O(n)$ | $O(n)$ | $O(n)$ | Contiguous memory allocation; cache-friendly. |
| Singly Linked List | $O(n)$ | $O(n)$ | Head: $O(1)$ | Tail: $O(n)$ or $O(1)$ with tail pointer | Head: $O(1)$ | Middle: $O(n)$ | Dynamic size, non-contiguous nodes; $O(n)$ extra pointer space. |
| Doubly Linked List | $O(n)$ | $O(n)$ | $O(1)$ at both ends | $O(1)$ given direct node pointer | Bidirectional traversal; requires 2 pointer references per node. |
| Stack (LIFO) | $O(n)$ | $O(n)$ | Push: $O(1)$ | Pop: $O(1)$ | Applications: Function call stack, Infix to Postfix conversion, DFS. |
| Queue (FIFO) | $O(n)$ | $O(n)$ | Enqueue: $O(1)$ | Dequeue: $O(1)$ | Applications: CPU scheduling, BFS traversal, printer spooling. |
🌳 2. Trees, Binary Search Trees & Balanced Trees
- Binary Search Tree (BST): Left Subtree < Root < Right Subtree.
- Inorder Traversal: Traverses BST in strictly ascending sorted order!
- Search/Insert/Delete Time: Best/Avg: $O(log n)$; Worst (skewed tree): $O(n)$.
- Binary Tree Reconstruction: A unique binary tree can be uniquely reconstructed if given Inorder + Preorder OR Inorder + Postorder. (Preorder + Postorder cannot guarantee uniqueness).
- AVL Tree: Strictly height-balanced BST where Balance Factor $BF = |h_L - h_R| leq 1$ for all nodes.
- Guarantees $O(log n)$ time for Search, Insert, and Delete.
- Rotations to rebalance: Single (LL, RR) and Double (LR, RL).
- Binary Heap & Priority Queue: Complete binary tree stored in array.
- For node at index $i$: Left Child $= 2i + 1$, Right Child $= 2i + 2$, Parent $= lfloor (i - 1)/2 floor$.
- Root access: $O(1)$. Insert & Extract-Min/Max: $O(log n)$. Heapify array of $n$ elements takes $O(n)$ time!
⚠️ GPSC Exam Traps — Sorting Stability & Worst-Case Complexities:
- Sorting Stability: A sort is stable if duplicate keys maintain their original relative order.
• Stable Sorts: Bubble Sort, Insertion Sort, Merge Sort, Counting Sort, Radix Sort.
• Unstable Sorts: Quick Sort, Heap Sort, Selection Sort. - Quick Sort Trap: Average time is $O(n log n)$, but worst-case time is $O(n^2)$ (when pivot is repeatedly smallest/largest element, e.g., already sorted array with first element as pivot).
- Merge Sort vs Quick Sort: Merge Sort guarantees $O(n log n)$ even in worst case, but requires $O(n)$ auxiliary space. Quick Sort is in-place ($O(log n)$ stack space) and faster in practical CPU caches.
📊 3. Comprehensive Sorting Algorithms Master Matrix
| Algorithm | Best Time | Average Time | Worst Time | Space Complexity | Stable? | Key Paradigm / Use Case |
|---|---|---|---|---|---|---|
| Bubble Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Repeated adjacent swapping; educational use. |
| Selection Sort | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | No | Minimizes total memory writes ($O(n)$ swaps). |
| Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Adaptive; fastest for small ($n le 15$) or nearly sorted arrays. |
| Merge Sort | $O(n log n)$ | $O(n log n)$ | $O(n log n)$ | $O(n)$ | Yes | Divide-and-conquer; optimal for external sorting and linked lists. |
| Quick Sort | $O(n log n)$ | $O(n log n)$ | $O(n^2)$ | $O(log n)$ | No | Partitioning around pivot; standard library default. |
| Heap Sort | $O(n log n)$ | $O(n log n)$ | $O(n log n)$ | $O(1)$ | No | In-place $O(1)$ extra space with guaranteed $O(n log n)$. |
🌐 4. Graph Algorithms & Minimum Spanning Trees (MST)
| Algorithm | Paradigm | Time Complexity | Negative Edges? | Primary Purpose & Behavior |
|---|---|---|---|---|
| BFS (Breadth First) | Queue-based traversal | $$O(V + E)$$ | N/A | Shortest path in unweighted graphs; level-order exploration. |
| DFS (Depth First) | Stack / Recursion | $$O(V + E)$$ | N/A | Topological sorting (DAG), cycle detection, connected components. |
| Dijkstra's Algorithm | Greedy (Min-Heap) | $$O((V + E) log V)$$ | No (Fails!) | Single-source shortest path for non-negative weights. |
| Bellman-Ford Algorithm | Dynamic Programming | $$O(V imes E)$$ | Yes (Detects cycles) | Single-source shortest path; detects negative weight cycles. |
| Floyd-Warshall | Dynamic Programming | $$O(V^3)$$ | Yes (No neg cycles) | All-pairs shortest path matrix. |
| Kruskal's Algorithm | Greedy with DSU | $$O(E log E)$$ | Yes | Minimum Spanning Tree; sorts all edges globally; ideal for sparse graphs. |
| Prim's Algorithm | Greedy (Min-Heap) | $$O(E log V)$$ | Yes | Minimum Spanning Tree; grows connected tree from a vertex; ideal for dense graphs. |
⚡ Master Theorem Shortcut for Divide & Conquer:
For recurrence relation: $$T(n) = aT(n/b) + Theta(n^k log^p n)$$
- Compare $log_b a$ with $k$:
- If $log_b a > k$: $$T(n) = Theta(n^{log_b a})$$
- If $log_b a = k$:
• If $p > -1$: $$T(n) = Theta(n^k log^{p+1} n)$$
• If $p = -1$: $$T(n) = Theta(n^k log log n)$$ - If $log_b a < k$: $$T(n) = Theta(n^k log^p n)$$
📚 Authoritative Reference Books
- Introduction to Algorithms (CLRS): Cormen, Leiserson, Rivest, Stein (MIT Press).
- Data Structures and Algorithms Made Easy: Narasimha Karumanchi.
- GATE Computer Science & Information Technology: Made Easy / ACE Academy.
હવે પોતાની કસોટી કરોTest yourself next
દરેક પરીક્ષાનો મોક 1 ફ્રી છે, સાઇન અપ વગર, અને દરેક પ્રશ્નની ગુજરાતી અને અંગ્રેજી સમજૂતી છે.Mock 1 of every exam is free, with no sign-up, and every question has a Gujarati and English explanation.