Algorithms — Sorting and Searching

**1. What is an Algorithm? — Recipes for Computers**

An algorithm is a step-by-step set of instructions to solve a problem. Just like a biryani recipe tells you exactly what to do in what order, an algorithm tells a computer exactly how to process data.

Good algorithms are:

• Correct — they produce the right output
• Efficient — they don't waste time or memory
• Clear — each step is unambiguous

In Pakistan's tech scene — from Karachi's Arbisoft to Lahore's Systems Limited — software engineers write and optimise algorithms daily. Understanding searching and sorting is fundamental to every tech career.

**2. Searching Algorithms**

Linear Search:

• Check each item one by one from start to end
• Works on unsorted AND sorted data
• Simple but slow for large datasets

Steps:

1. Start at the first item
2. Compare with the target value
3. If match → found! Return position
4. If no match → move to next item
5. If end of list reached → item not found

Efficiency: Worst case checks **every** item. For a list of 1 million items, worst case = 1 million comparisons.

Binary Search:

• Works ONLY on sorted data
• Repeatedly divides the list in half
• Much faster than linear search for large datasets

Steps:

1. Find the middle item
2. Compare with target
3. If match → found!
4. If target < middle → search the left half
5. If target > middle → search the right half
6. Repeat until found or sublist is empty

Example: Searching for "Karachi" in an alphabetically sorted list of Pakistani cities:

• Middle = "Lahore". Karachi < Lahore → search left half
• New middle = "Hyderabad". Karachi > Hyderabad → search right half
• New middle = "Islamabad". Karachi > Islamabad → search right half
• Found "Karachi"!

Efficiency: For 1 million items, binary search needs at most **20 comparisons** (log₂ 1,000,000 ≈ 20). That's 20 vs 1,000,000 — binary search is massively faster.

**3. Sorting Algorithms**

Bubble Sort:

• Compare adjacent pairs, swap if in wrong order
• Repeat passes until no swaps needed
• Simple but slow for large datasets

Steps:

1. Compare items at position 0 and 1 — swap if needed
2. Compare items at position 1 and 2 — swap if needed
3. Continue to end of list (one pass complete)
4. The largest item "bubbles" to the end
5. Repeat passes until a complete pass has zero swaps

Example: Sort [5, 3, 8, 1]:

• Pass 1: [3,5,8,1] → [3,5,8,1] → [3,5,1,8] — 2 swaps
• Pass 2: [3,5,1,8] → [3,1,5,8] — 1 swap
• Pass 3: [1,3,5,8] — 1 swap
• Pass 4: [1,3,5,8] — 0 swaps → DONE!

Merge Sort:

• Divide and conquer strategy
• Split the list into halves until each sublist has 1 item
• Merge sublists back together in sorted order
• Much faster than bubble sort for large datasets

Steps:

1. Divide: Split list into two halves
2. Recurse: Keep splitting until sublists have 1 item each
3. Merge: Combine sublists by comparing first elements and taking the smaller one

Example: Sort [8, 3, 5, 1]:

• Split: [8,3] and [5,1]
• Split: [8] [3] and [5] [1]
• Merge: [3,8] and [1,5]
• Merge: [1,3,5,8] ✓

**4. Comparing Algorithms**

| Algorithm | Best For | Speed | Memory | Data Must Be Sorted? |

|---|---|---|---|---|

| Linear Search | Small/unsorted lists | Slow (n comparisons) | Low | No |

| Binary Search | Large sorted lists | Fast (log₂n) | Low | Yes |

| Bubble Sort | Small lists, nearly sorted | Slow (n² comparisons) | Low (in-place) | N/A |

| Merge Sort | Large lists | Fast (n log n) | Higher (needs extra space) | N/A |

Trade-offs: Merge sort is faster but uses more memory. Bubble sort is simple to code but painfully slow on large datasets. Binary search is fast but requires sorted data — so you may need to sort first.

**5. Exam Strategy**

• Trace tables are your best friend — show every step of the algorithm with actual values.
• Bubble sort: count the number of passes and swaps. Show the list after each pass.
• Binary search: show the middle element, which half you discard, and repeat.
• Always state whether the data needs to be sorted first (binary search = yes).
• "Compare two algorithms" questions: mention speed, memory usage, and suitability for the data size.
• Merge sort diagrams: draw the full split tree AND the merge tree with values at each level.