Swift

Introduction The insertion sort algorithm builds a sorted list one item at a time by comparison. It is more efficient on small datasets but much less efficient on larger ones. source source Code Example func insertionSort(_ array: [Int]) -> [Int] { var A = array for i in 0 ..< A.count { var j = i while j > 0 && A[j - 1] > A[j] { let tmp = A[j] A[j] = A[j - 1] A[j - 1] = tmp j -= 1 } } return A } Implementation For each index in the input array: Set the j variable to i. Loop while j is greater than 0 and the element at index j - 1 is greater than the element at index j: Swap the elements at index j and j - 1. Decrement j by 1. Why use Insertion Sort? Fast for small data sets. More efficient in practice than most other algorithms, such as selection sort or bubble sort. Adaptive: Efficient for datasets that are already substantially sorted; the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position. Stable: Does not change the relative order of elements with equal keys. In-place: Only requires O(1) of additional memory space. Online: Can sort a list as it receives it. Time/Space Complexity Time: O(N^2) Space: O(1) (in-place) Thank you for reading! 😊

What is Merge Sort? Merge sort is a recursive algorithm that uses the divide and conquer algorithm design paradigm to find the solution. source The merge sort conceptually consists of two separate functions: mergeSort and merge. It works as follows: Divide the unsorted list into two equal halves. Recursively sort the two halves. Merge the two halves to form a sorted array. There are multiple implementations of merge sort. I will be focusing on the top-down implementation using lists. ...

What is the Bubble Sort Algorithm? The bubble sort is a basic sorting algorithm named after the way elements progressively “bubble up” to the top of the list. source Code Example func bubbleSort(_ array: [Int]) -> [Int] { var A = array var N = array.count var swapping = true while swapping { swapping = false for i in 1 ..< N { if A[i - 1] > A[i] { let tmp = A[i - 1] A[i - 1] = A[i] A[i] = tmp swapping = true } } N -= 1 } return A } Implementation The bubble sort uses an loop and swapping property to control it behaviour. Inside the loop, it iterates over all elements, comparing the current and next elements. If the current element is greater than the next, it swaps them. ...

Introduction Previously, we discussed a custom hashmap implementation. That implementation has a lot of collisions because we are using a fixed-size array. If we want to reduce the chances of collisions, we can increase the number of slots in the hashmap, or in other words, resize our hashmap. Resizing cannot guarantee that collisions will be entirely eliminated, but it will help reduce the likelihood of one happening. Code Example private func loadFactor() -> Double? { if self.hashMap.isEmpty { return nil } else { var filledSlots = 0 for slot in self.hashMap { if slot != nil { filledSlots += 1 } } return Double(filledSlots / self.hashMap.count) } } private func resize() { if self.hashMap.isEmpty { self.hashMap = [nil] return } guard let load = self.loadFactor() else { return } if load < 0.05 { return } let oldHashMap = self.hashMap self.hashMap = Array(repeating: nil, count: oldHashMap.count * 10) for kvp in oldHashMap { if let kvp = kvp { self.insert(key: kvp.key, value: kvp.value) } } } Implementation When resizing, we create a new hashmap with a larger number of slots. Then, we re-insert all the key-value pairs from the old hashmap into the new one. ...

Introduction Let’s take a closer look at a HashMap implementation by building it without using the built-in dictionary in Swift. The HashMap will use a fixed-size array underneath the hash function that will transform the key into an index. In this example, the hash function is based on taking the modulo of the sum of all key.unicodeScalars integer values with the size of the array. Code Example final class HashMap<Key: StringProtocol, Value> { private var hashMap: [(key: Key, value: Value)?] init(size: Int) { self.hashMap = Array(repeating: nil, count: size) } private func hashFunction(key: Key) -> Int { var count = 0 for element in key.unicodeScalars { count += Int(element.value) } return count % self.hashMap.count } } Insert The insert operation uses the index provided by the hashFunction and sets the value at this index. ...