How unit 5 is examined
Covers sorting methods, searching, hashing and indexing; Hashing and Indexing, Binary search and Quick sort carry the most marks.
Sorting: Introduction
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>
Definition. <mark>Sorting is arranging the records of a list in ascending or descending order of a key.</mark>
Key points.
- Sorted data makes searching fast, because binary search needs a sorted list and works in $O(\log n)$.
- Sorted output is easier to present, as in merit lists and directories, and brings duplicates together.
- Database merge-join, grouping and index building depend on sorted data.
- Internal sorting keeps all data in main memory; external sorting is used when data is too big for memory and works on files on disk.
| Basis | Internal sorting | External sorting |
|---|---|---|
| Data location | Whole data fits in RAM | Data lives on disk or tape |
| Data size | Small to medium | Very large |
| Access | Random access, fast | Sequential blocks, slow |
| Methods | Quick, heap, insertion | Merge-based (multiway merge) |
| Cost measure | Comparisons and swaps | Disk passes and I/O |
Answer frame. Open with the definition; list needs 1-3; close with the internal versus external table; end by saying the choice of method depends on data size.
Asked: [7 marks] (May 2019, Jun 2024) What do you mean by sorting? Describe the need for sorting. Asked: [7 marks] (Nov 2019) Differentiate between internal sorting and external sorting.
Bubble Sort
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>
Definition. <mark>Bubble sort repeatedly compares adjacent elements and swaps them if they are out of order, so the largest element bubbles to the end in each pass.</mark>
Key points.
- Pass $k$ fixes the $k$-th largest element at its final place, so $n-1$ passes are enough.
- Comparisons total $(n-1)+(n-2)+\dots+1 = \frac{n(n-1)}{2}$, giving $O(n^2)$ in best-unoptimised, average and worst cases.
- A swapped flag that stops when a pass makes no swap gives best case $O(n)$.
- It is stable and in place.
Step 1: for i = 1 to n-1
Step 2: for j = 0 to n-i-1
Step 3: if a[j] > a[j+1] then swap a[j], a[j+1]
Example. Data 35, 33, 42, 10, 14, 19, 27, 44.
| Pass | Array after pass |
|---|---|
| 1 | 33, 35, 10, 14, 19, 27, 42, 44 |
| 2 | 33, 10, 14, 19, 27, 35, 42, 44 |
| 3 | 10, 14, 19, 27, 33, 35, 42, 44 |
Answer frame. Open with the adjacent-swap principle; write the algorithm; show the pass table; close with $\frac{n(n-1)}{2}$ comparisons and $O(n^2)$.
Asked: [7 marks] (Dec 2020, Nov 2022) Explain Bubble Sort with the help of example; simulate it for 35, 33, 42, 10, 14, 19, 27, 44.
Quick sort
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>
Definition. <mark>Quick sort is a divide-and-conquer algorithm that picks a pivot, partitions the array so smaller elements lie left and larger ones right, and sorts both parts recursively.</mark>
Key points.
- Divide: choose a pivot (first, last or random) and partition; after partitioning the pivot sits at its final position.
- Conquer: apply quick sort recursively to the left and right sub-arrays; no combine step is needed.
- Partition: $i$ moves right to an element greater than the pivot, $j$ moves left to one not greater; swap them while $i<j$, then swap the pivot with $a[j]$.
- Best and average time is $O(n\log n)$ because the array splits about evenly: $T(n)=2T(n/2)+O(n)$.
- Worst time is $O(n^2)$ when the pivot is always the smallest or largest, as in a sorted array.
- It is in place, uses $O(\log n)$ stack space and is not stable.
Step 1: QuickSort(a, lo, hi): if lo < hi
Step 2: p = Partition(a, lo, hi) (pivot = a[lo])
Step 3: QuickSort(a, lo, p-1); QuickSort(a, p+1, hi)
Example. 36, 25, 32, 5, 8, 65, 38, 47, 95, pivot = first element.
| Sub-array | Pivot | Result |
|---|---|---|
| 36 25 32 5 8 65 38 47 95 | 36 | 8 25 32 5 36 65 38 47 95 |
| 8 25 32 5 | 8 | 5 8 32 25 |
| 65 38 47 95 | 65 | 47 38 65 95 |
Sorted: 5, 8, 25, 32, 36, 38, 47, 65, 95. Same method: 9, 4, 12, 6, 5, 10, 7 gives 4, 5, 6, 7, 9, 10, 12; 32, 23, 56, 78, 12, 66, 37, 93, 29, 80 gives 12, 23, 29, 32, 37, 56, 66, 78, 80, 93; 44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66 gives 11, 22, 33, 40, 44, 55, 60, 66, 77, 88, 90, 99; 55, 72, 12, 45, 88, 38, 27, 33, 91, 80 gives 12, 27, 33, 38, 45, 55, 72, 80, 88, 91.
Worst-case (Dec 2023 ii). Merge sort: $T(n)=2T(n/2)+O(n)$ gives $O(n\log n)$. Heap sort: build heap $O(n)$ plus $n$ deletions of $O(\log n)$ each gives $O(n\log n)$. Quick sort is $O(n^2)$ unless a median or random pivot balances every split.
Answer frame. Open with the definition; state pivot rule; write the algorithm; show the partition table; close with best/average $O(n\log n)$ and worst $O(n^2)$.
Asked: [7 marks] (Nov 2018, Nov 2019, Dec 2024) Sort by quick sort: 36, 25, 32, 5, 8, 65, 38, 47, 95 (also the 12-item 44, 33, 11... and 10-item 55, 72, 12... lists). Asked: [7 marks] (Jun 2020) Explain Quick sort; sort 32, 23, 56, 78, 12, 66, 37, 93, 29, 80. Asked: [9 marks] (Dec 2023) Sort 9, 4, 12, 6, 5, 10, 7 by quick sort; prove heap, merge and quick sort take $O(n\log n)$ in the worst case. Asked: [7 marks] (Dec 2025) Explain the Quick Sort algorithm with suitable example. Pitfall: Do not claim quick sort is $O(n\log n)$ in the worst case without stating the pivot condition.
Selection sort
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>
Definition. <mark>Selection sort finds the minimum of the unsorted part in each pass and swaps it into the next position.</mark>
Key points.
- Pass $i$ scans $a[i..n-1]$ for the minimum and swaps it with $a[i]$; after $n-1$ passes the list is sorted.
- Comparisons are always $(n-1)+\dots+1=\frac{n(n-1)}{2}$, so best, average and worst time are all $O(n^2)$.
- Swaps are at most $n-1$, and space is $O(1)$; it is not stable.
- Example 29, 10, 14, 37, 13 becomes 10 29 14 37 13, then 10 13 14 37 29, then 10 13 14 37 29, then 10 13 14 29 37.
Step 1: for i = 0 to n-2: min = i
Step 2: for j = i+1 to n-1: if a[j] < a[min] then min = j
Step 3: swap a[i], a[min]
Asked: [7 marks] (May 2019) Write the algorithm of selection sort and find its time complexity?
Heap sort
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>Heap sort builds a max-heap from the array and repeatedly swaps the root with the last element, shrinks the heap and heapifies.</mark>
Key points.
- Building the max-heap by heapify from the last parent costs $O(n)$.
- Each of the $n$ extractions costs $O(\log n)$, so total time is $O(n\log n)$ in best, average and worst cases.
- It sorts in place with $O(1)$ space and is not stable.
Insertion sort
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>
Definition. <mark>Insertion sort takes each element and inserts it into its correct place in the already sorted left part.</mark>
Key points.
- Take $a[i]$ as key, shift larger left elements one place right, and drop the key in the gap.
- Worst case (reverse order) needs $\frac{n(n-1)}{2}$ comparisons and shifts, so $O(n^2)$; average is also $O(n^2)$.
- Best case (sorted) needs $n-1$ comparisons, so $O(n)$; it is stable and in place.
- Example 12, 11, 13, 5, 6: 11 12 13 5 6, then 11 12 13 5 6, then 5 11 12 13 6, then 5 6 11 12 13.
Step 1: for i = 1 to n-1: key = a[i], j = i-1
Step 2: while j >= 0 and a[j] > key: a[j+1] = a[j]; j = j-1
Step 3: a[j+1] = key
Asked: [7 marks] (Nov 2019) Write the algorithm of insertion sort and find its time complexity.
Shell sort
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>
Definition. <mark>Shell sort is a generalised insertion sort that first sorts elements a gap apart and then reduces the gap to 1.</mark>
Key points.
- Far-apart elements are compared early, so each move covers many places.
- The gap starts at $\lfloor n/2 \rfloor$ and is halved each pass: for $n=8$ the gaps are 4, 2, 1.
- The gap-1 pass is plain insertion sort on a nearly sorted list, which is cheap.
- Worst case is $O(n^2)$ for the halving gaps; better gap sequences give about $O(n^{1.5})$; space is $O(1)$ and it is not stable.
Example. 35, 33, 42, 10, 14, 19, 27, 44.
| Gap | Array after the pass |
|---|---|
| 4 | 14, 19, 27, 10, 35, 33, 42, 44 |
| 2 | 14, 10, 27, 19, 35, 33, 42, 44 |
| 1 | 10, 14, 19, 27, 33, 35, 42, 44 |
Answer frame. Open with the definition and the gap rule $\lfloor n/2 \rfloor$; show the gap-4, 2, 1 table; close with the complexity and that it improves insertion sort.
Asked: [7 marks] (Jun 2023, Jun 2024) Explain shell sort algorithm and simulate it for 35, 33, 42, 10, 14, 19, 27, 44.
Merge sort
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>
Definition. <mark>Merge sort divides the list into halves, sorts each half recursively and merges the two sorted halves into one.</mark>
Key points.
- Divide at $mid=(low+high)/2$ until each part has one element, which is sorted by itself.
- Merging two sorted lists copies the smaller front element repeatedly, taking $O(n)$.
- Time is $T(n)=2T(n/2)+n$, so $O(n\log n)$ in every case; it needs $O(n)$ extra space and is stable.
- Multiway (k-way) merge sort splits data into runs, sorts each, then merges $k$ runs at a time (choosing the smallest front with a heap), needing about $\log_k n$ passes, so $O(n\log_k n)$; it suits external sorting.
<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-01" viewBox="0 0 2149 262" width="2149" height="262" role="img" aria-label="Merge sort division of 30, 56, 78, 99, 12, 43, 10, 24, 85 (leaves split further to single elements)"><style>#dsfig-u5-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-01 .t{fill:#16181D;font-weight:500}#dsfig-u5-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-01 .dot{fill:#16181D}#dsfig-u5-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-01 .ah{fill:#454C5A}#dsfig-u5-01 .ah.hi{fill:#2340B8}#dsfig-u5-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-01 .e{stroke:#B1B7C3}html.dark #dsfig-u5-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-01 .t{fill:#E6E8ED}html.dark #dsfig-u5-01 .t.inv{fill:#0F1115}html.dark #dsfig-u5-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-01 .dot{fill:#E6E8ED}html.dark #dsfig-u5-01 .ann{fill:#8FA3FF}html.dark #dsfig-u5-01 .lbl{fill:#858D9C}html.dark #dsfig-u5-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-01 .ah{fill:#B1B7C3}html.dark #dsfig-u5-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah26" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh26" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="1295.5" y1="39" x2="829.5" y2="103"/><line class="e" x1="1295.5" y1="39" x2="1761.5" y2="103"/><line class="e" x1="829.5" y1="103" x2="363.5" y2="167"/><line class="e" x1="829.5" y1="103" x2="1062.5" y2="167"/><line class="e" x1="363.5" y1="167" x2="130.5" y2="231"/><line class="e" x1="363.5" y1="167" x2="596.5" y2="231"/><line class="e" x1="1761.5" y1="103" x2="1528.5" y2="167"/><line class="e" x1="1761.5" y1="103" x2="1994.5" y2="167"/><rect class="n" x="1184" y="24" width="223" height="30" rx="8"/><text class="t" x="1295.5" y="39" dy=".35em" text-anchor="middle">30 56 78 99 12 43 10 24 85</text><rect class="n" x="764.5" y="88" width="130" height="30" rx="8"/><text class="t" x="829.5" y="103" dy=".35em" text-anchor="middle">30 56 78 99 12</text><rect class="n" x="322" y="152" width="83" height="30" rx="8"/><text class="t" x="363.5" y="167" dy=".35em" text-anchor="middle">30 56 78</text><rect class="n" x="101" y="216" width="59" height="30" rx="8"/><text class="t" x="130.5" y="231" dy=".35em" text-anchor="middle">30 56</text><circle class="n" cx="596.5" cy="231" r="17"/><text class="t" x="596.5" y="231" dy=".35em" text-anchor="middle">78</text><rect class="n" x="1033" y="152" width="59" height="30" rx="8"/><text class="t" x="1062.5" y="167" dy=".35em" text-anchor="middle">99 12</text><rect class="n" x="1708.5" y="88" width="106" height="30" rx="8"/><text class="t" x="1761.5" y="103" dy=".35em" text-anchor="middle">43 10 24 85</text><rect class="n" x="1499" y="152" width="59" height="30" rx="8"/><text class="t" x="1528.5" y="167" dy=".35em" text-anchor="middle">43 10</text><rect class="n" x="1965" y="152" width="59" height="30" rx="8"/><text class="t" x="1994.5" y="167" dy=".35em" text-anchor="middle">24 85</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Merge sort division of 30, 56, 78, 99, 12, 43, 10, 24, 85 (leaves split further to single elements)</figcaption></figure>
Example. Merging back: 30 56 then 78 gives 30 56 78; 99 12 gives 12 99; these give 12 30 56 78 99. Right half: 43 10 gives 10 43; 24 85; together 10 24 43 85. Final merge: 10, 12, 24, 30, 43, 56, 78, 85, 99. 3-way merge of (2, 9, 15), (4, 7, 20), (1, 8, 12) gives 1, 2, 4, 7, 8, 9, 12, 15, 20.
Answer frame. Open with the divide-and-conquer definition; draw the division tree; show merges upward; close with $O(n\log n)$ and $O(n)$ space. For multiway, add the $k$-run and heap merge.
Asked: [7 marks] (May 2019, Jun 2024) Explain Multiway Merge sort with an example. Asked: [7 marks] (Jun 2023) Sort 30, 56, 78, 99, 12, 43, 10, 24, 85 by using merge sort.
Radix sort
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>
Definition. <mark>Radix sort sorts numbers digit by digit, from the least significant digit to the most, using a stable sort such as bucket distribution at each digit.</mark>
Key points.
- Numbers go into 10 buckets (0-9) by the current digit and are collected in bucket order; no comparisons are made.
- Passes equal the number of digits $d$ of the largest key, and time is $O(d(n+b))$ for base $b$.
- Example 170, 45, 75, 90, 802, 24, 2, 66: units pass 170 90 802 2 24 45 75 66; tens pass 802 2 24 45 66 170 75 90; hundreds pass 2 24 45 66 75 90 170 802.
Asked: [7 marks] (Jun 2020) Write short notes: comparison of indexing and hashing; radix sort; insertion sort.
Comparison of sorting techniques
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>Sorting methods are compared on time in best, average and worst cases, extra space and stability.</mark>
| Method | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes |
| Selection | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | No |
| Insertion | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes |
| Quick | $O(n\log n)$ | $O(n\log n)$ | $O(n^2)$ | $O(\log n)$ | No |
| Merge | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(n)$ | Yes |
| Heap | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(1)$ | No |
Sequential search
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>
Definition. <mark>Searching is finding the position of a given key in a collection; sequential (linear) search compares the key with each element from the first until it is found or the list ends.</mark>
Key points.
- It works on unsorted data and needs no preparation.
- Best case is 1 comparison, $O(1)$, when the key is first; worst and average cases are $O(n)$.
- An unsuccessful search takes $n$ comparisons; a successful one takes about $\frac{n+1}{2}$ on average.
Step 1: for i = 0 to n-1
Step 2: if a[i] == key then return i
Step 3: return -1 (not found)
Example. Data 4, 21, 36, 14, 62, 91, 8, 22, 81, 77, 10. Key 8: compare with 4, 21, 36, 14, 62, 91, then 8, so found at index 6 (position 7) after 7 comparisons. Key 50: all 11 comparisons fail, so not found.
Answer frame. Open with the definition of searching; give the algorithm; trace key 8 and a missing key; close with $O(1)$ best and $O(n)$ worst.
Asked: [7 marks] (Jun 2023, Jun 2024) Explain sequential search and simulate it for the 11-item list 4, 21, 36... Asked: [7 marks] (Dec 2020) What do you mean by Searching? Explain Sequential search and Binary search with the help of example.
Binary search
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>
Definition. <mark>Binary search finds a key in a sorted array by repeatedly comparing it with the middle element and discarding the half that cannot contain it.</mark>
Key points.
- The array must be sorted, so an unsorted list such as the ones in the papers is sorted first.
- Set $low=0$, $high=n-1$ and compute $mid=\lfloor (low+high)/2 \rfloor$.
- If $a[mid]=key$ the search succeeds; if $key<a[mid]$ set $high=mid-1$; otherwise set $low=mid+1$.
- It fails when $low>high$.
- Each step halves the range, so at most $\lfloor\log_2 n\rfloor+1$ comparisons are needed: $O(\log n)$ worst and average, $O(1)$ best.
- It needs random access, so it suits arrays, not linked lists.
Step 1: low = 0, high = n-1
Step 2: while low <= high: mid = (low + high) / 2
Step 3: if a[mid] == key return mid
Step 4: else if key < a[mid] high = mid - 1 else low = mid + 1
Step 5: return -1
Example. DATA = 11, 22, 30, 33, 40, 44, 50, 60, 66, 77, 80, 88, 99, ITEM = 60 (index from 0).
| low | high | mid | a[mid] | Action |
|---|---|---|---|---|
| 0 | 12 | 6 | 50 | 60 > 50, low = 7 |
| 7 | 12 | 9 | 77 | 60 < 77, high = 8 |
| 7 | 8 | 7 | 60 | found |
ITEM 60 is found at index 7 (position 8). Sorted 4, 8, 10, 14, 21, 22, 36, 62, 77, 81, 91, key 81: mid 5 = 22, mid 8 = 77, mid 9 = 81, index 9. Sorted 5, 10, 12, 15, 21, 23, 32, 36, 38, 56, 83, 92, key 36: mids 5, 8, 6, 7 (23, 38, 32, 36), index 7. In 49, 98, 101, 123, 149, 194, 199, 211, 240, 286, 840, 930, key 123: mids 5, 2, 3, index 3.
Answer frame. Open with the sorted-array condition; write the steps with $mid$; give the low-high-mid table; close with $O(\log n)$ and the comparison with sequential search.
Asked: [14 marks] (Nov 2018) Write short notes: Binary search, Heap sort, Red Black tree, Stack. Asked: [7 marks] (May 2019, Dec 2023) Apply binary search to find 60 in the 13-item list (also 123 in the 12-item list). Asked: [7 marks] (Nov 2022, Dec 2025) Explain Binary search and simulate it for the 11-item list 4, 21, 36... Asked: [7 marks] (Dec 2024) Apply Binary search to search 36 in 21, 12, 36, 32, 38, 23... Asked: [7 marks] (Dec 2025) Explain Binary Search with an example. Pitfall: Searching an unsorted list directly loses the marks; sort first.
Comparison of search methods
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>Search methods are compared on the data condition they need and their time cost.</mark>
Sequential search needs no order and costs $O(1)$ best and $O(n)$ worst; binary search needs a sorted array and costs $O(\log n)$; hashing averages $O(1)$.
Hashing & Indexing
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>
Definition. <mark>Hashing maps a key to a table address by a hash function $h(k)$, giving direct access in $O(1)$ average time; indexing keeps a separate table of key and record address so records can be found without scanning the file.</mark>
Key points.
- A good hash function is fast, spreads keys uniformly and keeps collisions few.
- Division method: $h(k)=k \bmod m$, with $m$ a prime. Mid-square: square the key and take the middle digits (123 gives 15129, digits 512). Folding: split the key into parts and add them (123456789 gives 123+456+789=1368, keep 368).
- A collision occurs when two keys hash to the same slot.
- Separate chaining keeps a linked list at each slot for all keys that hash there.
- Open addressing stores the key in another slot: linear probing $(h+i) \bmod m$, quadratic probing $(h+i^2) \bmod m$, double hashing $(h+i\cdot h_1) \bmod m$.
- Indexing keeps a key-to-record-address table (dense or sparse, primary or secondary, or a B+ tree) so databases avoid scanning the file.
Example. Keys 2341, 4234, 2839, 430, 22, 397, 3920, $m=7$, $h=x \bmod 7$ gives 3, 6, 4, 3, 1, 5, 0; $h_1=(2x-1)\bmod 7$ gives 5, 4, 0, 5, 1, 2, 6.
Slots 0 to 6.
- Chaining: 3920; 22; empty; 2341 -> 430; 2839; 397; 4234.
- Linear probing: 397; 22; 3920; 2341; 2839; 430; 4234.
- Double hashing: 3920; 430; 22; 2341; 2839; 397; 4234.
Linear: 430 takes 5, 397 wraps to 0, 3920 takes 2. Double: 430 goes to $(3+5)\bmod 7=1$; 22 to $(1+1)\bmod 7=2$.
Stable sorting keeps equal keys in their original order: bubble, insertion, merge and radix are stable; selection, quick, heap and shell are not.
| Basis | Sequential file | Index sequential file |
|---|---|---|
| Access | Only sequential | Sequential and direct |
| Index | None | Index of keys |
| Search time | Slow, $O(n)$ | Fast |
| Storage | No extra | Extra for index |
Benefits: fast direct retrieval, ordered processing, suits large databases.
Hashing versus indexing: hashing gives $O(1)$ average search but poor range queries; indexing gives $O(\log n)$ search and supports ordered and range queries.
Answer frame. Open with the definition; give each hash function with an example; then collision and both resolution families; close with the file or stable-sort part as asked.
Asked: [14 marks] (Nov 2022) Write short notes on any two: Queue using linked list, Hashing, B+ tree, Postfix expression evaluation. Asked: [14 marks] (Dec 2023) Insert 2341, 4234, 2839, 430, 22, 397, 3920 into a table of size 7 by chaining, linear probing and double hashing. Asked: [7 marks] (Nov 2018) What do you mean by Hashing and Indexing? Asked: [7 marks] (Nov 2019) Explain collision resolution strategies? What is stable sorting Algorithm? Asked: [7 marks] (May 2019, Nov 2019) Differentiate between sequential file and index sequential file, also write down its benefits. Asked: [7 marks] (May 2019) What are hash function? Write down various popular hash function name. Asked: [7 marks] (Dec 2020) What is Hashing? Explain different Hash function method in detail. Asked: [7 marks] (Dec 2024) Write short notes: Hashing and Indexing, Heap Sort, Red Black Tree.
Case Study: Application of data structures in operating system, DBMS
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>
Definition. <mark>Operating systems and databases use standard data structures internally to manage processes, memory, files and data.</mark>
Key points.
- OS: queues for process scheduling and stacks for function calls and recursion; linked lists for free memory blocks; trees for directory structure; graphs for resource allocation and deadlock detection.
- DBMS: B and B+ trees for indexing; hash tables for hash indexing and joins; trees for query optimisation; graphs for schema and transaction dependency.
Asked: [7 marks] (Nov 2018) Write down the applications of data structures in OS and DBMS.
Last-minute revision
- Internal sort uses RAM; external sort uses disk files.
- Bubble and selection sort: $\frac{n(n-1)}{2}$ comparisons, $O(n^2)$.
- Quick sort: average $O(n\log n)$, worst $O(n^2)$.
- Insertion sort: worst $O(n^2)$, best $O(n)$; Shell gaps for $n=8$: 4, 2, 1.
- Merge and heap sort: $O(n\log n)$ always; merge needs $O(n)$ space.
- Binary search: sorted data, $mid=(low+high)/2$, $O(\log n)$; 60 at index 7.
- Sequential search: $O(1)$ best, $O(n)$ worst.
- Hash keys mod 7 of the Dec 2023 set: 3, 6, 4, 3, 1, 5, 0.
- Stable: bubble, insertion, merge, radix.
Memory hooks
- Bubble: biggest bubbles up; Selection: select the smallest; Insertion: like sorting playing cards.
- Chain, probe, double: three ways out of a collision.
Coverage checklist
- Sorting: Introduction: Q28, Q29.
- Sort methods like: Bubble Sort: Q27.
- Quick sort: Q4, Q19, Q20, Q21.
- Selection sort: Q25.
- Heap sort: definition and complexity.
- Insertion sort: Q16.
- Shell sort: Q26.
- Merge sort: Q17, Q18.
- Radix sort: Q22.
- comparison of various sorting techniques: complexity table.
- Searching: Basic Search Techniques: Sequential search: Q23, Q24.
- Binary search: Q1, Q5-Q8.
- Comparison of search methods: table.
- Hashing & Indexing: Q2, Q3, Q10-Q15.
- Case Study: Application of various data structures in operating system, DBMS etc.: Q9.