Searching & Sorting Algorithms: Techniques, Complexity & Applications

1. Introduction to Searching Algorithms

Searching algorithms locate a target value in a data structure. The choice depends on data order and access pattern.

1.1 Sequential Search

• Definition: Linear scan through an unsorted array/list until the target is found or the end is reached.
• How it works:
  • Compare each element sequentially with the target.
  • Return index if match found; else return -1.
• Time Complexity:
  • Best Case: $O(1)$ (target is first element).
  • Average/Worst Case: $O(n)$ (target is last or absent).

flowchart TD
    A["Start at index 0"] --> B["Compare with target"]
    B --> C{"Match?"}
    C -->|"Yes"| D["Return index"]
    C -->|"No"| E["Increment index"]
    E --> B

Example Trace: Search for 30 in [40, 6, 5, 21, 3, 100, 90, 7, 8, 12, 30]:

Step | Index | Value | Match?
-----|-------|-------|-------
1    | 0     | 40    | No
2    | 1     | 6     | No
...
11   | 10    | 30    | Yes → Return 10

1.2 Binary Search

• Definition: Efficient search for sorted arrays by repeatedly dividing the search interval in half.
• How it works:
  1. Compare target with middle element (mid = low + (high - low)/2).
  2. If match, return mid.
  3. If target < arr[mid], search left half; else search right half.
• Time Complexity: $O(\log n)$ (halving each step).

Example Trace: Search for 25 in [5, 8, 11, 15, 17, 21, 23, 25, 31, 37, 45, 48]:

Step | low | high | mid | arr[mid] | Action
-----|-----|------|-----|----------|-------
1    | 0   | 11   | 5   | 21       | 25 > 21 → low = 6
2    | 6   | 11   | 8   | 25       | Match → Return 8

2. Comparison of Searching Algorithms

In the real world:

• NTC’s Call Directory: Uses binary search on sorted phone books to quickly locate numbers (sorted by name/number).
• Daraz’s Product Search: Sequential search for unsorted product categories (e.g., "find a laptop") but binary search for sorted filters (e.g., "price < ₹5,000").

3. Introduction to Sorting Algorithms

Sorting rearranges data in ascending/descending order. Choices depend on stability, adaptability, and performance.

3.1 Bubble Sort

• Definition: Repeatedly steps through the list, compares adjacent elements, and swaps them if in wrong order.
• Time Complexity:
  • Best Case (already sorted): $O(n)$.
  • Worst/Average Case: $O(n^2)$.

flowchart TD
    A["i = 0"] --> B["j = 0"]
    B --> C{"arr[j] > arr[j+1]?"}
    C -->|"Yes"| D["Swap(arr[j], arr[j+1])"]
    D --> E["j++"]
    E --> B
    C -->|"No"| F["j++"]
    F --> G{"j < n-i-1?"}
    G -->|"Yes"| B
    G -->|"No"| H["i++"]
    H --> A

Example Trace: Sort [40, 6, 5, 21]:

Pass 1: [6, 5, 21, 40] (swap 40↔6, 40↔21)
Pass 2: [5, 6, 21, 40] (swap 21↔6)
Pass 3: [5, 6, 21, 40] (no swap)

3.2 Selection Sort

• Definition: Divides array into sorted/unsorted parts; repeatedly finds the minimum in unsorted and swaps it to the front.
• Time Complexity: Always $O(n^2)$.

flowchart TD
    A["i = 0 to n-1"] --> B["min_idx = i"]
    B --> C["j = i+1 to n-1"]
    C --> D{"min_idx = j if arr[j] < arr[min_idx]"}
    D --> C
    B --> E["Swap(arr[i], arr[min_idx])"]

Example Trace: Sort [40, 6, 5, 21]:

Step | min_idx | Swap Target | Action
-----|---------|--------------|-------
1    | 0       | 6 (index 1)  | Swap 40↔6 → [6, 40, 5, 21]
2    | 1       | 5 (index 2)  | Swap 40↔5 → [6, 5, 40, 21]
3    | 2       | 21 (index 3) | Swap 40↔21 → [6, 5, 21, 40]

3.3 Insertion Sort

• Definition: Builds sorted array one element at a time by inserting each new element into its correct position.
• Time Complexity:
  • Best Case (sorted): $O(n)$.
  • Worst Case: $O(n^2)$.

Example Trace: Sort [40, 6, 5, 21]:

Step | key | j   | arr[j] > key? | Shift | Insert
-----|-----|-----|---------------|-------|--------
1    | 6   | 0   | 40 > 6        | [40]→[ ] | [6, 40, 5, 21]
2    | 5   | 1   | 40 > 5        | [6,40]→[ ] | [5, 6, 40, 21]
3    | 21  | 2   | 40 > 21       | [5,6,40]→[ ] | [5, 6, 21, 40]

4. Advanced Sorting Algorithms

4.1 Merge Sort

• Definition: Divide-and-conquer algorithm that splits the array into halves, recursively sorts them, and merges the sorted halves.
• Time Complexity: $O(n\log n)$ (always).
• Space Complexity: $O(n)$ (auxiliary space).

flowchart TD
    A["Divide: Split array into two halves"] --> B["Left half sorted recursively"]
    A --> C["Right half sorted recursively"]
    B --> D["Merge left and right sorted halves"]
    C --> D

Example Trace: Sort [40, 6, 5, 21, 3, 100, 90, 7, 8, 12, 30]:

1. Divide:

   [40,6,5,21] | [3,100,90,7,8,12,30]
   

2. Merge:
   • Left half sorted: [5,6,21,40].
   • Right half sorted: [3,7,8,12,30,90,100].
   • Final merge: [3,5,6,7,8,12,21,30,40,90,100].

Code Example:

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

Run Trace: Input: [25, 37, 48, 25, 23, 17, 31, 45, 7, 21, 15, 8, 11]

Step | Array State
-----|-------------
1    | [7,8,11,15,21,23,25,25,31,37,45,48] (after merge)

4.2 Quick Sort

• Definition: Chooses a "pivot" element and partitions the array into two subarrays: elements < pivot and > pivot. Recursively sorts the subarrays.
• Time Complexity:
  • Best/Average Case: $O(n\log n)$.
  • Worst Case (bad pivot): $O(n^2)$ (e.g., already sorted array with first element as pivot).
• Space Complexity: $O(\log n)$ (stack space).

flowchart TD
    A["Choose pivot (e.g., last element)"] --> B["Partition: arr[0..i] < pivot, arr[i+1..n-1] >= pivot"]
    B --> C["Recursively sort left partition"]
    B --> D["Recursively sort right partition"]

Example Trace: Sort [35, 82, 18, 54, 13, 31, 20, 69, 19] (pivot = last element):

Step | Pivot | Partitioned Array          | Left/Right
-----|-------|----------------------------|-----------
1    | 19    | [13,18,19,31,20,35,82,54,69] | Left: [13,18,19,31,20], Right: [35,82,54,69]
2    | 20    | [13,18,19,20,31,35,82,54,69] | Left: [13,18,19], Right: [31,35,82,54,69]
...  | ...   | ...                        | ...
Final|       | [13,18,19,20,31,35,54,69,82]  | Sorted

Code Example:

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi-1)
        quick_sort(arr, pi+1, high)
def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

Run Trace: Input: [35, 82, 18, 54, 13, 31, 20, 69, 19]

Step | Pivot | i   | j   | Swap? | Array State
-----|-------|-----|-----|-------|-------------
1    | 19    | -1  | 0   | No    | [35,82,18,54,13,31,20,69,19]
...  | ...   | ... | ... | ...   | [13,18,19,20,31,35,54,69,82]

5. Comparison of Sorting Algorithms

In the real world:

• Pathao’s Ride Matching: Uses quick sort to rank drivers by proximity (avg. $O(n\log n)$) for faster matching.
• NEPSE Stock Sorting: Merge sort is used for stable ranking of stocks by price/volume (external sorting for large datasets).
• Khalti’s Transaction Logs: Insertion sort for small, frequently updated logs (adaptive to recent changes).

6. Practical Example: Sorting Daraz Orders

Scenario: Daraz receives 10 orders with delivery times (minutes): [40, 6, 5, 21, 3, 100, 90, 7, 8, 12]. Sort to prioritize faster deliveries.

Using Merge Sort:

1. Divide:

   [40,6,5,21] | [3,100,90,7,8,12]
   

2. Merge:
   • Left: [5,6,21,40].
   • Right: [3,7,8,12,90,100].
   • Final: [3,5,6,7,8,12,21,40,90,100].

Optimization:

• Quick Sort (avg. $O(n\log n)$) would be faster for this dataset, but merge sort guarantees $O(n\log n)$ worst case.

7. Exam Tip

• Focus Areas:
  • Definitions: Clearly state time/space complexity for each algorithm (e.g., "Binary search is $O(\log n)$ because it halves the search space").
  • Traces: Always show step-by-step state changes (e.g., array after each merge/partition). Use tables for clarity.
  • Comparisons: Highlight trade-offs (e.g., "Merge sort is stable but uses extra space; quick sort is in-place but sensitive to pivot choice").
  • Real-world Tie-ins: Relate algorithms to Nepalese examples (e.g., "NTC uses binary search on sorted call logs").
• Common Pitfalls:
  • Forgetting to handle edge cases (e.g., empty array in binary search).
  • Incorrect pivot selection in quick sort (always choose median-of-three for stability).
  • Miscounting steps in traces (e.g., off-by-one errors in loop bounds).
• Question Patterns:
  • Short Answer: Define an algorithm + time complexity (e.g., "Explain insertion sort’s best case").
  • Long Answer: Trace a full sort/search (e.g., "Sort [40,6,5,21] using merge sort").
  • Comparison: Table-based (e.g., "Compare bubble and quick sort").

Sample Question Breakdown:

"Using merge sort, sort the numbers: 40, 6, 5, 21, 3, 100, 90, 7, 8, 12, 30." How to Score Full Marks:

1. Divide Step: Show split into [40,6,5,21] and [3,100,90,7,8,12,30] (1 mark).
2. Recursive Sort: Trace left/right halves (2 marks).
3. Merge Step: Show merged subarrays with correct comparisons (3 marks).
4. Final Array: Present [3,5,6,7,8,12,21,30,40,90,100] (1 mark).
5. Time Complexity: State $O(n\log n)$ (1 mark).