Swift 3.1 Algorithms

http://www.knowstack.com/swift-3-1-algorithms-part-1/

In this post we will implement the following algorithms in Swift
  • Implementing a stack in Swift
  • Implementing a queue in Swift
  • Prime Numbers – Check if a number is prime
  • List of Prime numbers less than a given number
  • Binary Search
  • Binary Search Using Swift Generics
  • Quick Sort
  • Selection Sort
  • Insertion Sort
  • Recursively Searching a File in folders and sub folders
  • Bubblesort
  • Merge Sort

 

Implementing a Stack in Swift

In this sample we will implement a stack using an array.
The stack has a first in last out or last in first out implementation.
We can push an element to the top of the stack and pop to remove the top element of the stack.
The pop function will remove and return the top most element of the stack.
We can also have a function called as lastObject that returns the top most element of the stack without removing it from the stack.
import Cocoa

struct Stack{
    fileprivate var array = [T]()
    
    func isEmpty()->Bool{
        return array.isEmpty
    }
    
    func count()->Int{
        return array.count
    }
    //We use mutating function when we are actually changing the variables in our struct!
    mutating func push(element:T){
        array.append(element)
    }
    
    mutating func pop()->T?{
        return array.popLast()
    }
    
    func top()-> T?{
        return array.last
    }
}

var stack = Stack()
print(stack.pop())      //nil - as nothing is there in the stack yet
print(stack.top())      //nil
print(stack.count())    //0
//Lets add a few elements
stack.push(element: 10)
stack.push(element: 20)
stack.push(element: 30)
print(stack.count())    //3
print(stack)            //Stack(array: [10, 20, 30])
print(stack.top())      //Optional(30)
print(stack.pop())      //Optional(30) At this point 30 is popped/removed from the stack
print(stack)            //Stack(array: [10, 20])
print(stack.count())    //2

Implementing a Queue in Swift

Queue is First In First Out.
The item that is enqueued first is the one that gets dequeued the first.
This is a sample implementation using an array to hold the items of the queue.
Array is not a good choice for a queue implementation as when an object is dequeued, all other objects in the queue must be moved forward to fill in the gap leading to a O(n) iteration.
Using a linked list to hold the items in the queue would be a better option.
struct Queue{
    fileprivate var array = [T]()
    
    func isEmpty()->Bool{
        return array.isEmpty
    }
    
    func count()->Int{
        return array.count
    }
    
    mutating func enqueue(element:T){
        array.append(element)
    }
    
    mutating func dequeue()->T?{
        if isEmpty(){
            return nil
        }else{
            return array.removeFirst()
        }
    }
    
}

var queue = Queue()
queue.enqueue(element: 10)
queue.enqueue(element: 20)
print(queue) //Queue(array: [10, 20])
queue.dequeue()
print(queue) //Queue(array: [20])
print(queue.count()) //1

Prime Numbers – Check if a number is prime

import Cocoa
//Given a number - to check if its prime or not.
func isPrime(num:Int) -> Bool{
    if (num == 2 || num == 3){
        return true
    }
    var isPrime = true
    let maxDivisor = Int(sqrt(Double(num)))
    for i in 2...maxDivisor{
        if (num % i) == 0{
            isPrime = false
            break
        }
    }
    return isPrime
}
print ("3 is prime = \(isPrime(num: 3))")
print ("4 is prime = \(isPrime(num: 4))")
print ("11 is prime = \(isPrime(num: 11))")
print ("47 is prime = \(isPrime(num: 47))")
print ("113 is prime = \(isPrime(num: 113))")

List of Prime numbers less than a given number

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Sieve of Eratosthenes approach to find the list of prime numbers in an array
The simple sieve of Eratosthenes (250s BCE)
The problem with the sieve of Eratosthenes is not the number of operations it performs but rather its memory requirements.[8] For large n, the range of primes may not fit in memory; worse, even for moderate n, its cache use is highly suboptimal.
func primeNumbersList(lessThan:Int)->[Int]{
    var primeNumbers:[Int] = []
    //Create list of integers from 2...lessThan
    var allNumbers = Array(2...lessThan)
    var allNumTuple = [(name: Int, value: Bool)]()
    for num in allNumbers{
        allNumTuple.append((name:num, value:true))
    }
    var index = 2
    while index < lessThan{
        if allNumTuple[index].value == false{
            index += 1
            continue
        }
        var iCount = Int(lessThan/index)
        if iCount == 1{
            break
        }
        for i in 2...iCount{
            var refIndex = i * index
            if (refIndex <= lessThan){
                    allNumTuple[(refIndex-2)].value = false
            }
            
        }
        index += 1
    }
    var nums = allNumTuple.filter { (name:Int, value:Bool) -> Bool in
        return value == true
    }
    for item in nums{
        primeNumbers.append(item.name)
    }
    return primeNumbers
}

var primeNumbers = primeNumbersList(lessThan: 100)
print("prime numbers less than 100 = \(primeNumbers)")
//prime numbers less than 100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97]
//Todo – may be implement the sieve of atkin in Swift Someday
//https://en.wikipedia.org/wiki/Sieve_of_Atkin

Binary Search

import Cocoa

//Binary Search of an Int in an Int Array

func binarySearch(arrayToBeSearched:[Int], searchItem:Int) ->Int{
    var index:Int = -1
    var lowerIndex = 0
    var upperIndex = arrayToBeSearched.count - 1
    if upperIndex == -1{ //Check if searching an empty array
        return -1
    }
    else{
        while (true){
            var currentIndex = (lowerIndex + upperIndex)/2
            if (arrayToBeSearched[currentIndex] == searchItem){
                return currentIndex
            }
            else if (lowerIndex > upperIndex){
                return -1
            }
            else{
                if arrayToBeSearched[currentIndex] > searchItem{
                    upperIndex = currentIndex - 1
                }
                else{
                    lowerIndex = currentIndex + 1
                }
            }
        }
    }
    return index
}


var arrayToBeSearched = [1,2,3,5,7,8,11,13,76,98,101,121,131,144,176]
var foundIndex = binarySearch(arrayToBeSearched: arrayToBeSearched, searchItem: 780)
print("found Index = \(foundIndex)")

Binary Search Using Swift Generics

func binarySearch(arrayToBeSearched:Array, searchItem:T) -> Int{
    var index:Int = -1
    var lowerIndex = 0
    var upperIndex = arrayToBeSearched.count - 1
    if upperIndex == -1{ //Check if searching an empty array
        return -1
    }
    else{
        while (true){
            var currentIndex = (lowerIndex + upperIndex)/2
            if (arrayToBeSearched[currentIndex] == searchItem){
                return currentIndex
            }
            else if (lowerIndex > upperIndex){
                return -1
            }
            else{
                if arrayToBeSearched[currentIndex] > searchItem{
                    upperIndex = currentIndex - 1
                }
                else{
                    lowerIndex = currentIndex + 1
                }
            }
        }
    }
    return index
}

var arrayToBeSearched1 = [1,2,3,5,7,8,11,13,76,98,101,121,131,144,176]
var fIndex = binarySearch(arrayToBeSearched: arrayToBeSearched1, searchItem: 176)
print("found Index = \(fIndex)")

//The String array needs to be sorted
var stringArray = ["John","Jane","Mary","Bill","Will","Bob"].sorted(){$0<$1}
var strIndex = binarySearch(arrayToBeSearched: stringArray, searchItem: "Jane")
print("String found at index = \(strIndex)")

Quick Sort

Quick Sort
The quicksort algorithm divides a list/array into two smaller arrays (low elements & high elements)
Step 1: Pick a pivot point (In this sample we have picked a random pivot point between the range of the list)
Step 2: Divide/Reorder the list so that all the elements smaller than the pivot is added to the low elements array and all the elements greater than the pivot are added to the high element array.
Step 3: Repeat Step 1 and Step 2 for the sub arrays/lists
Recreate the array by joining (the lowelement array), (the pivot) and (the high element array)
import Cocoa
var totalIteration = 0
func quickSort(array:[Int])->[Int]{
    var sortedArray:[Int] = []
    if array.count > 0 {
        if array.count == 1{
            return array
        }
        let pivot = Int(arc4random_uniform(UInt32(array.count)))
        var leftArray = [Int]()
        var rightArray = [Int]()
        let pivotValue = array[pivot]
        for num in array{
            if num < pivotValue{
                leftArray.append(num)
            }
            else{
                rightArray.append(num)
            }
            totalIteration += 1
        }
        
        sortedArray.append(contentsOf: quickSort(array: leftArray))
        sortedArray.append(contentsOf: quickSort(array: rightArray))
        
        
    }
    return sortedArray
}

var sortedArray = quickSort(array: [100,-10,123,11,32,76,89,90,10,21,98])
print("sortedArray = \(sortedArray)") //sortedArray = [-10, 10, 11, 21, 32, 76, 89, 90, 98, 100, 123]
print("totalIteration = \(totalIteration)")

Selection Sort

https://en.wikipedia.org/wiki/Selection_sort
Selection Sort
It has O(n^2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.
The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
import Cocoa

func selectionSort(array:[Int])->[Int]{
    var sortedArray = array
    
    var i_min = 0
    for i in 0..<sortedArray.count{
        i_min = i
        for j in i+1..<sortedArray.count{
            if sortedArray[j] < sortedArray[i_min]{
                i_min = j
            }
        }
        if (i_min != i){
            swap(&sortedArray[i], &sortedArray[i_min])
        }
    }
    return sortedArray
}

var sortedArray = selectionSort(array: [67,71,11,32,98,12,100])
print(sortedArray) //[11, 12, 32, 67, 71, 98, 100]

Insertion Sort

https://en.wikipedia.org/wiki/Insertion_sort
Extract from the above link
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position.
import Cocoa

func insertionSort(array:[Int]) ->[Int]{
    var sortedArray = array
    for i in 1..<sortedArray.count{         
           var j = i         
           while (j>0 && sortedArray[j-1] > sortedArray[j]){
            swap(&sortedArray[j-1], &sortedArray[j])
            j -= 1
        }
        //print(sortedArray)
    }
    return sortedArray
}

var sortedArray = insertionSort(array: [56,32,12,98,89,90,21])
print(sortedArray)

Recursively Searching a File in folders and sub folders

import Cocoa
//Recursively look for files in a directory
func searchFiles(directoryPath:String) ->[String]{
    var array = [String]()
    let fileManager = FileManager.default
    do {
        let contents = try fileManager.contentsOfDirectory(atPath: directoryPath)
        print(contents)
        for filePath in contents{
            let newPath = directoryPath + "/" + filePath
            var isDir : ObjCBool = false
            if fileManager.fileExists(atPath: newPath, isDirectory: &isDir){
                if isDir.boolValue{
                    array.append(contentsOf: searchFiles(directoryPath: newPath))
                }
                else{
                    array.append(newPath)
                }
            }
        }
        
    } catch {
        print("Error here")
    }
    return array
    
}

var files = searchFiles(directoryPath: "/Users/debasis_das/Desktop/filetest")
print(files)

Bubblesort

import Cocoa

//Bubble Sort
func bubbleSort(arr:[Int])->[Int]{
    var sortedArray = arr
    var swapped:Bool = true
    while swapped{
        swapped = false
        for i in 1..<sortedArray.endIndex{             if sortedArray[i-1] > sortedArray[i]{
                swap(&sortedArray[i], &sortedArray[(i-1)])
                swapped = true
            }
            
        }
    }
    return sortedArray
}


var array1 = bubbleSort(arr: [32,12,12,23,11,19,81,76])
print(array1)

Merge Sort

import Cocoa

func mergeSort(array:[Int])->[Int]{
    if array.count < 2{
        return array
    }
    let middle = array.count/2
    let lArray = array[0..<middle]
    let rArray = array[middle..<array.count]     
    return merge(leftArray: mergeSort(array: Array(lArray)), rightArray: mergeSort(array: Array(rArray))) 
} 

    func merge(leftArray:[Int], rightArray:[Int])->[Int]{
    var left = 0
    var right = 0
    var result:[Int] = []
    while left rightArray[right]{
            result.append(rightArray[right])
            right += 1
        }
        else{
            result.append(leftArray[left])
            left += 1
            result.append(rightArray[right])
            right += 1
        }
        
    }
    
    while left<leftArray.count{
        result.append(leftArray[left])
        left += 1
    }
    while right<rightArray.count{
        result.append(rightArray[right])
        right += 1
    }
    
    return result
}

var sortedArray = mergeSort(array: [100,908,23,32,13,45,54])
print("sortedArray = \(sortedArray)") //sortedArray = [13, 23, 32, 45, 54, 100, 908]

Comments

Post a Comment

Popular posts from this blog

Installing Mac OS X 10.11 El Capitan on VMWare

Image
1-  Requirements 2-  Download Mac OS X 10.11 3-  Mac OS X Unlocker for VMware 4-  Install virtual operating system Mac OS 5-  Install VMWare Tools 6-  You may be interested 1- Requirements In this document, I will guide you how to install   Mac OS 10.11  on   VMWare . First of all, you must ensure that your computer have been install    VMWare .  VMWare version 12 is highly recommend.  See Also: TODO Link! Installing Mac OS X Virtual Machine on VirtualBox 2- Download Mac OS X 10.11 Download  Mac OS X 10.11. Download  Mac OS X 10.11  (Backup Link) Unzip the file that you have just downloaded: 3- Mac OS X Unlocker for VMware You need to unlock   Mac OS  for   VMWare  before creating a virtual operating system   Mac OS  on   VMWare.  To do this, you need a software....
Read more

Swift Programming Tutorials

Image
Installing Mac OS X 10.11 El Capitan on VMWare Installing and Configuring XCode Swift Tutorial for Beginners Swift Functions Tutorial Swift Closures Tutorial Class and Object in Swift Swift Enums Tutorial Swift Structs Tutorial Programming for Team using XCode and SVN    *   *  Basic Swift 4 and iOS 11 - Free Preview     Beginner's Swift 4 & Unreal Engine - Learn Xcode, Make Games     C# Unity® and Swift 4 Masterclass: Make Games and Apps     Create an app like Twitter with Swift     How to create a Flappy Bird inspired iPhone game in Swift 2     iOS 10 Swift 3 - A Complete Practical Approach     iOS 11 & Swift 4.0 - A Beginner's Guide with Projects     iOS 11 & Swift 4: From Beginner to Paid Professional™     iOS 11 / Swift 4 - Programming 101     iOS Development - Create 4 Quiz Apps with Swift 3 & iOS 10     Make ...
Read more

IPHONE MOCKUP WIREFRAME SERVICE

Image
https://www.spaceotechnologies.com/iphone-mockup-wireframes-service/ IPHONE MOCKUP WIREFRAME SERVICE Turning your ideas into reality is easier than you think… Our Expertise in Wireframe Services Information Architecture Prototype Development Code Review and Documentation Services Mockup for iPhone app iPhone App Prototyping Wireframe Services for iPhone Design Realistic Mock Ups Create Stunning wireframes What is an iPhone Mockup Wireframe Service? Here at Space-O technologies, we believe in involving our clients in every phase of the design and development of their iPhone application. Therefore, we create wireframes for iPhone apps so that our clients are able to follow the direction their app is taking throughout the process—from beginning to end. Our iPhone mockup wireframe service shows the skeletal framework of the iPhone app; allowing you to see how the user interface will work. IPhone mockup wireframe services act as a bridge for the information ar...
Read more