DSA – Arrays, Searching & Sorting

Array Basics

• Ordered, fixed-size collection of same-type elements, contiguous in memory

• Index range: $0 \rightarrow n-1$ (direct access via subscript $[]$)

• Size formula: $N = U<em>b - L</em>b + 1$

Core Array Operations

• Traversal: visit each element once (read, print, process)

• Insertion at position $a$
  • If $a = U<em>b + 1$ → append • Else shift right from $U</em>b \rightarrow a$, place new item, update $U_b$

• Deletion at position $b$
  • Save $A[b]$, shift left $b+1 \rightarrow U<em>b$, decrement $U</em>b$

2-D & Multidimensional Arrays

• Represented as rows & columns: $A[i][j]$

• Memory layouts
  • Row-major: store rows consecutively
  • Column-major: store columns consecutively

• Ragged arrays: rows of unequal length

Searching Algorithms

Linear (Sequential) Search

• Scan from first to last element

• Works on unsorted arrays

• Complexity: best $1$, worst $N$, average $\tfrac{N+1}{2}$ ⇒ $O(N)$

Binary Search

• Requires sorted array

• Repeatedly halve search range using middle element

• Complexity: worst $\lceil\log_2 N\rceil$ ⇒ $O(\log N)$

Sorting Algorithms

Selection Sort

• Repeatedly select smallest remaining element and swap into place

• $O(N^2)$ comparisons, $O(N)$ swaps

Bubble Sort

• Repeatedly swap adjacent out-of-order pairs; large items “sink”

• Worst $O(N^2)$ comparisons & swaps; best (already sorted) $O(N)$

Insertion Sort

• Insert each element into its correct place within sorted prefix

• Worst $O(N^2)$, best $O(N)$ (nearly sorted)

Merge Sort (Divide & Conquer)

• Recursively split array, sort halves, merge

• Time $O(N \log N)$, extra space $O(N)$

Quick Sort (Divide, Partition, Conquer)

• Partition around pivot into < pivot, = pivot, > pivot; recurse on subarrays

• Average $O(N \log N)$; worst $O(N^2)$ (e.g., already sorted with bad pivot)

Radix Sort

• Non-comparison sort; group items by each digit/character from least to most significant

• Time $O(d\,N)$ for $d$ digits; high memory overhead, suited to linked lists

Complexity Comparison (Key Results)

• Quadratic sorts (Selection, Bubble, Insertion): $O(N^2)$ worst-case; only viable for small $N$ or nearly sorted data

• Efficient comparison sorts: Merge & Quick (avg) $O(N \log N)$, Heap sort (not detailed) also $O(N \log N)$

• Search: use Binary search on sorted data for $O(\log N)$ speed; otherwise Linear search $O(N)$