12 Sorting & Searching

Sorting & Searching

Finding order and efficiency. From binary search to advanced sorting algorithms.

13 Sorting & Searching: Finding Order in Chaos

Why sort? Because searching becomes trivial.

My realization: Divide and Conquer isn’t just an algorithm strategy; it’s a life strategy. Merge Sort taught me that breaking a big problem into tiny, solvable pieces is the way to go.

13.1 Sorting Algorithms

13.1.1 1. Quick Sort

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    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)

13.1.2 2. Merge Sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

13.1.3 3. Heap Sort

def heap_sort(arr):
    n = len(arr)
    
    # Build max heap
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extract elements one by one
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # Swap
        heapify(arr, i, 0)

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

13.2 Searching Algorithms

13.2.1 1. Binary Search

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

13.2.2 2. Find Kth Largest Element

def find_kth_largest(nums, k):
    import heapq
    
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    
    return min_heap[0]

13.3 Time Complexity

Algorithm	Time (Best)	Time (Avg)	Time (Worst)	Space
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)
Binary Search	O(1)	O(log n)	O(log n)	O(1)

13.4 Common Problems

13.5 Tips for Interviews

For sorted arrays, always consider binary search first
Use two pointers technique for certain search problems
For Kth element problems, consider using heaps
Know the time/space complexity of built-in sort functions in your language
Practice implementing sorting algorithms from scratch

--- title: "Sorting & Searching" format: html toc: true --- ```{=html} <div class="hero-section fade-in"> <h1>Sorting & Searching</h1> <p class="lead">Finding order and efficiency. From binary search to advanced sorting algorithms.</p> </div> ``` # Sorting & Searching: Finding Order in Chaos Why sort? Because searching becomes trivial. **My realization:** Divide and Conquer isn't just an algorithm strategy; it's a life strategy. Merge Sort taught me that breaking a big problem into tiny, solvable pieces is the way to go. ## Sorting Algorithms ### 1. Quick Sort ```python def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] 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) ``` ### 2. Merge Sort ```python def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result ``` ### 3. Heap Sort ```python def heap_sort(arr): n = len(arr) # Build max heap for i in range(n//2 - 1, -1, -1): heapify(arr, n, i) # Extract elements one by one for i in range(n-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # Swap heapify(arr, i, 0) def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) ``` ## Searching Algorithms ### 1. Binary Search ```python def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 ``` ### 2. Find Kth Largest Element ```python def find_kth_largest(nums, k): import heapq min_heap = [] for num in nums: heapq.heappush(min_heap, num) if len(min_heap) > k: heapq.heappop(min_heap) return min_heap[0] ``` ## Time Complexity | Algorithm | Time (Best) | Time (Avg) | Time (Worst) | Space | |-----------|-------------|------------|--------------|-------| | Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | | Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | | Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | | Binary Search | O(1) | O(log n) | O(log n) | O(1) | ## Common Problems 1. [Merge Intervals](https://leetcode.com/problems/merge-intervals/) 2. [Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/) 3. [Find Peak Element](https://leetcode.com/problems/find-peak-element/) 4. [Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/) 5. [Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/) ## Tips for Interviews 1. For sorted arrays, always consider binary search first 2. Use two pointers technique for certain search problems 3. For Kth element problems, consider using heaps 4. Know the time/space complexity of built-in sort functions in your language 5. Practice implementing sorting algorithms from scratch