Searching & Sorting: Algorithms, Analysis, and Real-World Applications

Core Concepts: Searching Algorithms

1. Linear Search

Definition: A simple search algorithm that checks each element sequentially until the target is found or the list ends.

How it works:

• Start from the first element.
• Compare each element with the target.
• If found, return its position; else, continue until the end.

Visualization:

graph LR
    A["Start"] --> B["Check arr[0] == target?"]
    B -->|"Yes"| C["Return index 0"]
    B -->|"No"| D["Check arr[1] == target?"]
    D -->|"Yes"| E["Return index 1"]
    D -->|"No"| F["Check arr[n-1] == target?"]
    F -->|"Yes"| G["Return index n-1"]
    F -->|"No"| H["Target not found"]

Example: Search for 12 in [11, 19, 5, 2, 7, 21, 8, 21, 12]:

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

Trace:

Time Complexity: $O(n)$ (worst/average case). Space Complexity: $O(1)$ (in-place).

2. Binary Search

Definition: A fast search algorithm for sorted arrays that repeatedly divides the search interval in half.

How it works:

1. Compare the target with the middle element.
2. If equal, return the index.
3. If target < middle, search the left half; else, search the right half.
4. Repeat until found or the interval is empty.

Visualization (Searching for 12 in [2, 5, 7, 8, 11, 12, 19, 21, 21]):

Example Code:

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 12 in [2,5,7,8,11,12,19,21,21]:

Time Complexity: $O(\log n)$ (best/average/worst case). Space Complexity: $O(1)$ (iterative).

## In the real world

• eSewa (Nepal): Uses binary search to quickly locate user transactions in its sorted database of millions of records, reducing search time from $O(n)$ to $O(\log n)$.
• Khalti’s Payment Sorting: When processing bulk transactions, Khalti sorts payment amounts using merge sort (stable and efficient for large datasets) to group similar transactions for fraud detection.
• NTC’s Call Routing: The National Telecommunications Commission uses priority queues (a type of queue) to route emergency calls (highest priority) before regular calls, ensuring critical services are handled first.

Core Concepts: Sorting Algorithms

1. Insertion Sort

Definition: Builds the final sorted array one element at a time by inserting each new element into its correct position in the already-sorted part.

How it works:

1. Start with the second element.
2. Compare it with elements in the sorted subarray (left side).
3. Shift elements to make space and insert the current element in its correct position.

Visualization (Sorting [90, 57, 80, 10, 22]):

graph TD
    A["Initial: [90] [57] [80] [10] [22]"] --> B["Insert 57: [57, 90]"]
    B --> C["Insert 80: [57, 80, 90]"]
    C --> D["Insert 10: [10, 57, 80, 90]"]
    D --> E["Insert 22: [10, 22, 57, 80, 90]"]

Example Code:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Trace for [90, 57, 80, 10, 22]:

Time Complexity:

• Best case: $O(n)$ (already sorted).
• Average/Worst case: $O(n^2)$. Space Complexity: $O(1)$ (in-place).

Advantages:

• Simple to implement.
• Efficient for small or nearly sorted datasets.
• Stable (preserves order of equal elements).

Disadvantages:

• Inefficient for large datasets ($O(n^2)$ time).

2. Selection Sort

Definition: Repeatedly selects the smallest (or largest) element from the unsorted part and swaps it with the first unsorted element.

How it works:

1. Find the minimum element in the unsorted array.
2. Swap it with the first unsorted element.
3. Repeat for the remaining unsorted subarray.

Visualization (Sorting [64, 25, 12, 22, 11]):

graph TD
    A["Initial: [64, 25, 12, 22, 11]"] --> B["Find min (11), swap with 64: [11, 25, 12, 22, 64]"]
    B --> C["Find min (12), swap with 25: [11, 12, 25, 22, 64]"]
    C --> D["Find min (22), swap with 25: [11, 12, 22, 25, 64]"]

Example Code:

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

Trace for [64, 25, 12, 22, 11]:

Time Complexity: $O(n^2)$ (all cases). Space Complexity: $O(1)$ (in-place).

Advantages:

• Simple to implement.
• Performs well for small datasets.

Disadvantages:

• Inefficient for large datasets.
• Unstable (does not preserve order of equal elements).

3. Bubble Sort

Definition: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

How it works:

1. Compare adjacent elements.
2. If they are in the wrong order, swap them.
3. Repeat until the list is sorted.

Visualization (Sorting [5, 1, 4, 2, 8]):

graph TD
    A["Initial: [5,1,4,2,8]"] --> B["Pass 1: [1,4,2,5,8]"]
    B --> C["Pass 2: [1,2,4,5,8]"]
    C --> D["Pass 3: [1,2,4,5,8] (sorted)"]

Example Code:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

Trace for [5, 1, 4, 2, 8]:

Time Complexity:

• Best case: $O(n)$ (already sorted, with optimized version).
• Average/Worst case: $O(n^2)$. Space Complexity: $O(1)$ (in-place).

Advantages:

• Simple to implement.
• Stable (preserves order of equal elements).

Disadvantages:

• Inefficient for large datasets.
• Performs many unnecessary swaps.

4. Merge Sort

Definition: A divide-and-conquer algorithm that recursively splits the array into halves, sorts them, and merges the sorted halves.

How it works:

1. Divide the unsorted array into $n$ subarrays of size 1.
2. Merge subarrays to produce new sorted subarrays until the entire array is sorted.

Visualization (Sorting [38, 27, 43, 3, 9, 82, 10]):

Example Code:

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]:

Time Complexity: $O(n\log n)$ (all cases). Space Complexity: $O(n)$ (requires auxiliary space).

Advantages:

• Efficient for large datasets.
• Stable (preserves order of equal elements).
• Works well for linked lists.

Disadvantages:

• Requires $O(n)$ extra space.
• Slower than quicksort for small datasets.

5. Quick Sort

Definition: A divide-and-conquer algorithm that selects a 'pivot' element and partitions the array into two subarrays: elements less than the pivot and elements greater than the pivot.

How it works:

1. Choose a pivot (e.g., last element).
2. Partition the array such that elements < pivot are on the left, and elements > pivot are on the right.
3. Recursively sort the subarrays.

Visualization (Sorting [10, 7, 8, 9, 1, 5] with pivot = last element):

Example Code:

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

Trace for [10, 7, 8, 9, 1, 5]:

Time Complexity:

• Best/Average case: $O(n\log n)$.
• Worst case: $O(n^2)$ (when pivot is smallest/largest element). Space Complexity: $O(\log n)$ (due to recursion stack).

Advantages:

• Fastest in practice for large datasets.
• In-place (minimal extra space).
• Cache-friendly (good locality).

Disadvantages:

• Unstable (does not preserve order of equal elements).
• Worst-case performance can be avoided with good pivot selection (e.g., median-of-three).

6. Heap Sort

Definition: Uses a binary heap data structure to sort elements. It first builds a max-heap (or min-heap) and repeatedly extracts the maximum (or minimum) element.

How it works:

1. Build a max-heap from the input data.
2. Extract the maximum element (root) and place it at the end of the array.
3. Reduce the heap size and heapify the root to maintain the heap property.
4. Repeat until the heap is empty.

Visualization (Heapify and Sort [12, 9, 1, 13, 16, 24, 21, 5]):

graph TD
    A["Initial Array: [12,9,1,13,16,24,21,5]"] --> B["Max-Heap: [24,16,21,13,12,9,1,5]"]
    B --> C["Extract 24: [16,12,21,13,5,9,1]"]
    C --> D["Heapify: [21,12,16,13,5,9,1]"]
    D --> E["Extract 21: [16,12,9,13,5,1]"]
    E --> F["Heapify: [16,12,9,13,5,1]"]
    F --> G["Final Sorted: [1,5,9,12,13,16,21,24]"]

Example Code:

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

Trace for [12, 9, 1, 13, 16, 24, 21, 5]:

Time Complexity: $O(n\log n)$ (all cases). Space Complexity: $O(1)$ (in-place).

Advantages:

• Efficient for large datasets.
• In-place (no extra space).
• Guaranteed $O(n\log n)$ performance.

Disadvantages:

• Unstable (does not preserve order of equal elements).
• Slower in practice than quicksort due to poor cache performance.

Comparison of Sorting Algorithms

Exam Tip

1. Understand the Definitions:

   • Know the difference between internal (in-memory) and external (disk-based) sorting.
   • Differentiate between stable (preserves order) and unstable sorts.

2. Algorithm Selection:

   • For small datasets: Insertion Sort or Selection Sort.
   • For large datasets: Merge Sort or Quick Sort.
   • When stability matters: Merge Sort or Insertion Sort.
   • When memory is constrained: Heap Sort or Quick Sort.

3. Tracing is Key:

   • Always show step-by-step traces for sorting/searching algorithms in exams.
   • Draw arrays/heaps after each operation (e.g., heapify, partition).

4. Time Complexity:

   • Memorize the Big-O for best/average/worst cases of each algorithm.
   • Example: Quick Sort is $O(n\log n)$ on average but $O(n^2)$ in the worst case.

5. Real-World Applications:

   • Relate algorithms to Nepali examples (e.g., eSewa’s binary search, Khalti’s merge sort).
   • Explain how priority queues (used in Pathao’s ride allocation) work.

6. Common Pitfalls:

   • Forgetting to sort the array first before binary search.
   • Incorrect pivot selection in Quick Sort leading to worst-case performance.
   • Misapplying stable vs. unstable sorts in scenarios where order matters.