Courses / HEC NSCT – National Skill Competency Test: Complete Preparation for Computing Graduates
3.6 Searching, Sorting and Algorithm Design
Area 3 – Data Structures & Algorithms (10%) · 50 min read · 21 MCQs to check yourself
Searching
| Algorithm | Needs sorted data? | Time |
|---|---|---|
| Linear search | No | O(n) |
| Binary search | Yes | O(log n) – check middle, discard half each step |
Sorting cheat sheet
| Algorithm | Best | Average | Worst | Stable? | Idea |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | Yes | Swap adjacent pairs; largest "bubbles" to the end |
| Selection | O(n²) | O(n²) | O(n²) | No | Select the minimum, put it in front |
| Insertion | O(n) | O(n²) | O(n²) | Yes | Insert each item into the sorted part – great for nearly sorted data |
| Merge | O(n log n) | O(n log n) | O(n log n) | Yes | Divide, sort halves, merge; O(n) extra space |
| Quick | O(n log n) | O(n log n) | O(n²) (bad pivot) | No | Partition around a pivot; in-place |
| Heap | O(n log n) | O(n log n) | O(n log n) | No | Build heap, extract max repeatedly |
| Counting / Radix | O(n + k) | Yes | Not comparison-based; small integer ranges | ||
| Comparison-based sorting cannot beat O(n log n) in the worst case. Stable = equal keys keep their original order. |
Algorithm design techniques
| Technique | Idea | Examples |
|---|---|---|
| Divide and conquer | Split, solve parts, combine | Merge sort, quick sort, binary search |
| Greedy | Take the best local choice each step | Dijkstra, Kruskal, Prim, Huffman coding, activity selection |
| Dynamic programming | Solve overlapping subproblems once and store answers (memoisation/tabulation) | Fibonacci, 0/1 knapsack, LCS, Floyd-Warshall |
| Backtracking | Try options, undo when a choice fails | N-Queens, Sudoku, maze |
| Brute force | Try everything | Small inputs, checking answers |
10 sorting algorithms easily explained (Coding with Lewis)
This lesson ends with a quiz of 21 MCQs. Open the lesson on PrepOasis to take it and save your progress.
Previous: 3.5 Hashing · Next: Area 3 Review, Checklist and Area Test