pavel-sazonov · May 25, 2019 15:43 · May 25, 2019 · May 25, 2019 · May 24, 2019 · May 24, 2019
diff --git a/algorithms.swift b/algorithms.swift
@@ -25,7 +25,7 @@ func findMinIndex(_ arr: [Int]) -> Int {
     var minElement = arr[0]
     var minIndex = 0
 
-    for index in arr.indices {
+    for index in 1..<arr.count {
         if arr[index] < minElement {
             minElement = arr[index]
             minIndex = index

diff --git a/algorithms.swift b/algorithms.swift
@@ -265,4 +265,40 @@ search(name: "you")
 // thom is Mango Seller
 
 
+// Chapter 7. Dijkstra's algorithm (SPF)
 
+// Chapter 8. Greedy algorithm
+
+// You pass an array in, and it gets converted to a set.
+var statesNeeded : Set = ["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]
+
+var stations = [String: Set<String>]()
+stations["kone"] = ["id", "nv", "ut"]
+stations["ktwo"] = ["wa", "id", "mt"]
+stations["kthree"] = ["or", "nv", "ca"]
+stations["kfour"] = ["nv", "ut"]
+stations["kfive"] = ["ca", "az"]
+
+var finalStations = Set<String>();
+
+while !statesNeeded.isEmpty {
+    var bestStation = String()
+    var statesCovered = Set<String>()
+
+    for station in stations {
+        var covered = statesNeeded.intersection(station.value)
+        if covered.count > statesCovered.count {
+            bestStation = station.key
+            statesCovered = covered
+        }
+        statesNeeded = statesNeeded.subtracting(statesCovered)
+        //Swift note: We should avoid adding empty station to Set
+        if !bestStation.isEmpty {
+            finalStations.insert(bestStation)
+        }
+    }
+}
+
+print(finalStations) // -> ["kone", "kfive", "ktwo", "kthree"]
+
+// Chapter 9: Dynamic Programming
diff --git a/algorithms.swift b/algorithms.swift
@@ -175,7 +175,7 @@ print(quickSort(&arr))
 
 // Chapter 6: Breadth Search
 
-// Deaue Realization
+// Dequeue Realization
 
 public struct Deque<T> {
     private var array = [T]()

diff --git a/algorithms.swift b/algorithms.swift
@@ -51,6 +51,8 @@ func selectionSort(_ arr: [Int]) -> [Int] {
 
 func factorial(_ x: Int) -> Int {
     return x == 1 ? 1 : x * factorial(x - 1)
+
+    // OR:
     /*
         if x == 1 {
             return 1

diff --git a/algorithms.swift b/algorithms.swift
@@ -171,5 +171,96 @@ var arr = Array(1...100)
 print(quickSort(&arr))
 
 
+// Chapter 6: Breadth Search
+
+// Deaue Realization
+
+public struct Deque<T> {
+    private var array = [T]()
+
+    public var isEmpty: Bool {
+        return array.isEmpty
+    }
+
+    public var count: Int {
+        return array.count
+    }
+
+    public mutating func enqueue(_ element: T) {
+        array.append(element)
+    }
+
+    public mutating func enqueueFront(_ element: T) {
+        array.insert(element, at: 0)
+    }
+
+    public mutating func dequeue() -> T? {
+        if isEmpty {
+            return nil
+        } else {
+            return array.removeFirst()
+        }
+    }
+
+    public mutating func dequeueBack() -> T? {
+        if isEmpty {
+            return nil
+        } else {
+            return array.removeLast()
+        }
+    }
+
+    public func peekFront() -> T? {
+        return array.first
+    }
+
+    public func peekBack() -> T? {
+        return array.last
+    }
+}
+
+func personIsSeller(name: String) -> Bool {
+    return name.last == "m"
+}
+
+var graph = [String : [String]]()
+graph["you"] = ["alice", "bob", "claire"]
+graph["bob"] = ["anuj", "peggy"]
+graph["alice"] = ["peggy"]
+graph["claire"] = ["thom", "jonny"]
+graph["anuj"] = []
+graph["peggy"] = []
+graph["thom"] = []
+graph["jonny"] = []
+
+func search(name: String) -> Bool {
+    var searchQueue = Deque<String>()
+    var searched = [String]()
+
+    for name in graph[name]! {
+        searchQueue.enqueue(name)
+    }
+
+    while !searchQueue.isEmpty {
+        let person = searchQueue.dequeue()!
+        if !searched.contains(person) {
+            if personIsSeller(name: person) {
+                print("\(person) is Mango Seller")
+                return true
+            } else {
+                for name in graph[person]! {
+                    searchQueue.enqueue(name)
+                }
+                searched.append(person)
+            }
+        }
+    }
+
+    return false
+}
+
+search(name: "you")
+// thom is Mango Seller
+
 
 
diff --git a/algorithms.swift b/algorithms.swift
@@ -137,7 +137,38 @@ max([1, 5, 10, 25, 16, 1])
  max([1, 5, 10, 25, 16, 1]): subMax = max([1, 5, 10, 25, 16]) = 25
 */
 
+// Maybe O(n^2) or O(n log n)
+func quickSort(_ arr: [Int]) -> [Int] {
+    guard arr.count > 1 else { return arr }
 
+    let pivot = arr[0]
+    var less = [Int]()
+    var greater = [Int]()
+
+    arr.dropFirst().forEach {
+        $0 <= pivot ? less.append($0) : greater.append($0)
+    }
+    return quickSort(less) + [pivot] + quickSort(greater)
+}
+
+var arr = Array(1...100).shuffled()
+quickSort(arr)
+
+// Will be O(n log n)
+func quickSort(_ arr: inout [Int]) -> [Int] {
+    guard arr.count > 1 else { return arr }
+
+    let pivot = arr.remove(at: arr.count / 2)
+    var less = [Int]()
+    var greater = [Int]()
+
+    arr.forEach {
+        $0 <= pivot ? less.append($0) : greater.append($0)
+    }
+    return quickSort(&less) + [pivot] + quickSort(&greater)
+}
+var arr = Array(1...100)
+print(quickSort(&arr))
 
 
 

diff --git a/algorithms.swift b/algorithms.swift
@@ -72,3 +72,73 @@ factorial(3)
 
 
 // Chapter 4 Quick Sort
+
+func sum(_ arr: [Int]) -> Int {
+    guard !arr.isEmpty else { return 0 }
+
+    var tempArr = arr
+    return tempArr.removeLast() + sum(tempArr)
+}
+
+sum([1,2,3])
+
+/*
+ sum([]) -> 0
+
+ sum([1]) -> sum([]) + 1 = 0 + 1
+
+ sum([1,2]) -> sum([1]) + 2 = 1 + 2 = 3
+
+ sum([1, 2, 3]) -> sum([1,2]) + 3 = 3 + 3 = 6
+*/
+
+func count(_ arr: [Int]) -> Int {
+    guard !arr.isEmpty else { return 0 }
+
+    var tempArr = arr
+    tempArr.removeLast()
+    return 1 + count(tempArr)
+}
+
+count([1,2,3])
+
+/*
+ count([]) -> 0
+
+ count([1]) -> 1 + count([]) = 1 + 0 = 1
+
+ count([1,2]) -> 1 + count([1]) = 1 + 1 = 2
+
+ count([1,2,3]) -> 1 + count([1,2]) = 1 + 2 = 3
+*/
+
+func max(_ arr: [Int]) -> Int {
+    guard arr.count > 1 else { return arr.first ?? 0 }
+
+    if arr.count == 2 {
+        return arr[0] > arr[1] ? arr[0] : arr[1]
+    }
+
+    let subMax = max(arr.dropLast())
+    return (arr.last! > subMax) ? arr.last! : subMax
+}
+
+max([1, 5, 10, 25, 16, 1])
+
+/*
+ max([1, 5]) -> 5
+
+ max([1, 5, 10]: subMax = max([1, 5]) = 5 -> 10
+
+ max([1, 5, 10, 25]: subMax = max([1, 5, 10]) = 10 -> 25
+
+ max([1, 5, 10, 25, 16]: subMax = max([1, 5, 10, 25] = 25 -> 25
+
+ max([1, 5, 10, 25, 16, 1]): subMax = max([1, 5, 10, 25, 16]) = 25
+*/
+
+
+
+
+
+
diff --git a/algorithms.swift b/algorithms.swift
@@ -0,0 +1,74 @@
+// Chapter 1 Binary Search
+
+func binarySearch(arr: [Int], num: Int) -> Int? {
+    var low = 0
+    var high = arr.count - 1
+
+    while low <= high {
+        let mid = (low + high) / 2
+        let guess = arr[mid]
+        if guess == num {
+            return mid
+        }
+        if guess < num {
+            low = mid + 1
+        } else {
+            high = mid - 1
+        }
+    }
+    return nil
+}
+
+// Chapter 2 Selection Sort
+
+func findMinIndex(_ arr: [Int]) -> Int {
+    var minElement = arr[0]
+    var minIndex = 0
+
+    for index in arr.indices {
+        if arr[index] < minElement {
+            minElement = arr[index]
+            minIndex = index
+        }
+    }
+    return minIndex
+}
+
+
+func selectionSort(_ arr: [Int]) -> [Int] {
+    var mutableArr = arr
+    var sortedArr = [Int]()
+
+    for _ in mutableArr {
+        let index = findMinIndex(mutableArr)
+        sortedArr.append(mutableArr.remove(at: index))
+    }
+
+    return sortedArr
+}
+
+// Chapter 3 Recursion
+
+func factorial(_ x: Int) -> Int {
+    return x == 1 ? 1 : x * factorial(x - 1)
+    /*
+        if x == 1 {
+            return 1
+        } else {
+            return x * factorial(x - 1)
+        }
+    */
+}
+
+factorial(3)
+
+/*
+ factiorial(1) -> 1
+
+ factiorial(2) -> 2 * factiorial(1) = 2 * 1 = 2
+
+ factorial(3) -> 3 * factiorial(2) = 3 * 2 = 6
+ */
+
+
+// Chapter 4 Quick Sort