Sorting & Searching Algorithms: Techniques, Analysis & Applications

Core Concepts

1. Sorting Algorithms: Classification & Comparison

Sorting rearranges elements into a specific order (ascending/descending). Algorithms differ in efficiency, stability, and adaptability.

Comparison-Based vs. Non-Comparison-Based

Why does this matter?

• Comparison-based sorts have a lower bound of $O(n\log n)$ (proven by decision tree analysis).
• Non-comparison sorts exploit additional information (e.g., integer ranges) for linear time.

2. Key Sorting Algorithms (Visualized)

A. Bubble Sort (Simple but Inefficient)

How it works: Repeatedly swaps adjacent elements if they are in the wrong order. Time Complexity:

• Best: $O(n)$ (already sorted)
• Average/Worst: $O(n^2)$

Code (Iterative):

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped: break  # Early exit if sorted

Trace for [5,3,8,4]:

B. Merge Sort (Divide & Conquer)

How it works:

1. Divide: Split array into halves.
2. Conquer: Recursively sort each half.
3. Merge: Combine sorted halves.

Time Complexity: Always $O(n\log n)$ (stable, not in-place).

flowchart TD
    A["MergeSort([38,27,43,3,9,82,10])"] --> B["Divide: [38,27,43] | [3,9,82,10]"]
    B --> C["Recurse Left: [38,27,43] → [27,38,43]"]
    B --> D["Recurse Right: [3,9,82,10] → [3,9,10,82]"]
    C --> E["Merge [27,38,43] + [3,9,10,82] → [3,9,10,27,38,43,82]"]

Code (Recursive):

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]
        merge_sort(L)
        merge_sort(R)
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        while i < len(L): arr[k] = L[i]; i += 1; k += 1
        while j < len(R): arr[k] = R[j]; j += 1; k += 1

Trace for [38,27,43,3,9,82,10]:

C. Quick Sort (Efficient, In-Place)

How it works:

1. Pivot Selection: Choose a pivot (e.g., last element).
2. Partition: Rearrange so elements < pivot are left, > pivot are right.
3. Recurse: Sort subarrays.

Time Complexity:

• Best/Average: $O(n\log n)$
• Worst: $O(n^2)$ (if pivot is smallest/largest).

Code (Randomized Pivot):

import random
def quick_sort(arr):
    if len(arr) <= 1: return arr
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

Trace for [10,80,30,90,40,50,70] (pivot=70):

3. Searching Algorithms

A. Linear Search (Brute-Force)

How it works: Check each element sequentially until the target is found. Time Complexity: $O(n)$ (worst/average/best).

Code:

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Trace for [4,2,7,1] searching 7:

B. Binary Search (Efficient for Sorted Data)

How it works: Repeatedly divide the search interval in half. Time Complexity: $O(\log n)$ (must be sorted).

Code (Recursive):

def binary_search(arr, target):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Trace for [1,3,5,7,9] searching 5:

In the Real World

1. eSewa (Nepal):

   • Uses sorted transaction queues to prioritize payments (e.g., electricity bills, fines).
   • Binary search optimizes user lookup in the database of 10M+ accounts.

2. Ncell (Telecom):

   • Merge sort organizes call logs by timestamp for billing reports.
   • Quick sort ranks customers by data usage for targeted promotions.

3. Daraz (E-Commerce):

   • Linear search checks inventory for product availability in real-time.
   • Hash tables (with chaining) store user profiles for $O(1)$ access.

4. NEPSE (Stock Exchange):

   • Binary search trees maintain share prices for efficient trading order matching.
   • Heap sort ranks stocks by volatility for portfolio analysis.

Worked Example: Sorting Ncell Customer Data

Scenario: Ncell has 5 customers with data usage (in GB): [3.2, 1.5, 4.7, 0.9, 2.1]. Sort to identify top 3 users for a bonus.

Solution: Use Quick Sort (in-place, efficient for medium-sized data).

data = [3.2, 1.5, 4.7, 0.9, 2.1]
quick_sort(data)  # Sorted: [0.9, 1.5, 2.1, 3.2, 4.7]
top_3 = data[:3]  # [0.9, 1.5, 2.1] → Wait, this is the lowest! Correct approach:

Correction: To get highest usage, sort in descending order:

quick_sort(data, reverse=True)  # [4.7, 3.2, 2.1, 1.5, 0.9]
top_3 = data[:3]  # [4.7, 3.2, 2.1]

Output: Ncell rewards customers with usage > 2.1 GB.

Comparison Table: Sorting Algorithms

*Stack space for recursion.

Searching Algorithm Comparison

Exam Tip

1. Define Clearly:

   • Binary search: "A divide-and-conquer algorithm that repeatedly halves the search space by comparing the target to the middle element of a sorted array."
   • Stable sort: "Preserves the relative order of equal elements."

2. Pseudocode > Code:

   • Exams often ask for iterative/recursive algorithms in plain English. Focus on steps, not syntax.

3. Complexity is Key:

   • Always state best/average/worst case for sorting/searching.
   • Example: "Merge sort has $O(n\log n)$ time in all cases but requires $O(n)$ auxiliary space."

4. Real-World Links:

   • Relate to Nepalese systems:
     • "eSewa uses hash tables for user authentication (O(1) lookup)."
     • "Ncell’s billing system sorts transactions (Merge Sort) before generating reports."

5. Trace Tables:

   • For binary search, show low/high/mid values at each step.
   • For sorting, illustrate array state after each pass.

6. Common Pitfalls:

   • Off-by-one errors in binary search (e.g., high = mid vs high = mid - 1).
   • Unsorted input for binary search (always check!).
   • Quick Sort pivot choice: Randomized pivot avoids worst-case $O(n^2)$.

Practice Questions (Exam Style)

1. Define:

   • What is a stable sorting algorithm? Give an example.
   • Explain why linear search is $O(n)$ in the worst case.

2. Algorithm Design:

   • Write the iterative binary search algorithm and analyze its time complexity.
   • Convert the recursive Quick Sort to an iterative version using a stack.

3. Application:

   • "NTC needs to sort 10,000 electricity bill records by due date. Recommend a sorting algorithm and justify your choice."
   • "Pathao’s ride-matching system uses a priority queue to assign drivers. Which sorting algorithm underlies this queue?"

4. Trace:

   • Perform one pass of Bubble Sort on [64, 34, 25, 12, 22, 11, 90].
   • Trace binary search for [5, 10, 15, 20, 25] searching 15.

5. Comparison:

   • "Why is Merge Sort preferred over Quick Sort for sorting linked lists?"
   • "When would you use Linear Search over Binary Search?"