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

All lessons in HEC NSCT – National Skill Competency Test: Complete Preparation for Computing Graduates