Skip to content

AEiE0702 Sorting, searching, and graphs

Internal versus external sorting

Type Meaning
Internal sort Entire data fits in main memory
External sort Data too large for main memory; secondary storage involved

Sorting algorithms and comparison table

Algorithm Core idea Best-known exam cue Time complexity Stable? In-place?
Insertion sort Insert each item into sorted prefix Good for small or nearly sorted data \(O(n^2)\) average/worst Yes Yes
Selection sort Repeatedly select minimum Few swaps \(O(n^2)\) No in common form Yes
Exchange / interchange sort Compare each position with later positions and swap out-of-order pairs Non-adjacent pair exchanges \(O(n^2)\) No Yes
Bubble sort Repeatedly swap out-of-order adjacent items Largest/smallest item “bubbles” per pass \(O(n^2)\) Yes in ordinary form Yes
Merge sort Divide, sort halves, merge External sorting friendly \(O(n\log n)\) Yes No
Radix sort Sort by digits/positions Non-comparison sort Depends on digits, often \(O(d(n+k))\) Yes in stable form Extra space
Shell sort Gapped insertion sorts Improves insertion sort Depends on gap sequence, commonly subquadratic Usually no Yes
Heap sort Use heap priority queue Guaranteed \(O(n\log n)\) \(O(n\log n)\) No Yes

Recognition traps:

  • Merge sort is stable and \(O(n\log n)\) but needs extra memory.
  • Heap sort is \(O(n\log n)\) and in-place but not stable.
  • Binary search is not a sorting algorithm.
  • Radix sort is not comparison-based in the usual sense.

Heap as priority queue

  • A heap supports quick access to highest-priority or lowest-priority item.
  • In a max-heap, parent key is at least as large as each child key.
  • Insert and delete-root operations are typically \(O(\log n)\).

Search techniques

Method Condition Complexity cue
Sequential / linear search Works on unsorted sequence \(O(n)\)
Binary search Requires sorted order for correctness \(O(\log n)\) with efficient midpoint access
Tree search Depends on tree structure Balanced BST about \(O(\log n)\); skewed can become \(O(n)\)

Mandatory conditions:

  • Sorted order is required for binary-search correctness.
  • Logarithmic running time additionally assumes efficient midpoint access, normally an array; it is not obtained on a plain singly linked list.
  • Binary search is defined by repeatedly halving a sorted interval, not by the vague phrase “no unnecessary comparisons.”

Graph concepts

  • A graph consists of vertices and edges.
  • Undirected graph edges have no direction.
  • Directed graph edges have direction and are called arcs.
  • Representation methods include adjacency matrix and adjacency list.
Representation Strength Weakness
Adjacency matrix Fast edge lookup Uses \(O(V^2)\) space
Adjacency list Space-efficient for sparse graphs Edge lookup may be slower

DFS and BFS

Traversal Data structure used Key feature
DFS Stack or recursion Goes deep before backtracking
BFS Queue Explores level by level

Recognition cues:

  • BFS gives shortest path in number of edges in an unweighted graph.
  • DFS is useful for connectivity, topological-style explorations, and cycle-related reasoning.

Shortest-path algorithms

  • Greedy algorithms make locally optimal choices hoping for a global optimum.
  • Dijkstra's algorithm is a greedy shortest-path algorithm for graphs with nonnegative edge weights.
  • It repeatedly fixes the currently closest unsettled vertex.

Trap:

  • Dijkstra is not valid unchanged for negative edge weights.

Sorting-searching-graph examples

  1. If the dataset is already almost sorted, insertion sort is often efficient in practice.
  2. If the array is sorted and random-access indexing exists, binary search gives logarithmic search time.
  3. For unweighted shortest-hop search, BFS is the natural choice.

AEiE0702 revision box

  • Internal sort fits in RAM; external sort relies on secondary storage.
  • Merge sort and heap sort are both \(O(n\log n)\), but only merge sort is stable.
  • Binary search requires sorted random-access data.
  • BFS uses queue; DFS uses stack or recursion.
  • Dijkstra assumes nonnegative edge weights.