Swift Data Structure and Algorithms: Implement Swift structures and algorithms natively

Data abstraction is a technique for managing complexity. We use data abstraction when designing our data structures because it hides the internal implementation from the developer. It allows the developer to focus on the interface that is provided by the algorithm, which works with the implementation of the data structure internally.

Data structures and algorithms are patterns used for solving problems. When used correctly they allow you to create elegant solutions to some very difficult problems.

In this day and age, when you use library functions for 90% of your coding, why should you bother to learn their implementations? Without a firm technical understanding, you may not understand the trade-offs between the different types and when to use one over another, and this will eventually cause you problems.

By developing a broad and deep knowledge of data structures and algorithms, you'll be able to spot patterns to problems that would otherwise be difficult to model. As you become experienced in identifying these patterns you begin seeing applications for their use in your day-to-day development tasks.

We will make use of Playgrounds and the Swift REPL in this section as we begin to learn about data structures in Swift.

Xcode 8.1 has added many new features to Playgrounds and updated it to work with the latest syntax for Swift 3.0. We will use Playgrounds as we begin experimenting with different algorithms so we can rapidly modify the code and see how changes appear instantly.

We are going to use the Swift compiler from the command-line interface known as the Read-Eval-Print-Loop, or REPL. Developers who are familiar with interpretive languages such as Ruby or Python will feel comfortable in the command-line environment. All you need to do is enter Swift statements, which the compiler will execute and evaluate immediately. To get started, launch the Terminal.app in the /Applications/Utilities folder and type swift from the prompt in macOS Sierra or OS X El Capitan. Alternatively, it can also be launched by typing xcrun swift. You will then be in the REPL:

erik@iMac ~ swift
Welcome to Apple Swift version 3.0 (swiftlang-800.0.46.2 clang-
800.0.38). Type :help for assistance.
  1>

Statement results are automatically formatted and displayed with their type, as are the results of their variables and constant values:

erik@iMac ~ swift
Welcome to Apple Swift version 3.0 (swiftlang-800.0.46.2 clang-
800.0.38). Type :help for assistance.
  1> var firstName = "Kyra"
firstName: String = "Kyra"
  2> print("Hello, \(firstName)")
Hello, Kyra
  3> let lastName: String = "Smith"
lastName: String = "Smith"
  4> Int("2000")
$R0: Int? = 2000

Note that the results from line four have been given the name $R0 by the REPL even though the result of the expression wasn't explicitly assigned to anything. This is so you can reference these results to reuse their values in subsequent statements:

  5> $R0! + 500
$R1: Int = 2500

The following table will come in handy as you learn to use the REPL; these are some of the most frequently used commands for editing and navigating the cursor:

Table 1.1 – Quick Reference

The first data structures we will explore are contiguous data structures. These linear data structures are index-based, where each element is accessed sequentially in a particular order.

Arrays

The array data structure is the most well-known data storage structure and it is built into most programming languages, including Swift. The simplest type is the linear array, also known as a one-dimensional array. In Swift, arrays are a zero-based index, with an ordered, random-access collection of elements of a given type.

For one-dimensional arrays, the index notation allows indication of the elements by simply writing ai, where the index i is known to go from 0 to n:

For example, give the array:

α = (3 5 7 9 13)

Some of the entries are:

α₀ = 3, α₁ = 5, ..., α₄ = 13

Another form of an array is the multidimensional array. A matrix is an example of a multidimensional array that is implemented as a two-dimensional array. The index notation allows indication of the elements by writing aij, where the indexes denote an element in row i and column j:

Given the matrix:

Some of the entries are:

α₀₀ = 2, α₁₁ = 3, ..., α₂₂ = 4

var myIntArray: Array<Int> = [1,3,5,7,9] 

var myIntArray: [Int] = [1,3,5,7,9] 

var myIntArray = [1,3,5,7,9] 

var myIntArray: [Int] = [] 

var my2DArray: [[Int]] = [[1,2], [10,11], [20, 30]] 

1> var myIntArray: [Int] = [1,3,5,7,9]
myIntArray: [Int] = 5 values {
  [0] = 1
  [1] = 3
  [2] = 5
  [3] = 7
  [4] = 9
}
  2> var someNumber = myIntArray[2]
someNumber: Int = 5

1> var myIntArray: [Int] = [1,3,5,7,9]
myIntArray: [Int] = 5 values {
  [0] = 1
  [1] = 3
  [2] = 5
  [3] = 7
  [4] = 9
}
  2> for element in myIntArray {
  3.     print(element)
  4. }

1
3
5
7
9

1> var myIntArray: [Int] = [1,3,5,7,9]
myIntArray: [Int] = 5 values {
  [0] = 1
  [1] = 3
  [2] = 5
  [3] = 7
  [4] = 9
}
2> var someSubset = myIntArray[2...4]
someSubset: ArraySlice<Int> = 3 values {
  [2] = 5
  [3] = 7
  [4] = 9
}

1> var my2DArray: [[Int]] = [[1,2], [10,11], [20, 30]]
my2DArray: [[Int]] = 3 values {
  [0] = 2 values {
    [0] = 1
    [1] = 2
  }
[1] = 2 values {
  [0] = 10
  [1] = 11
}
[2] = 2 values {
  [0] = 20
  [1] = 30
}

}
  2> var element = my2DArray[0][0]
element: Int = 1
3> element = my2DArray[1][1]
4> print(element)
11

1> var myIntArray: [Int] = [1,3,5,7,9]
myIntArray: [Int] = 5 values {
  [0] = 1
  [1] = 3
  [2] = 5
  [3] = 7
  [4] = 9
}
  2> myIntArray.append(10)
  3> print(myIntArray)
[1, 3, 5, 7, 9, 10]

1> var myIntArray: [Int] = [1,3,5,7,9]
myIntArray: [Int] = 5 values {
  [0] = 1
[1] = 3
[2] = 5
[3] = 7
[4] = 9
}
2> myIntArray.insert(4, at: 2)
3> print(myIntArray)
[1, 3, 4, 5, 7, 9]

1> var myIntArray: [Int] = [1,3]
myIntArray: [Int] = 2 values {
  [0] = 1
  [1] = 3
}
  2> myIntArray.removeLast()

$R0: Int = 3
  3> print(myIntArray)
[1]

1> var myIntArray: [Int] = [1,3,5,7,9]
myIntArray: [Int] = 5 values {
  [0] = 1
  [1] = 3
  [2] = 5
  [3] = 7
  [4] = 9
}
  2> myIntArray.remove(at: 3)
$R0: Int = 7
  3> print(myIntArray)
[1, 3, 5, 9]

Linked structures are composed of a data type and bound together by pointers. A pointer represents the address of a location in the memory. Unlike other low-level programming languages such as C, where you have direct access to the pointer memory address, Swift, whenever possible, avoids giving you direct access to pointers. Instead, they are abstracted away from you.

We're going to look at linked lists in this section. A linked list consists of a sequence of nodes that are interconnected via their link field. In their simplest form, the node contains data and a reference (or link) to the next node in the sequence. More complex forms add additional links, so as to allow traversing forwards and backwards in the sequence. Additional nodes can easily be inserted or removed from the linked list.

Linked lists are made up of nodes, which are self-referential classes, where each node contains data and one or more links to the next node in the sequence.

In computer science, when you represent linked lists, arrows are used to depict references to other nodes in the sequence. Depending on whether you're representing a singly or doubly linked list, the number and direction of arrows will vary.

In the following example, nodes S and D have one or more arrows; these represent references to other nodes in the sequence. The S node represents a node in a singly linked list, where the arrow represents a link to the next node in the sequence. The N node represents a null reference and represents the end of a singly linked list. The D node represents a node that is in a doubly linked list, where the left arrow represents a link to the previous node, and the right arrow represents a link to the next node in the sequence.

Singly and doubly linked list data structures

We'll look at another linear data structure, this time implemented as a singly linked list.

class LinkedList<T> {
    var item: T?
    var next: LinkedList<T>?
}

In studying algorithms, we often concern ourselves with ensuring their stingy use of resources. The time and space needed to solve a problem are the two most common resources we consider.

Specifically, we're interested in the asymptotic behavior of functions describing resource use in terms of some measure of problem size. We'll take a closer look at asymptotic behavior later in this chapter. This behavior is often used as a basis for comparison between methods, where we prefer methods whose resource use grows slowly as a function of the problem size. This means we should be able to solve larger problems quicker.

The algorithms we'll discuss in this book apply directly to specific data structures. For most data structures, we'll need to know how to:

Swift has two fundamental types: value types and reference types. Value types are a type whose value is copied when it is assigned to a variable or constant, or when it is passed to a function. Value types have only one owner. Value types include structures and enumerations. All of Swift's basic types are implemented as structures.

Reference types, unlike value types, are not copied on assignment but are shared. Instead of a copy being made when assigning a variable or passing to a function, a reference to the same existing instance is used. Reference types have multiple owners.

The Swift standard library defines many commonly used native types such as int, double, float, string, character, bool, array, dictionary, and set.

It's important to remember though that the preceding types, unlike in other languages, are not primitive types. They are actually named types, defined and implemented in the Swift standard library as structures. We'll discuss named types in the following section.

In Swift, types are also classified as named types and compound types. A named type is a type that can be user-defined and given a particular name when it's defined. Named types include classes, structures, enumerations, and protocols. In addition to user-defined named types, the Swift standard library also includes named types that represent arrays, dictionaries, sets, and optional values. Named types can also have their behavior extended by using an extension declaration.

Compound types are types without a name, In Swift, the language defines two compound types: function types and type types. A compound type can contain both named types, and other compound types. As an example, the following tuple type contains two elements: the first is the named type Int, and the second is another compound type (Float, Float):

(Int, (Float, Float))

Type aliases define an alternative name for existing types. The typealias keyword is similar to typedef in C-based languages. Type aliases are useful when working with existing types that you want to be more contextually appropriate to the domain you are working in. For example, the following associates the identifier TCPPacket with the type UInt16:

typealias TCPPacket = UInt16

Once you define a type alias you can use the alias anywhere you would use the original type:

1> typealias TCPPacket = UInt16
2> var maxTCPPacketSize = TCPPacket.max
maxTCPPacketSize: UInt16 = 65535

Swift provides three types of collections: arrays, dictionaries, and sets. There is one additional type we'll also discuss, even though it's technically not a collection—tuples, which allow for the grouping of multiple values into a compound value. The values that are ordered can be of any type and do not have to be of the same type as each other. We'll look at these collection classes in depth in the next chapter.

In estimating the running time for the preceding sort algorithms, we don't know what the constants c or k are. We know they are a constant of modest size, but other than that, it is not important. From our asymptotic analysis, we know that the log-linear merge sort is faster than the insertion sort, which is quadratic, even though their constants differ. We might not even be able to measure the constants directly because of CPU instruction sets and programming language differences. These estimates are usually only accurate up to a constant factor; for these reasons, we usually ignore constant factors in comparing asymptotic running times.

In computer science, Big-O is the most commonly used asymptotic notation for comparing functions, which also has a convenient notation for hiding the constant factor of an algorithm. Big-O compares functions expressing the upper bound of an algorithm's running time, often called the order of growth. It's a measure of the longest amount of time it could possibly take for an algorithm to complete. A function of a Big-O notation is determined by how it responds to different inputs. Will it be much slower if we have a list of 5,000 items to work with instead of a list of 500 items?

Let's visualize how insertion sort works before we look at the algorithm implementation.

Given the list in Step 1, we assume the first item is in sorted order. In Step 2, we start at the second item and compare it to the previous item, if it is smaller we move the higher item to the right and insert the second item in first position and stop since we're at the beginning. We continue the same pattern in Step 3. In Step 4, it gets a little more interesting. We compare our current item, 34, to the previous one, 63. Since 34 is less than 63, we move 63 to the right. Next, we compare 34 to 56. Since it is also less, we move 56 to the right. Next, we compare 34 to 17, Since 17 is greater than 34, we insert 34 at the current position. We continue this pattern for the remaining steps.

Now let's consider an insertion sort algorithm:

func insertionSort( alist: inout [Int]){ 
    for i in 1..<alist.count { 
        let tmp = alist[i] 
        var j = i - 1 
        while j >= 0 && alist[j] > tmp { 
            alist[j+1] = alist[j] 
            j = j - 1 
        } 
        alist[j+1] = tmp 
    } 
} 

If we call this function with an array of 500, it should be pretty quick. Recall previously where we said the insertion sort represents a quadratic running time where f(x) = c*n²+q. We can express the complexity of this function with the formula, ƒ(x) ϵ O(x²), which means that the function f grows no faster than the quadratic polynomial x² , in the asymptotic sense. Often a Big-O notation is abused by making statements such as the complexity of f(x) is O(x²). What we mean is that the worst case f will take O(x²) steps to run. There is a subtle difference between a function being in O(x²) and being O(x²), but it is important. Saying that ƒ(x) ϵ O(x²) does not preclude the worst-case running time of f from being considerably less than O(x²). When we say f(x) is O(x²), we're implying that x² is both an upper and lower bound on the asymptotic worst-case running time.

Let's visualize how merge sort works before we look at the algorithm implementation:

In Chapter 4, Sorting Algorithms, we will take a detailed look at the merge sort algorithm so we'll just take a high-level view of it for now. The first thing we do is begin to divide our array, roughly in half depending on the number of elements. We continue to do this recursively until we have a list size of 1. Then we begin the combine phase by merging the sublists back into a single sorted list.

Now let's consider a merge sort algorithm:

func mergeSort<T:Comparable>(inout list:[T]) { 
    if list.count <= 1 { 
        return 
    } 
     
    func merge(var left:[T], var right:[T]) -> [T] { 
        var result = [T]() 
         
        while left.count != 0 && right.count != 0 { 
            if left[0] <= right[0] { 
                result.append(left.removeAtIndex(0)) 
            } else { 
                result.append(right.removeAtIndex(0)) 
            } 
        } 
         
        while left.count != 0 { 
            result.append(left.removeAtIndex(0)) 
        } 
         
        while right.count != 0 { 
            result.append(right.removeAtIndex(0)) 
        } 
         
        return result 
    } 
     
    var left = [T]() 
    var right = [T]() 
     
    let mid = list.count / 2 
     
    for i in 0..<mid { 
        left.append(list[i]) 
    } 
     
    for i in mid..<list.count { 
        right.append(list[i]) 
    } 
     
    mergeSort(&left) 
    mergeSort(&right) 
     
    list = merge(left, right: right) 
} 

In Table 1.3, we can see with smaller sized inputs it appears at first glance that the insertion sort offers better performance over the merge sort:

Table 1.3 – Small Input Size: 100-1,000 items / seconds

We can see from the following graph that the insertion sort performs quicker than the merge sort:

We can see in Table 1.4, what happens as our input gets very large using the insertion sort and merge sort we used previously:

Table 1.4 – Very Large Input Size: 2,000-60,000 items / seconds

In this graph, the data clearly shows that the insertion sort algorithm does not scale for larger values of n:

Algorithmic complexity is a very important topic in computer science; this was just a basic introduction to the topic to raise your awareness on the subject. Towards the end of this book, we will cover these topics in greater detail in their own chapter.