Searching & Sorting

Overview

Searching and sorting are fundamental operations in computer science and software development. Swift provides built-in methods, but understanding and implementing common algorithms from scratch is essential for building a strong foundation in data structures and algorithms.

Searching Algorithms

1. Linear Search

• Time Complexity: O(n)

• Use when data is unsorted

func linearSearch<T: Equatable>(_ array: [T], target: T) -> Int? {
    for (index, value) in array.enumerated() {
        if value == target {
            return index
        }
    }
    return nil
}

2. Binary Search

• Time Complexity: O(log n)

• Requires sorted array

func binarySearch<T: Comparable>(_ array: [T], target: T) -> Int? {
    var low = 0
    var high = array.count - 1

    while low <= high {
        let mid = low + (high - low) / 2
        if array[mid] == target {
            return mid
        } else if array[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return nil
}

Sorting Algorithms

1. Bubble Sort

• Time Complexity: O(n²)

• Stable and simple but inefficient for large data sets

func bubbleSort<T: Comparable>(_ array: inout [T]) {
    for i in 0..<array.count {
        for j in 0..<array.count - i - 1 {
            if array[j] > array[j + 1] {
                array.swapAt(j, j + 1)
            }
        }
    }
}

2. Insertion Sort

• Time Complexity: O(n²)

• Good for small or nearly sorted data sets

func insertionSort<T: Comparable>(_ array: inout [T]) {
    for i in 1..<array.count {
        var j = i
        let key = array[j]
        while j > 0 && array[j - 1] > key {
            array[j] = array[j - 1]
            j -= 1
        }
        array[j] = key
    }
}

3. Merge Sort

• Time Complexity: O(n log n)

• Stable and efficient, uses extra space

func mergeSort<T: Comparable>(_ array: [T]) -> [T] {
    guard array.count > 1 else { return array }

    let middle = array.count / 2
    let left = mergeSort(Array(array[0..<middle]))
    let right = mergeSort(Array(array[middle..<array.count]))

    return merge(left, right)
}

private func merge<T: Comparable>(_ left: [T], _ right: [T]) -> [T] {
    var result: [T] = []
    var i = 0, j = 0

    while i < left.count && j < right.count {
        if left[i] <= right[j] {
            result.append(left[i])
            i += 1
        } else {
            result.append(right[j])
            j += 1
        }
    }

    return result + left[i...] + right[j...]
}

4. Quick Sort

• Time Complexity: O(n log n) average, O(n²) worst

• Fast and commonly used

func quickSort<T: Comparable>(_ array: [T]) -> [T] {
    guard array.count > 1 else { return array }

    let pivot = array[array.count / 2]
    let less = array.filter { $0 < pivot }
    let equal = array.filter { $0 == pivot }
    let greater = array.filter { $0 > pivot }

    return quickSort(less) + equal + quickSort(greater)
}

When to Use Each Algorithm

Summary

Mastering these searching and sorting algorithms gives you the tools to solve a wide range of programming problems. While Swift’s sort() is optimized under the hood, knowing the mechanics behind these algorithms deepens your understanding and helps in performance-critical or educational scenarios.